Tuning CP-SAT pour le Rostering a Grande Echelle

Le defi du passage a l'echelle

Un modele CP-SAT pour la planification du personnel croit dans trois dimensions simultanement : plus d'employes, plus de types de shifts, plus de jours. Un modele pour 100 employes avec 40 shifts sur 30 jours contient environ 80 000 variables booleennes. Doublez les employes et vous faites plus que doubler la taille du modele, car les contraintes inter-employes (equite, couverture) croissent de facon quadratique.

A 100 employes, CP-SAT resout typiquement le probleme en moins de 3 minutes. A 200 employes, une configuration naive peut prendre plus de 30 minutes ou depasser la limite de temps. La difference entre un solveur bien configure et un solveur mal configure est souvent la difference entre un systeme utilisable et un systeme qui frustre les planificateurs.

Cet article couvre les leviers pratiques disponibles : limites de temps, parallelisme, reduction du modele, brisure de symetrie et propagation. Chaque technique est independante et leurs effets se cumulent.

Limites de temps et comportement anytime

CP-SAT est un solveur anytime. Il n'a pas besoin de terminer pour etre utile. A tout moment pendant la recherche, il conserve la meilleure solution faisable trouvee jusque-la. Si vous l'arretez tot, vous obtenez cette solution. Si vous lui donnez plus de temps, il peut en trouver une meilleure.

La limite de temps se configure via :

solver.parameters.max_time_in_seconds = 300  # 5 minutes

Quand la limite est atteinte, le solveur s'arrete et retourne la meilleure solution trouvee avec la valeur de l'objectif et l'ecart d'optimalite (la distance entre la meilleure solution et la borne inferieure prouvee).

Cette propriete anytime change la facon de penser le tuning. La question n'est pas "est-ce qu'il va resoudre ?" mais "quelle sera la qualite de la solution dans mon budget de temps ?" Pour la plupart des problemes de rostering, le solveur trouve une bonne solution dans les premiers 10-20% du temps alloue, puis passe le reste a faire des ameliorations incrementales.

Choisir une limite de temps

La bonne limite de temps depend de la taille du probleme et du workflow du planificateur. Un planning mensuel est genere une fois par mois, donc meme 30 minutes est acceptable. Une re-resolution interactive apres une modification manuelle devrait se terminer en moins de 2 minutes.

# Recommandations pratiques :
# 100-150 employes :  max_time = 300   (5 min)
# 150-200 employes :  max_time = 900   (15 min)
# 200-300+ employes : max_time = 1800  (30 min)

Recherche multi-thread

Le parallelisme de CP-SAT n'est pas du parallelisme de donnees. Il ne decoupe pas le probleme en sous-problemes independants. A la place, il execute plusieurs strategies de recherche simultanement sur le modele complet. Chaque thread worker explore l'arbre de recherche avec une heuristique differente : l'un peut prioriser les variables de couverture, un autre se concentrer sur l'equite, un troisieme utiliser des redemarrages aleatoires.

Tous les workers partagent un pool global de solutions. Quand un worker trouve une meilleure solution, les autres sont immediatement notifies et peuvent l'utiliser pour elaguer leur propre recherche. Cette architecture signifie qu'ajouter des workers ne divise pas simplement le temps par N. L'acceleration vient de la diversite des strategies : des heuristiques differentes trouvent des parties differentes de l'espace de solutions, et les meilleures decouvertes sont partagees.

Configurer num_workers

solver.parameters.num_workers = 8  # Correspondre au nombre de coeurs CPU

La valeur par defaut est typiquement le nombre de coeurs CPU disponibles, mais il vaut la peine de la definir explicitement. Sur une machine avec 8 coeurs physiques, num_workers = 8 est le point optimal. Aller au-dela du nombre de coeurs physiques (ex : 16 workers sur 8 coeurs) donne des gains marginaux car les workers se disputent le temps CPU au lieu de tourner veritablement en parallele.

Pourquoi plus de workers aide

Avec 1 worker, le solveur utilise une seule strategie de recherche. Si cette strategie se retrouve bloquee dans une region improductive de l'espace de recherche, il n'y a pas de recours sauf les redemarrages aleatoires. Avec 8 workers executant 8 strategies differentes, la probabilite que tous les workers soient bloques simultanement est beaucoup plus faible. En pratique, le solveur avec 8 workers trouve une solution de meme qualite en 3-5x moins de temps qu'avec 1 worker.

Surveiller la progression de la recherche

solver.parameters.log_search_progress = True

Cela affiche une ligne chaque fois qu'un worker trouve une nouvelle meilleure solution, montrant quelle strategie l'a trouvee, la valeur de l'objectif et l'ecart d'optimalite actuel. C'est indispensable pour comprendre quels workers contribuent et si le solveur progresse encore.

Reduction de l'espace de variables

