Pourquoi nous avons choisi CP-SAT plutot que MIP

Deux paradigmes pour resoudre les problemes difficiles

Quand il faut resoudre un probleme d'optimisation a grande echelle, deux familles de solveurs dominent le paysage : la programmation lineaire en nombres entiers (MIP, Mixed-Integer Programming) et la programmation par contraintes (CP, Constraint Programming). Les deux peuvent resoudre des problemes de planification du personnel. Les deux gerent des centaines d'employes et des milliers de variables. Mais ils abordent le probleme sous des angles fondamentalement differents, et le choix a des consequences.

Les solveurs MIP comme Gurobi et CPLEX viennent de la tradition de la recherche operationnelle. Ils modelisent les problemes comme des systemes d'inegalites lineaires et utilisent la relaxation lineaire combinee 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 generation 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, ou chaque approche excelle, et ou MIP serait le meilleur outil.

MIP : programmation lineaire en nombres entiers

Un solveur MIP fonctionne en relaxant les variables entieres en valeurs continues, en resolvant le programme lineaire (LP) resultant, puis en utilisant le branch-and-bound pour retrouver des solutions entieres. La relaxation LP fournit une borne inferieure sur l'objectif, que le solveur utilise pour elaguer l'arbre de recherche.

Points forts du MIP :

