Le solveur CP-SAT

Qu'est-ce que CP-SAT

CP-SAT signifie Constraint Programming with Boolean Satisfiability. C'est le solveur phare de la suite Google OR-Tools, conçu pour résoudre des problèmes d'optimisation combinatoire définis sur des variables entières.

CP-SAT combine deux approches complémentaires :

• La programmation par contraintes (CP) : on déclare les règles que la solution doit respecter, et le solveur cherche les affectations valides. Le mot "programmation" désigne ici l'élaboration d'un plan, pas l'écriture de code
• La satisfaisabilité booléenne (SAT) : le problème est encodé en clauses logiques (vrai/faux). Le solveur utilise les techniques avancées des solveurs SAT (apprentissage de clauses conflictuelles, propagation unitaire, redémarrages)

Cette combinaison rend CP-SAT particulièrement efficace pour les problèmes de scheduling et d'affectation, où il faut trouver la meilleure combinaison parmi des millions de possibilités.

Comment fonctionne CP-SAT

Le solveur procède en trois phases qui s'enchaînent en boucle :

1. Affectation. Le solveur choisit une variable (par exemple : "l'agent Martin travaille-t-il le shift 6h-14h le lundi ?") et lui attribue une valeur (oui ou non).

2. Propagation. Dès qu'une variable est fixée, les contraintes propagent les conséquences sur toutes les autres variables. Si Martin travaille le lundi matin, il ne peut pas travailler le lundi après-midi (un seul shift par jour), il ne peut pas travailler le dimanche soir (repos minimum 11h), et le besoin de couverture du lundi matin est réduit d'une unité. Cette propagation élimine immédiatement des millions de combinaisons impossibles.

3. Backtracking. Si le solveur arrive dans une impasse (aucune valeur valide pour une variable), il revient en arrière à une décision précédente et essaie une autre valeur. Les techniques SAT permettent d'apprendre de ces impasses pour ne pas les répéter.

Ce cycle se répète jusqu'à trouver la solution optimale ou atteindre la limite de temps configurée.

Variables et contraintes

CP-SAT travaille exclusivement avec des entiers. Toutes les variables, contraintes et objectifs sont exprimés en nombres entiers.

Types de variables :

• Booléennes (0 ou 1) : "l'agent X est-il affecté au shift Y le jour Z ?" C'est le type principal utilisé en planification
• Entières (domaine borné) : "combien de minutes l'agent X travaille-t-il ce mois-ci ?"
• Intervalles (début, durée, fin) : utilisés pour les problèmes de scheduling avec chevauchement

Types de contraintes :

• AddExactlyOne() : exactement un shift par jour par agent
• AddAtMostOne() : au plus un agent sur un poste donné
• AddNoOverlap() : pas de chevauchement temporel sur une ressource
• OnlyEnforceIf() : contrainte conditionnelle ("si l'agent est qualifié pour cette fonction, alors il peut faire ce shift")
• Inégalités linéaires : somme des heures ≤ heures contractuelles

Contraintes dures vs contraintes souples

CP-SAT distingue deux types de contraintes :

Contraintes dures (obligatoires). Elles doivent être respectées. Si le solveur ne peut pas les satisfaire toutes, il retourne INFEASIBLE. Exemples dans Planopti :

• Un seul shift par jour par agent
• Repos minimum de 11 heures entre deux shifts
• Un agent ne peut faire que les shifts correspondant à ses qualifications
• Les vacances, jours fériés et jours fixes sont respectés

Contraintes souples (objectifs). Elles sont souhaitables mais pas obligatoires. Chaque violation a un coût (pénalité) que le solveur cherche à minimiser. Exemples dans Planopti :

• Couverture des shifts (pénalité par poste non couvert)
• Minimum 8 jours de repos par mois (pénalité par jour manquant)
• Garantir un weekend complet de repos par mois (pénalité par agent sans weekend)
• Répartition équitable des jours travaillés au sein d'un groupe
• Pas plus de 6 jours consécutifs de travail (pénalité par violation)