La technique de modelisation la plus impactante est de ne pas creer de variables pour les affectations impossibles. Chaque variable assign[e, d, s] que le solveur ne peut jamais mettre a 1 est de la memoire gaspillee et de l'effort de recherche gaspille.

Filtrage par qualification

Si l'employe e ne detient pas la qualification pour le shift s, ne creez pas assign[e, d, s] du tout. Avec 300 employes et 50 shifts, chaque employe est typiquement qualifie pour 15-25 shifts. Cela seul elimine 50-70% des variables potentielles.

# Au lieu de :
for e in employees:
    for d in days:
        for s in shifts:
            assign[e, d, s] = model.NewBoolVar(...)

# Faire :
for e in employees:
    for d in days:
        for s in qualified_shifts[e]:
            assign[e, d, s] = model.NewBoolVar(...)

Filtrage par absence

Si l'employe e a une absence pre-assignee (conge, vacances, jour de repos fixe) le jour d, ne creez aucune variable assign[e, d, s] pour ce jour. Fixez directement is_off[e, d] = 1.

# Pour chaque absence :
if employee_absent(e, d):
    model.Add(is_off[e, d] == 1)
    # Ne pas creer assign[e, d, *] du tout

Avec en moyenne 4-6 jours d'absence par employe par mois, cela elimine encore 15-20% des variables restantes.

Impact combine

Le filtrage par qualification plus le filtrage par absence reduit typiquement le modele de 30-50% par rapport a l'approche naive. Pour un probleme a 300 employes, cela signifie passer de ~450 000 variables booleennes a ~225 000-315 000. Le nombre de contraintes diminue proportionnellement, et la propagation du solveur devient significativement plus rapide.

Brisure de symetrie

La symetrie est l'un des tueurs de performance les plus subtils dans les modeles de planification. Deux employes avec des qualifications identiques, des types de contrat identiques, des contraintes identiques et aucune absence pre-assignee sont interchangeables. Le solveur ne le sait pas. Il va explorer a la fois "Alice prend le shift A lundi, Bob prend le shift B" et "Bob prend le shift A lundi, Alice prend le shift B" comme des solutions differentes, meme si elles sont fonctionnellement equivalentes.

Pour un groupe de K employes interchangeables, il y a K! affectations equivalentes. Avec 5 employes interchangeables, cela fait 120 permutations equivalentes que le solveur perd du temps a explorer.

Contraintes d'ordonnancement

La technique de brisure de symetrie la plus simple est d'imposer un ordre arbitraire. Si les employes e1 et e2 sont interchangeables, exiger que le total de shifts de e1 soit au moins egal a celui de e2.

# Pour les employes interchangeables e1, e2 (e1 < e2) :
# total shifts de e1 >= total shifts de e2
model.Add(total_shifts[e1] >= total_shifts[e2])

Cela ne change pas la qualite de la solution. Cela elimine simplement la moitie des permutations equivalentes, dirigeant le solveur vers l'exploration de l'ordonnancement "canonique" uniquement.

Identifier les employes interchangeables

Deux employes sont interchangeables s'ils partagent le meme ensemble de qualifications, le meme type de contrat, la meme appartenance a un groupe, et qu'aucun n'a d'absences pre-assignees ou de contraintes individuelles. En pratique, les paires veritablement interchangeables sont peu frequentes dans les donnees reelles de planification (3-8 par modele), mais meme quelques contraintes de brisure de symetrie peuvent reduire de facon mesurable le temps de resolution.

Conseils de propagation

La force principale de CP-SAT est la propagation de contraintes : deduire des affectations de variables a partir des contraintes existantes sans chercher. Plus le propagateur peut extraire d'informations, plus l'arbre de recherche se reduit.

Pre-calculer les paires toxiques

La contrainte de repos de 11 heures entre jours consecutifs peut etre encodee comme de l'arithmetique temporelle ou comme des implications booleennes. La forme par implication est nettement plus efficace.

# Lent : arithmetique temporelle dans le modele
model.Add(end_time[s1] + 660 <= start_time[s2])
    .OnlyEnforceIf(assign[e, d, s1], assign[e, d+1, s2])

# Rapide : implication booleenne pre-calculee
# Pre-calculer une fois : toxic_pairs = [(s1, s2) ou end(s1) + 660 > start(s2)]
for (s1, s2) in toxic_pairs:
    model.Add(assign[e, d, s1] + assign[e, d+1, s2] <= 1)

La forme booleenne declenche une propagation plus forte. Quand assign[e, d, s1] = 1, le solveur deduit immediatement assign[e, d+1, s2] = 0 pour tous les partenaires toxiques. La version arithmetique temporelle necessite la relaxation lineaire pour decouvrir cela, ce qui est plus lent.

Utiliser des implications au lieu de big-M

