Pourquoi nous avons choisi CP-SAT plutôt que MIP

Deux paradigmes pour résoudre les problèmes difficiles

Quand il faut résoudre un problème d'optimisation à grande échelle, deux familles de solveurs dominent le paysage : la programmation linéaire en nombres entiers (MIP, Mixed-Integer Programming) et la programmation par contraintes (CP, Constraint Programming). Les deux peuvent résoudre des problèmes de planification du personnel. Les deux gèrent des centaines d'employés et des milliers de variables. Mais ils abordent le problème sous des angles fondamentalement différents, et le choix a des conséquences.

Les solveurs MIP comme Gurobi et CPLEX viennent de la tradition de la recherche opérationnelle. Ils modélisent les problèmes comme des systèmes d'inégalités linéaires et utilisent la relaxation linéaire combinée au branch-and-bound pour trouver des solutions optimales. Les solveurs CP comme CP-SAT de Google viennent de la tradition de l'intelligence artificielle et de la satisfaction de contraintes. Ils utilisent la propagation de contraintes, des techniques SAT et la génération de clauses paresseuses (lazy clause generation) pour explorer l'espace de recherche.

Cet article explique pourquoi nous avons choisi CP-SAT pour la planification du personnel, où chaque approche excelle, et où MIP serait le meilleur outil.

MIP : programmation linéaire en nombres entiers

Un solveur MIP fonctionne en relaxant les variables entières en valeurs continues, en résolvant le programme linéaire (LP) résultant, puis en utilisant le branch-and-bound pour retrouver des solutions entières. La relaxation LP fournit une borne inférieure sur l'objectif, que le solveur utilise pour élaguer l'arbre de recherche.

Points forts du MIP :