• Les variables continues sont natives. Si votre probleme implique des quantites fractionnaires (allocation de couts, flux de ressources, melange), le MIP les gere directement. Pas de discretisation necessaire.
• Bornes LP serrees. Pour les problemes avec des relaxations LP "serrees" (transport, flot a cout minimum, localisation d'installations), l'ecart entre la borne LP et l'optimum entier est faible. Le solveur peut prouver l'optimalite rapidement.
• Solveurs commerciaux matures. Gurobi et CPLEX ont des decennies d'ingenierie derriere eux. Ils incluent le presolve, les coupes, les heuristiques et la recherche parallele. Pour les problemes LP/MIP bien structures, ils sont extremement rapides.
• Bornes duales. Les solveurs MIP fournissent une borne inferieure prouvable a chaque instant de la recherche. Vous savez toujours a quelle distance votre solution courante se trouve de l'optimum theorique.

La formulation MIP canonique pour la planification utilise des variables entieres 0/1 : x[e,d,s] = 1 si l'employe e travaille le shift s le jour d. Les contraintes sont ecrites sous forme d'inegalites lineaires. L'objectif est une fonction lineaire des variables de decision. Cela fonctionne, mais la planification introduit une structure pour laquelle le MIP n'a pas ete initialement concu.

CP-SAT : programmation par contraintes avec SAT

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

• Propagation de contraintes. Quand une variable est affectee ou qu'un domaine est reduit, le solveur propage immediatement les consequences a travers toutes les contraintes connectees. Cela elimine les valeurs impossibles avant meme que la recherche ne les considere.
• Resolution SAT. Le solveur encode le probleme comme un probleme de satisfaisabilite booleenne et utilise des techniques SAT modernes : apprentissage de clauses par conflit (CDCL), redemarrages et selection de variables par activite.
• Generation de clauses paresseuses (LCG). Quand le solveur rencontre un conflit, il genere une clause qui explique le conflit et l'ajoute a la base de clauses. Cela empeche le solveur de revisiter la meme impasse.

Points forts de CP-SAT :

• Les variables booleennes sont des citoyens de premiere classe. La variable assign[e,d,s] est naturellement booleenne. Pas besoin de la modeliser comme une variable continue relaxee a [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 specialises.
• Penalites non lineaires. Les objectifs peuvent inclure des expressions min/max, des valeurs absolues et des penalites conditionnelles sans astuces de linearisation.
• Recherche parallele diversifiee. CP-SAT execute simultanement plusieurs strategies de recherche (workers), chacune avec des heuristiques differentes de selection de variables et de valeurs. Cela fournit une diversification implicite sans reglage manuel.

La planification est fondamentalement combinatoire

La decision centrale en planification du personnel est : "L'employe 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 ou un employe travaille 0,6 d'un shift. Le probleme est inheremment discret et combinatoire.

En MIP, on modelise cela comme une variable entiere 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 a brancher sur ces valeurs fractionnaires pour retrouver des solutions entieres. Pour les problemes de planification avec beaucoup de symetries (employes avec des qualifications identiques), la relaxation LP peut etre faible, ce qui signifie que la borne est lache et l'arbre de branch-and-bound est grand.

En CP-SAT, assign[e,d,s] est une variable booleenne des le depart. Le solveur ne considere jamais d'affectations fractionnaires. Quand il decide que l'employe e travaille le jour d, la propagation de contraintes elimine immediatement les shifts conflictuels. Cette gestion native des decisions booleennes est un avantage structurel pour la planification.

Ou CP-SAT excelle pour la planification

Paires toxiques (repos minimum entre shifts)

La reglementation du travail impose 11 heures de repos entre la fin d'un shift et le debut du suivant. Nous pre-calculons les "paires toxiques" : les combinaisons de shifts qui violeraient cette regle.

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

En CP-SAT, c'est une implication booleenne native. Quand assign[e,d,s1] est fixe a 1, le solveur propage immediatement assign[e,d+1,s2] = 0. Pas de branchement necessaire. En MIP, la meme contrainte est ecrite de maniere identique, mais la relaxation LP autorise les deux variables a valoir 0.5, ne fournissant aucun elagage utile tant que le solveur ne branche pas sur l'une d'elles.

Respect des qualifications

Si un employe n'est pas qualifie pour un shift, nous ne creons simplement pas la variable assign pour cette combinaison. En CP-SAT, c'est naturel : la variable n'existe pas, donc le solveur ne la considere jamais. En MIP, on fixe la variable a 0 (en ajoutant des contraintes explicites) ou on l'omet de la formulation (ce que les solveurs MIP peuvent aussi faire, mais le benefice de propagation en CP est plus fort car il se propage en cascade a travers les contraintes connectees).

Multi-objectif avec penalites ponderees

Notre fonction objectif est une somme ponderee de termes de penalite souples : couverture manquante (10 000 par poste), jours de repos manquants (1 500 par jour), pas de weekend garanti (5 000), violation jours consecutifs (2 000), jours de repos isoles (1 000), ecarts d'equite par qualification (500), ecarts d'equite de charge.

Chaque penalite implique une logique conditionnelle : "si la couverture le jour d est inferieure a la cible, penaliser le manque." En CP-SAT, cela s'exprime directement avec max(0, cible - affectes) sans linearisation. En MIP, il faut des variables auxiliaires et des contraintes big-M pour modeliser la structure conditionnelle, ce qui peut affaiblir la relaxation LP.

Gestion des symetries

Quand plusieurs employes ont les memes qualifications et le meme type de contrat, echanger leurs plannings produit une solution equivalente. Cette symetrie cree de vastes plateaux dans l'espace de recherche ou le solveur ne progresse pas. La recherche parallele diversifiee de CP-SAT, avec des workers utilisant differentes heuristiques et strategies de redemarrage, gere la symetrie plus efficacement que le branch-and-bound du MIP, qui peut rester bloque a explorer des branches equivalentes.

Ou MIP est le meilleur choix

Optimisation continue

Si votre probleme implique la minimisation d'une fonction de cout avec allocation fractionnaire de ressources, le MIP est le choix naturel. Problemes de melange, optimisation de portefeuille, planification de chaine logistique avec flux continus : c'est le territoire du MIP. CP-SAT travaille avec des entiers et des booleens. Si vous avez besoin de x = 3.7, il faudrait mettre a l'echelle et discretiser.

Problemes avec relaxation LP serree

Transport, flot a cout minimum, conception de reseau, localisation d'installations : ces problemes ont des relaxations LP serrees. 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 problemes, le MIP est plus rapide et offre de meilleures garanties d'optimalite.

Quand il faut des bornes duales prouvables

Les solveurs MIP maintiennent une borne inferieure serree tout au long de la recherche. A tout moment, vous connaissez l'ecart entre votre meilleure solution et l'optimum theorique. CP-SAT calcule aussi des bornes, mais pour les problemes avec une structure LP faible (ce qui inclut la plupart des problemes de planification), la borne CP-SAT peut etre plus lache. Si prouver l'optimalite dans un ecart serre est critique, les bornes LP du MIP sont plus fortes.

Structure lineaire a grande echelle

Si votre probleme est fondamentalement un programme lineaire avec quelques variables entieres (ex : "choisir quels 5 entrepots ouvrir, puis optimiser les flux continus"), les solveurs MIP sont imbattables. Le solveur LP gere efficacement la partie continue, et le branch-and-bound explore le petit espace de recherche entier.

Licence et cout

C'est une preoccupation pratique qui compte pour le deploiement on-premise.

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

Pour un systeme de planification on-premise deploye chez les clients, les licences ajoutent a la fois du cout et de la complexite operationnelle. Une licence Gurobi ou CPLEX doit etre provisionnee, activee et renouvelee pour chaque deploiement. Avec CP-SAT, le solveur est integre a l'application. Pas de serveur de licence, pas d'activation, pas de renouvellement. Le cout total de possession est nettement inferieur.

L'open-source signifie aussi l'absence de dependance fournisseur. Si Google abandonnait OR-Tools (improbable vu son utilisation repandue), la licence Apache 2.0 permet a quiconque de forker et maintenir le projet. Avec un solveur commercial, vous dependez des decisions commerciales du fournisseur.

Notre choix : CP-SAT pour la planification du personnel

Pour notre cas d'usage, la decision etait claire :

• Le probleme est combinatoire. Chaque variable de decision est booleenne : l'employe e travaille le shift s le jour d, ou non. CP-SAT gere les variables booleennes nativement.
• Les contraintes sont complexes. Paires toxiques, respect des qualifications, garanties de weekend, limites de jours consecutifs : tout se traduit directement dans le langage de contraintes de CP-SAT sans linearisation.
• L'objectif est une somme ponderee de penalites multiples. Penalites conditionnelles avec des priorites differentes. CP-SAT les exprime naturellement.
• Le deploiement est on-premise. Pas de serveur de licence, pas de cout par poste, pas de dependance fournisseur. CP-SAT est livre avec l'application.
• La performance est suffisante. Pour 300 employes, 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.

Resume de la comparaison

Dimension	CP-SAT	Gurobi	CPLEX
Types de variables	Booleen, entier	Continu, entier, booleen	Continu, entier, booleen
Types de contraintes	AllDifferent, Circuit, Element, Automaton, implications booleennes	Inegalites lineaires, contraintes indicateur, SOS	Inegalites lineaires, contraintes indicateur, SOS
Licence	Apache 2.0, gratuit	Commercial, 12k+$/an	Commercial, similaire
Adaptation planification	Excellente : booleen natif, propagation rapide	Bonne : linearisation necessaire pour certaines contraintes	Bonne : linearisation necessaire pour certaines contraintes
Optimisation continue	Non supportee	Excellente	Excellente
Bornes LP	Plus faibles pour la planification	Fortes	Fortes
Recherche parallele	Workers diversifies integres	B&B parallele integre	B&B parallele integre
Courbe d'apprentissage	Moderee (API Python)	Moderee (API Python/C++)	Moderee (API Python/C++)
Communaute	Open-source, GitHub actif	Support commercial	Support commercial
Deploiement on-premise	Aucune restriction	Serveur de licence requis	Serveur de licence requis

Si notre probleme etait la minimisation de couts avec des flux continus, ou la conception de reseaux avec une structure LP solide, nous choisirions Gurobi ou CPLEX sans hesitation. Ce sont des outils remarquables pour les problemes pour lesquels ils ont ete concus. Mais la planification du personnel est un probleme combinatoire avec des decisions booleennes, des contraintes complexes et des penalites multi-objectifs. Pour ce probleme, CP-SAT est le meilleur choix.