Tuning CP-SAT pour le Rostering à Grande Échelle

Le défi du passage à l'échelle

Un modèle CP-SAT pour la planification du personnel croit dans trois dimensions simultanément : plus d'employés, plus de types de shifts, plus de jours. Un modèle pour 100 employés avec 40 shifts sur 30 jours contient environ 80 000 variables booléennes. Doublez les employés et vous faites plus que doubler la taille du modèle, car les contraintes inter-employés (équité, couverture) croissent de façon quadratique.

À 100 employés, CP-SAT résout typiquement le problème en moins de 3 minutes. À 200 employés, une configuration naïve peut prendre plus de 30 minutes ou dépasser la limite de temps. La différence entre un solveur bien configuré et un solveur mal configuré est souvent la différence entre un système utilisable et un système qui frustre les planificateurs.

Cet article couvre les leviers pratiques disponibles : limites de temps, parallélisme, réduction du modèle, brisure de symétrie et propagation. Chaque technique est indépendante 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 être utile. À tout moment pendant la recherche, il conserve la meilleure solution faisable trouvée jusque-là. Si vous l'arrêtez tôt, 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'arrête et retourne la meilleure solution trouvée avec la valeur de l'objectif et l'écart d'optimalité (la distance entre la meilleure solution et la borne inférieure prouvée).

Cette propriété anytime change la façon de penser le tuning. La question n'est pas "est-ce qu'il va résoudre ?" mais "quelle sera la qualité de la solution dans mon budget de temps ?" Pour la plupart des problèmes de rostering, le solveur trouve une bonne solution dans les premiers 10-20% du temps alloue, puis passe le reste à faire des améliorations incrémentales.

Choisir une limite de temps

La bonne limite de temps dépend de la taille du problème et du workflow du planificateur. Un planning mensuel est généré une fois par mois, donc même 30 minutes est acceptable. Une re-résolution interactive après 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 parallélisme de CP-SAT n'est pas du parallélisme de données. Il ne découpe pas le problème en sous-problèmes indépendants. À la place, il exécute plusieurs stratégies de recherche simultanément sur le modèle complet. Chaque thread worker explore l'arbre de recherche avec une heuristique différente : l'un peut prioriser les variables de couverture, un autre se concentrer sur l'équité, un troisième utiliser des redémarrages aléatoires.

Tous les workers partagent un pool global de solutions. Quand un worker trouve une meilleure solution, les autres sont immédiatement notifiés et peuvent l'utiliser pour élaguer leur propre recherche. Cette architecture signifie qu'ajouter des workers ne divise pas simplement le temps par N. L'accélération vient de la diversité des stratégies : des heuristiques différentes trouvent des parties différentes de l'espace de solutions, et les meilleures découvertes sont partagées.

Configurer num_workers

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

La valeur par défaut est typiquement le nombre de coeurs CPU disponibles, mais il vaut la peine de la définir explicitement. Sur une machine avec 8 coeurs physiques, num_workers = 8 est le point optimal. Aller au-delà 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 véritablement en parallèle.

Pourquoi plus de workers aide

Avec 1 worker, le solveur utilise une seule stratégie de recherche. Si cette stratégie se retrouve bloquée dans une région improductive de l'espace de recherche, il n'y a pas de recours sauf les redémarrages aléatoires. Avec 8 workers exécutant 8 stratégies différentes, la probabilité que tous les workers soient bloques simultanément est beaucoup plus faible. En pratique, le solveur avec 8 workers trouve une solution de même qualité 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 stratégie l'a trouvée, la valeur de l'objectif et l'écart d'optimalité actuel. C'est indispensable pour comprendre quels workers contribuent et si le solveur progresse encore.

Réduction de l'espace de variables

La technique de modélisation la plus impactante est de ne pas créer de variables pour les affectations impossibles. Chaque variable assign[e, d, s] que le solveur ne peut jamais mettre à 1 est de la mémoire gaspillée et de l'effort de recherche gaspille.

Filtrage par qualification

Si l'employé e ne détient pas la qualification pour le shift s, ne créez pas assign[e, d, s] du tout. Avec 300 employés et 50 shifts, chaque employé est typiquement qualifié pour 15-25 shifts. Cela seul élimine 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'employé e à une absence pré-assignée (congé, vacances, jour de repos fixe) le jour d, ne créez 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 employé par mois, cela élimine encore 15-20% des variables restantes.

Impact combiné

Le filtrage par qualification plus le filtrage par absence réduit typiquement le modèle de 30-50% par rapport à l'approche naïve. Pour un problème à 300 employés, cela signifie passer de ~450 000 variables booléennes à ~225 000-315 000. Le nombre de contraintes diminue proportionnellement, et la propagation du solveur devient significativement plus rapide.

Brisure de symétrie

La symétrie est l'un des tueurs de performance les plus subtils dans les modèles de planification. Deux employés avec des qualifications identiques, des types de contrat identiques, des contraintes identiques et aucune absence pré-assignée sont interchangeables. Le solveur ne le sait pas. Il va explorer à 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 différentes, même si elles sont fonctionnellement équivalentes.

Pour un groupe de K employés interchangeables, il y a K! affectations équivalentes. Avec 5 employés interchangeables, cela fait 120 permutations équivalentes que le solveur perd du temps à explorer.