Fonction objectif

L'objectif du solveur est de minimiser la somme pondérée des pénalités. Chaque contrainte souple a un poids configurable qui reflète sa priorité :

• La couverture d'un poste non rempli a une pénalité élevée (10 000 par unité) car c'est critique pour les opérations
• Un weekend non garanti a une pénalité intermédiaire (5 000 par agent) car c'est important mais pas bloquant
• Un écart d'équité a une pénalité plus faible (50 par écart) car c'est un objectif de qualité

Le planificateur peut ajuster ces poids dans la configuration du solveur pour refléter les priorités de sa compagnie. Un score final bas signifie un planning de meilleure qualité.

Statuts de résolution

Après chaque exécution, CP-SAT retourne un statut clair :

• OPTIMAL : la meilleure solution possible a été trouvée et prouvée optimale. Aucune autre combinaison ne peut faire mieux
• FEASIBLE : une solution valide a été trouvée, mais le solveur n'a pas eu le temps de prouver qu'elle est optimale (limite de temps atteinte). La solution est néanmoins utilisable
• INFEASIBLE : aucune solution n'existe qui respecte toutes les contraintes dures. Cela signifie généralement que les données sont incompatibles (trop d'absences, pas assez d'agents qualifiés, besoins irréalistes)
• MODEL_INVALID : le modèle mathématique est mal formulé. Erreur de configuration

Le solveur retourne également des statistiques : nombre de conflits rencontrés, nombre de branches explorées, temps de résolution en secondes.

Déterminisme

CP-SAT est déterministe : les mêmes données d'entrée produisent systématiquement le même résultat. Ce n'est pas de l'IA générative, pas du machine learning, pas de l'heuristique approximative.

Cela signifie :

• Pas de résultat aléatoire ou imprévisible
• Résultat reproductible et vérifiable
• Pas de "boîte noire" : chaque décision du solveur est traçable
• Pas de données d'entraînement, pas de modèle statistique, pas de biais

Performance

CP-SAT a remporté la médaille d'or au concours international de programmation par contraintes (MiniZinc Challenge) chaque année depuis 2018.

Performances documentées par Google :

• 5 agents, 7 jours, 3 shifts : solution optimale en 0,003 seconde
• Problèmes industriels (centaines de variables, milliers de contraintes) : solutions en minutes avec limite de temps configurable

Dans Planopti, la génération d'un planning mensuel pour une structure de taille moyenne (100 à 150 employés, plusieurs groupes fonctionnels, dizaines de types de shifts) prend environ 2 à 5 minutes. Pour les grandes structures (200 à 300+ employés, contraintes croisées complexes), le temps de résolution peut atteindre 10 à 30 minutes selon la complexité du modèle. La limite de temps est configurable, et CP-SAT retourne toujours la meilleure solution trouvée dans le temps imparti.

CP-SAT supporte la recherche multi-thread : plusieurs stratégies de recherche tournent en parallèle pour trouver plus vite la solution optimale.

CP-SAT dans Planopti

Voici comment Planopti utilise concrètement CP-SAT pour générer un planning mensuel :

1. Construction du modèle. Planopti lit les données du dashboard (staff, qualifications, shifts, besoins, contraintes, absences) et crée un modèle CP-SAT avec :

• Une variable booléenne assign[agent, jour, shift] pour chaque combinaison possible
• Une variable booléenne is_off[agent, jour] pour les jours de repos
• Une variable entière total_minutes[agent] pour le suivi des heures

2. Ajout des contraintes. Planopti injecte les contraintes dures (qualifications, repos, vacances) et souples (couverture, équité, weekends) dans le modèle.

3. Résolution. CP-SAT cherche la meilleure affectation possible dans la limite de temps configurée (120 secondes par défaut).

4. Résultat. Planopti récupère la solution, la traduit en grille de planning et l'affiche dans le dashboard. Le planificateur peut ensuite ajuster manuellement et exporter.