Les contraintes big-M (utilisant une grande constante pour lineariser la logique conditionnelle) sont un pattern courant venant de la modelisation MIP. CP-SAT les gere, mais elles affaiblissent la relaxation lineaire et produisent de mauvaises bornes.

# Eviter big-M :
model.Add(coverage[f, d] >= need[f, d] - M * slack[f, d])

# Preferer les variables de penalite directes :
model.Add(coverage[f, d] + missing[f, d] >= need[f, d])
model.Add(missing[f, d] >= 0)

Les variables de penalite directes donnent a CP-SAT des bornes plus serrees, ce qui signifie un meilleur elagage et une convergence plus rapide vers les solutions optimales.

Exploiter AddBoolOr et AddBoolAnd

Pour exprimer des relations logiques entre variables booleennes, utilisez les operations booleennes natives de CP-SAT plutot que l'arithmetique lineaire. AddBoolOr et AddBoolAnd declenchent des propagateurs specialises qui sont significativement plus rapides que leurs equivalents lineaires.

# Au lieu de : assign[e, d, s1] + assign[e, d, s2] >= 1
model.AddBoolOr([assign[e, d, s1], assign[e, d, s2]])

Benchmarks

Mesures sur un serveur standard (8 coeurs, 16 Go RAM) avec un modele de rostering reel (40-50 types de shifts, 30 jours, plusieurs groupes fonctionnels, ensemble complet de contraintes). Le temps indique est le temps pour atteindre la meilleure solution trouvee dans une fenetre de 30 minutes.

Employes	1 worker	4 workers	8 workers	16 workers
100	8 min	3 min	2 min	1,8 min
150	15 min	6 min	4 min	3,5 min
200	30+ min	12 min	8 min	7 min
300	timeout	25 min	15 min	12 min

Observations cles :

• Passer de 1 a 4 workers donne l'acceleration la plus importante (2-3x). C'est parce que 4 strategies diverses sont bien meilleures qu'une seule.
• Passer de 4 a 8 workers ajoute encore 1,5-2x. La diversite marginale des strategies reste precieuse.
• Passer de 8 a 16 workers sur une machine a 8 coeurs ne donne que 10-15% d'amelioration. Les workers commencent a se partager le temps CPU au lieu de tourner reellement en parallele.
• A 300 employes avec 1 worker, le solveur depasse la limite de 30 minutes sans trouver de bonne solution. Avec 8 workers, il converge en 15 minutes.

Impact de la reduction de variables

Les benchmarks ci-dessus utilisent le filtrage par qualification et par absence. Sans ces optimisations, le cas a 200 employes avec 8 workers prend 14-18 minutes au lieu de 8. Le cas a 300 employes prend 22-28 minutes au lieu de 15. La reduction de variables n'est pas optionnelle a grande echelle.

Recommandations de configuration

num_workers

Reglez num_workers au nombre de coeurs CPU physiques de votre machine. Sur une VM cloud, c'est generalement 4 ou 8. Sur un serveur dedie, cela peut etre 16 ou 32. Ne depassez pas le nombre de coeurs physiques.

import os
solver.parameters.num_workers = os.cpu_count()

Limite de temps

Adaptez la limite de temps a la taille du probleme et au cas d'usage :

Employes	Generation mensuelle	Re-resolution interactive
< 150	5 minutes	2 minutes
150-200	15 minutes	5 minutes
200-300+	30 minutes	10 minutes

Pour la generation mensuelle, la qualite compte plus que la vitesse. Pour les re-resolutions interactives (apres une modification manuelle), la reactivite compte plus que les derniers 2% d'optimalite.

Logging

solver.parameters.log_search_progress = True

Activez toujours le logging de recherche pendant le developpement. Il montre l'amelioration de l'objectif au fil du temps, quels workers trouvent des solutions, et l'ecart d'optimalite. Desactivez-le en production si le volume de logs est une preoccupation.

Checklist au niveau du modele

• Ne pas creer assign[e, d, s] pour les paires employe-shift non qualifiees
• Ne pas creer de variables d'affectation pour les jours d'absence des employes
• Pre-calculer les paires toxiques pour les contraintes de repos
• Ajouter des contraintes de brisure de symetrie pour les employes interchangeables
• Utiliser des implications booleennes au lieu de big-M quand c'est possible
• Exclure les employes absents des calculs d'equite

Quand arreter le tuning

Si le solveur atteint un ecart d'optimalite inferieur a 5% dans votre budget de temps, un tuning supplementaire donnera des gains decroissants. Concentrez-vous plutot sur la structure des penalites : une fonction objectif bien calibree compte plus qu'une resolution 10% plus rapide. Le travail du solveur est de trouver le meilleur planning dans les regles que vous definissez. Assurez-vous que les regles sont correctes avant d'optimiser la recherche.