Contraintes d'ordonnancement

La technique de brisure de symétrie la plus simple est d'imposer un ordre arbitraire. Si les employés e1 et e2 sont interchangeables, exiger que le total de shifts de e1 soit au moins égal à 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 qualité de la solution. Cela élimine simplement la moitié des permutations équivalentes, dirigeant le solveur vers l'exploration de l'ordonnancement "canonique" uniquement.

Identifier les employés interchangeables

Deux employés sont interchangeables s'ils partagent le même ensemble de qualifications, le même type de contrat, la même appartenance à un groupe, et qu'aucun n'a d'absences pré-assignées ou de contraintes individuelles. En pratique, les paires véritablement interchangeables sont peu fréquentes dans les données réelles de planification (3-8 par modèle), mais même quelques contraintes de brisure de symétrie peuvent réduire de façon mesurable le temps de résolution.

Conseils de propagation

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

Pré-calculer les paires toxiques

La contrainte de repos de 11 heures entre jours consécutifs peut être encodée comme de l'arithmétique temporelle ou comme des implications booléennes. 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 booléenne déclenche une propagation plus forte. Quand assign[e, d, s1] = 1, le solveur déduit immédiatement assign[e, d+1, s2] = 0 pour tous les partenaires toxiques. La version arithmétique temporelle nécessite la relaxation linéaire pour découvrir cela, ce qui est plus lent.

Utiliser des implications au lieu de big-M

Les contraintes big-M (utilisant une grande constante pour linéariser la logique conditionnelle) sont un pattern courant venant de la modélisation MIP. CP-SAT les gère, mais elles affaiblissent la relaxation linéaire 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 pénalité directes donnent à CP-SAT des bornes plus serrées, ce qui signifie un meilleur élagage et une convergence plus rapide vers les solutions optimales.

Exploiter AddBoolOr et AddBoolAnd

Pour exprimer des relations logiques entre variables booléennes, utilisez les opérations booléennes natives de CP-SAT plutôt que l'arithmétique linéaire. AddBoolOr et AddBoolAnd déclenchent des propagateurs spécialisés qui sont significativement plus rapides que leurs équivalents linéaires.

# 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 modèle de rostering réel (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 trouvée dans une fenêtre de 30 minutes.

Employés	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 clés :

• Passer de 1 à 4 workers donne l'accélération la plus importante (2-3x). C'est parce que 4 stratégies diverses sont bien meilleures qu'une seule.
• Passer de 4 à 8 workers ajoute encore 1,5-2x. La diversité marginale des stratégies reste précieuse.
• Passer de 8 à 16 workers sur une machine à 8 coeurs ne donne que 10-15% d'amélioration. Les workers commencent à se partager le temps CPU au lieu de tourner réellement en parallèle.
• À 300 employés avec 1 worker, le solveur dépasse la limite de 30 minutes sans trouver de bonne solution. Avec 8 workers, il converge en 15 minutes.

Impact de la réduction de variables

Les benchmarks ci-dessus utilisent le filtrage par qualification et par absence. Sans ces optimisations, le cas à 200 employés avec 8 workers prend 14-18 minutes au lieu de 8. Le cas à 300 employés prend 22-28 minutes au lieu de 15. La réduction de variables n'est pas optionnelle à grande échelle.

Recommandations de configuration

num_workers

Réglez num_workers au nombre de coeurs CPU physiques de votre machine. Sur une VM cloud, c'est généralement 4 ou 8. Sur un serveur dédié, cela peut être 16 ou 32. Ne dépassez pas le nombre de coeurs physiques.

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

Limite de temps

Adaptez la limite de temps à la taille du problème et au cas d'usage :

Employés	Génération mensuelle	Re-résolution interactive
< 150	5 minutes	2 minutes
150-200	15 minutes	5 minutes
200-300+	30 minutes	10 minutes

Pour la génération mensuelle, la qualité compte plus que la vitesse. Pour les re-résolutions interactives (après une modification manuelle), la réactivité compte plus que les derniers 2% d'optimalité.

Logging

solver.parameters.log_search_progress = True

Activez toujours le logging de recherche pendant le développement. Il montre l'amélioration de l'objectif au fil du temps, quels workers trouvent des solutions, et l'écart d'optimalité. Désactivez-le en production si le volume de logs est une préoccupation.

Checklist au niveau du modèle

• Ne pas créer assign[e, d, s] pour les paires employé-shift non qualifiées
• Ne pas créer de variables d'affectation pour les jours d'absence des employés
• Pré-calculer les paires toxiques pour les contraintes de repos
• Ajouter des contraintes de brisure de symétrie pour les employés interchangeables
• Utiliser des implications booléennes au lieu de big-M quand c'est possible
• Exclure les employés absents des calculs d'équité

Quand arrêter le tuning

Si le solveur atteint un écart d'optimalité inférieur à 5% dans votre budget de temps, un tuning supplémentaire donnera des gains décroissants. Concentrez-vous plutôt sur la structure des pénalités : une fonction objectif bien calibrée compte plus qu'une résolution 10% plus rapide. Le travail du solveur est de trouver le meilleur planning dans les règles que vous définissez. Assurez-vous que les règles sont correctes avant d'optimiser la recherche.