• Les variables continues sont natives. Si votre problème implique des quantités fractionnaires (allocation de coûts, flux de ressources, mélange), le MIP les gère directement. Pas de discrétisation nécessaire.
• Bornes LP serrées. Pour les problèmes avec des relaxations LP "serrées" (transport, flot à coût minimum, localisation d'installations), l'écart entre la borne LP et l'optimum entier est faible. Le solveur peut prouver l'optimalité rapidement.
• Solveurs commerciaux matures. Gurobi et CPLEX ont des décennies d'ingénierie derrière eux. Ils incluent le presolve, les coupes, les heuristiques et la recherche parallèle. Pour les problèmes LP/MIP bien structurés, ils sont extrêmement rapides.
• Bornes duales. Les solveurs MIP fournissent une borne inférieure prouvable à chaque instant de la recherche. Vous savez toujours à quelle distance votre solution courante se trouve de l'optimum théorique.

La formulation MIP canonique pour la planification utilise des variables entières 0/1 : x[e,d,s] = 1 si l'employé e travaille le shift s le jour d. Les contraintes sont écrites sous forme d'inégalités linéaires. L'objectif est une fonction linéaire des variables de décision. Cela fonctionne, mais la planification introduit une structure pour laquelle le MIP n'a pas été initialement conçu.

CP-SAT : programmation par contraintes avec SAT

CP-SAT est le solveur open-source de Google issu de la bibliothèque OR-Tools. Il combine trois techniques :

• Propagation de contraintes. Quand une variable est affectée ou qu'un domaine est réduit, le solveur propage immédiatement les conséquences à travers toutes les contraintes connectées. Cela élimine les valeurs impossibles avant même que la recherche ne les considère.
• Résolution SAT. Le solveur encode le problème comme un problème de satisfaisabilité booléenne et utilise des techniques SAT modernes : apprentissage de clauses par conflit (CDCL), redémarrages et sélection de variables par activité.
• Génération de clauses paresseuses (LCG). Quand le solveur rencontre un conflit, il génère une clause qui explique le conflit et l'ajoute à la base de clauses. Cela empêche le solveur de revisiter la même impasse.

Points forts de CP-SAT :

• Les variables booléennes sont des citoyens de première classe. La variable assign[e,d,s] est naturellement booléenne. Pas besoin de la modéliser comme une variable continue relaxée à [0,1] puis arrondie en entier.
• Types de contraintes riches. CP-SAT supporte nativement AllDifferent, Circuit, Element, Automaton, Reservoir et d'autres contraintes globales. Celles-ci encodent des structures combinatoires complexes en une seule contrainte, avec des algorithmes de propagation spécialisés.
• Pénalités non linéaires. Les objectifs peuvent inclure des expressions min/max, des valeurs absolues et des pénalités conditionnelles sans astuces de linéarisation.
• Recherche parallèle diversifiée. CP-SAT exécute simultanément plusieurs stratégies de recherche (workers), chacune avec des heuristiques différentes de sélection de variables et de valeurs. Cela fournit une diversification implicite sans réglage manuel.

La planification est fondamentalement combinatoire

La décision centrale en planification du personnel est : "L'employé e travaille-t-il le shift s le jour d ?" C'est une question oui/non. Il n'y a pas de "demi-affectation" significative où un employé travaille 0,6 d'un shift. Le problème est inhéremment discret et combinatoire.

En MIP, on modélise cela comme une variable entière 0/1 x[e,d,s]. La relaxation LP autorise x[e,d,s] = 0.3, ce qui n'a aucune signification physique. Le solveur passe du temps à brancher sur ces valeurs fractionnaires pour retrouver des solutions entières. Pour les problèmes de planification avec beaucoup de symétries (employés avec des qualifications identiques), la relaxation LP peut être faible, ce qui signifie que la borne est lâche et l'arbre de branch-and-bound est grand.

En CP-SAT, assign[e,d,s] est une variable booléenne dès le départ. Le solveur ne considère jamais d'affectations fractionnaires. Quand il décide que l'employé e travaille le jour d, la propagation de contraintes élimine immédiatement les shifts conflictuels. Cette gestion native des décisions booléennes est un avantage structurel pour la planification.

Où CP-SAT excelle pour la planification

Paires toxiques (repos minimum entre shifts)

La réglementation du travail impose 11 heures de repos entre la fin d'un shift et le début du suivant. Nous pré-calculons les "paires toxiques" : les combinaisons de shifts qui violeraient cette règle.

# CP-SAT : implication booleenne, propagee instantanement
assign[e, d, s1] + assign[e, d+1, s2] <= 1

En CP-SAT, c'est une implication booléenne native. Quand assign[e,d,s1] est fixé à 1, le solveur propage immédiatement assign[e,d+1,s2] = 0. Pas de branchement nécessaire. En MIP, la même contrainte est écrite de manière identique, mais la relaxation LP autorise les deux variables à valoir 0.5, ne fournissant aucun élagage utile tant que le solveur ne branche pas sur l'une d'elles.

Respect des qualifications

Si un employé n'est pas qualifié pour un shift, nous ne créons simplement pas la variable assign pour cette combinaison. En CP-SAT, c'est naturel : la variable n'existe pas, donc le solveur ne la considère jamais. En MIP, on fixe la variable à 0 (en ajoutant des contraintes explicites) ou on l'omet de la formulation (ce que les solveurs MIP peuvent aussi faire, mais le bénéfice de propagation en CP est plus fort car il se propage en cascade à travers les contraintes connectées).

Multi-objectif avec pénalités pondérées

Notre fonction objectif est une somme pondérée de termes de pénalité souples : couverture manquante (10 000 par poste), jours de repos manquants (1 500 par jour), pas de weekend garanti (5 000), violation jours consécutifs (2 000), jours de repos isolés (1 000), écarts d'équité par qualification (500), écarts d'équité de charge.

Chaque pénalité implique une logique conditionnelle : "si la couverture le jour d est inférieure à la cible, pénaliser le manque." En CP-SAT, cela s'exprime directement avec max(0, cible - affectes) sans linéarisation. En MIP, il faut des variables auxiliaires et des contraintes big-M pour modéliser la structure conditionnelle, ce qui peut affaiblir la relaxation LP.

Gestion des symétries

Quand plusieurs employés ont les mêmes qualifications et le même type de contrat, échanger leurs plannings produit une solution équivalente. Cette symétrie crée de vastes plateaux dans l'espace de recherche où le solveur ne progresse pas. La recherche parallèle diversifiée de CP-SAT, avec des workers utilisant différentes heuristiques et stratégies de redémarrage, gère la symétrie plus efficacement que le branch-and-bound du MIP, qui peut rester bloqué à explorer des branches équivalentes.

Où MIP est le meilleur choix

Optimisation continue

Si votre problème implique la minimisation d'une fonction de coût avec allocation fractionnaire de ressources, le MIP est le choix naturel. Problèmes de mélange, optimisation de portefeuille, planification de chaîne logistique avec flux continus : c'est le territoire du MIP. CP-SAT travaille avec des entiers et des booléens. Si vous avez besoin de x = 3.7, il faudrait mettre à l'échelle et discrétiser.

Problèmes avec relaxation LP serrée

Transport, flot à coût minimum, conception de réseau, localisation d'installations : ces problèmes ont des relaxations LP serrées. La borne LP est proche de l'optimum entier, et l'arbre de branch-and-bound est petit. Les solveurs MIP exploitent brillamment cette structure. Pour ces problèmes, le MIP est plus rapide et offre de meilleures garanties d'optimalité.

Quand il faut des bornes duales prouvables

Les solveurs MIP maintiennent une borne inférieure serrée tout au long de la recherche. À tout moment, vous connaissez l'écart entre votre meilleure solution et l'optimum théorique. CP-SAT calcule aussi des bornes, mais pour les problèmes avec une structure LP faible (ce qui inclut la plupart des problèmes de planification), la borne CP-SAT peut être plus lâche. Si prouver l'optimalité dans un écart serre est critique, les bornes LP du MIP sont plus fortes.

Structure linéaire à grande échelle

Si votre problème est fondamentalement un programme linéaire avec quelques variables entières (ex : "choisir quels 5 entrepôts ouvrir, puis optimiser les flux continus"), les solveurs MIP sont imbattables. Le solveur LP gère efficacement la partie continue, et le branch-and-bound explore le petit espace de recherche entier.

Licence et coût

C'est une préoccupation pratique qui compte pour une application livrée à chaque client, installée chez lui ou hébergée en ligne.

Solveur	Licence	Coût	On-premise
CP-SAT (OR-Tools)	Apache 2.0	Gratuit, pour toujours	Aucune restriction
Gurobi	Commercial	Académique gratuit, commercial à partir de 12 000+$/an	Serveur de licence requis
CPLEX	Commercial	Académique gratuit, commercial similaire à Gurobi	Serveur de licence requis
HiGHS	MIT	Gratuit	Aucune restriction (LP/MIP uniquement)
SCIP	Apache 2.0	Gratuit	Aucune restriction

Pour un système de planification livré à chaque client, installé chez lui ou hébergé en ligne, les licences ajoutent à la fois du coût et de la complexité opérationnelle. Une licence Gurobi ou CPLEX doit être provisionnée, activée et renouvelée pour chaque déploiement. Avec CP-SAT, le solveur est intégré à l'application. Pas de serveur de licence, pas d'activation, pas de renouvellement. Le coût total de possession est nettement inférieur.

L'open-source signifie aussi l'absence de dépendance fournisseur. Si Google abandonnait OR-Tools (improbable vu son utilisation répandue), la licence Apache 2.0 permet à quiconque de forker et maintenir le projet. Avec un solveur commercial, vous dépendez des décisions commerciales du fournisseur.

Notre choix : CP-SAT pour la planification du personnel

Pour notre cas d'usage, la décision était claire :

• Le problème est combinatoire. Chaque variable de décision est booléenne : l'employé e travaille le shift s le jour d, ou non. CP-SAT gère les variables booléennes nativement.
• Les contraintes sont complexes. Paires toxiques, respect des qualifications, garanties de weekend, limites de jours consécutifs : tout se traduit directement dans le langage de contraintes de CP-SAT sans linéarisation.
• L'objectif est une somme pondérée de pénalités multiples. Pénalités conditionnelles avec des priorités différentes. CP-SAT les exprime naturellement.
• L'application est livrée au client, chez lui ou en ligne. Pas de serveur de licence, pas de coût par poste, pas de dépendance fournisseur. CP-SAT est livré avec l'application.
• La performance est suffisante. Pour 300 employés, 50 types de shifts et 30 jours, CP-SAT trouve une bonne solution en moins de 5 minutes et converge vers le quasi-optimal en 15-30 minutes sur un serveur 8 coeurs.

Résumé de la comparaison

Dimension	CP-SAT	Gurobi	CPLEX
Types de variables	Booléen, entier	Continu, entier, booléen	Continu, entier, booléen
Types de contraintes	AllDifferent, Circuit, Element, Automaton, implications booléennes	Inégalités linéaires, contraintes indicateur, SOS	Inégalités linéaires, contraintes indicateur, SOS
Licence	Apache 2.0, gratuit	Commercial, 12k+$/an	Commercial, similaire
Adaptation planification	Excellente : booléen natif, propagation rapide	Bonne : linéarisation nécessaire pour certaines contraintes	Bonne : linéarisation nécessaire pour certaines contraintes
Optimisation continue	Non supportée	Excellente	Excellente
Bornes LP	Plus faibles pour la planification	Fortes	Fortes
Recherche parallèle	Workers diversifies intégrés	B&B parallèle intégré	B&B parallèle intégré
Courbe d'apprentissage	Modérée (API Python)	Modérée (API Python/C++)	Modérée (API Python/C++)
Communauté	Open-source, GitHub actif	Support commercial	Support commercial
Déploiement on-premise	Aucune restriction	Serveur de licence requis	Serveur de licence requis

Si notre problème était la minimisation de coûts avec des flux continus, ou la conception de réseaux avec une structure LP solide, nous choisirions Gurobi ou CPLEX sans hésitation. Ce sont des outils remarquables pour les problèmes pour lesquels ils ont été conçus. Mais la planification du personnel est un problème combinatoire avec des décisions booléennes, des contraintes complexes et des pénalités multi-objectifs. Pour ce problème, CP-SAT est le meilleur choix.