Recherche Multi-Thread dans CP-SAT

Pas du parallelisme de donnees

Une idee recue courante : quand vous configurez num_workers = 8 dans CP-SAT, le solveur ne decoupe PAS votre probleme de planification en 8 morceaux. Il n'assigne pas les employes 1-37 au worker 1 et les employes 38-75 au worker 2. Ce serait du parallelisme de donnees, et cela ne fonctionne pas pour la programmation par contraintes.

A la place, CP-SAT utilise du parallelisme de portfolio. Chaque worker execute une strategie de recherche differente sur le probleme complet. Les 8 workers voient chaque employe, chaque shift, chaque contrainte. Ce qui differe, c'est la maniere dont ils explorent l'espace des solutions. Ils partagent leurs meilleures solutions et bornes en temps reel, de sorte que chaque decouverte d'un worker beneficie a tous les autres.

Cette distinction est importante car elle explique pourquoi ajouter des workers ameliore la qualite des solutions, pas seulement la vitesse. Plus de workers signifie plus de strategies de recherche diverses executees simultanement, ce qui augmente les chances de trouver de meilleures solutions.

Strategies de recherche

CP-SAT execute plusieurs strategies de recherche simultanement, chacune adaptee a differents aspects du probleme :

Recherche par defaut (branch-and-bound)

L'approche classique. Choisir une variable, essayer une valeur, propager les contraintes, revenir en arriere si ca echoue. CP-SAT utilise la reduction de domaine pour elaguer les valeurs impossibles avant de brancher. Cette strategie est methodique et exhaustive mais peut etre lente sur les grands problemes.

Large Neighborhood Search (LNS)

Partir de la meilleure solution courante, detruire un sous-ensemble aleatoire d'affectations (par exemple desaffecter 20% des paires employe-jour), puis reparer la partie detruite en gardant le reste fixe. Le LNS est excellent pour ameliorer incrementalement de bonnes solutions. C'est souvent lui qui trouve la meilleure solution finale dans les problemes de planification.

Relaxation lineaire

Relacher les variables booleennes en valeurs continues (autoriser 0.5 au lieu de seulement 0 ou 1), puis resoudre le programme lineaire resultant. La solution LP fournit une borne inferieure sur l'objectif. Cette borne indique a tous les autres workers : "aucune solution ne peut scorer en dessous de cette valeur", ce qui elague leurs arbres de recherche.

Recherche basee sur les cores

Trouver des cores insatisfaisables minimaux : de petits sous-ensembles de contraintes souples qui ne peuvent pas tous etre satisfaits simultanement. Cette strategie identifie quels compromis sont inevitables, aidant le solveur a se concentrer sur des ameliorations realistes plutot que de poursuivre des objectifs impossibles.

Recherche fixe

Suivre un ordre fixe de variables, typiquement base sur la structure du probleme. Pour la planification, cela peut signifier affecter les shifts jour par jour ou employe par employe. Previsible mais rapide, et trouve parfois de bonnes solutions que les strategies aleatoires manquent.

Recherche aleatoire avec redemarrages

Prendre des decisions de branchement aleatoires, mais redemarrer frequemment. Le caractere aleatoire apporte de la diversite, et les redemarrages empechent la recherche de rester bloquee dans des regions improductives. Combinee avec les clauses apprises des redemarrages precedents, cette strategie peut etre etonnamment efficace.

Quand un worker trouve une meilleure solution, tous les autres mettent a jour leurs bornes immediatement. Si le worker LNS ameliore le score de 95 000 a 88 000, le worker branch-and-bound peut desormais elaguer tout sous-arbre qui donnerait un score superieur a 88 000.

Comment les workers collaborent

Le mecanisme cle est un pool de solutions partage. Tous les workers lisent et ecrivent dans le meme pool. La collaboration fonctionne ainsi :

Supposons que le worker 1 (branch-and-bound) trouve une solution initiale avec un score de 120 000. Cette solution est immediatement visible par tous les autres workers. Le worker 3 (LNS) prend cette solution, en detruit et repare des parties, et trouve un score de 95 000. Maintenant tous les workers connaissent l'objectif : battre 95 000.

Le worker 2 (relaxation lineaire) calcule une borne inferieure de 82 000. Cela signifie qu'aucune solution ne peut scorer en dessous de 82 000. L'ecart entre 95 000 (meilleur trouve) et 82 000 (meilleur theorique) indique au solveur la marge d'amelioration restante.

Le worker 4 (LNS avec un schema de destruction different) trouve 88 000. Le worker 5 (base sur les cores) identifie que 3 000 points de penalite sont inevitables a cause de contraintes conflictuelles. La borne inferieure se resserre a 85 000. L'ecart se reduit de 13 000 a 3 000.

Cette convergence se produit sans aucune coordination explicite entre les workers. Chaque worker fait simplement son travail, mais chaque amelioration se propage instantanement a tous les autres. L'effet est multiplicatif : chaque worker rend tous les autres workers plus efficaces en reduisant l'espace de recherche.

Impact de num_workers

Voici ce qui se passe quand on fait varier num_workers sur un probleme reel de planification (200 employes, 30 jours, 50 types de shifts, limite de 5 minutes) :

Workers	Temps de resolution	Meilleur score	Amelioration vs 1 worker
1	30+ minutes	125 000	reference
2	18 minutes	110 000	12% meilleur
4	12 minutes	98 000	22% meilleur
8	8 minutes	92 000	26% meilleur
16	7 minutes	90 000	28% meilleur

Deux choses ressortent. D'abord, l'amelioration de la qualite des solutions est substantielle : 8 workers trouvent un score 26% meilleur qu'un seul worker sur le meme probleme. Ce n'est pas qu'une question de vitesse. La diversite des strategies de recherche decouvre des solutions qu'une seule strategie ne trouverait jamais dans un temps raisonnable.

Ensuite, l'amelioration de vitesse est super-lineaire jusqu'a 4 workers. Un worker a besoin de 30+ minutes ; 4 workers ont besoin de 12 minutes. C'est une acceleration de 2.5x pour une augmentation de 4x du calcul, mais la solution est aussi 22% meilleure. La vraie valeur est la combinaison d'une convergence plus rapide et d'une meilleure qualite de solution.

Benchmarks

Mesures sur differentes tailles de probleme sur un serveur standard (16 coeurs, 32 Go RAM), avec une limite de 10 minutes :

Employes	1 worker	4 workers	8 workers	16 workers
100	8 min / 95k	3 min / 82k	2 min / 78k	1.8 min / 77k
150	15 min / 115k	6 min / 95k	4 min / 88k	3.5 min / 85k
200	30+ min / 125k	12 min / 98k	8 min / 92k	7 min / 90k
300	timeout	25 min / 145k	15 min / 120k	12 min / 115k

Format : temps de resolution / meilleur score (score plus bas = meilleur planning). "Timeout" signifie que le solveur n'a pas trouve de solution satisfaisante dans la limite de temps avec un seul worker.

La ligne a 300 employes est particulierement revelante. Un seul worker ne peut pas resoudre ce probleme dans un temps raisonnable. Avec 4 workers, cela devient tractable. Avec 8, c'est pratique. L'ecart entre 8 et 16 workers est modeste, suggerant que 8 workers captent l'essentiel du benefice pour cette taille de probleme.

Rendements decroissants

La relation entre le nombre de workers et la performance suit une courbe de rendements decroissants :

• 1 a 4 workers : amelioration spectaculaire. Chaque nouveau worker ajoute une strategie de recherche fondamentalement differente. Le worker de relaxation LP fournit des bornes que le worker branch-and-bound ne pourrait pas calculer seul. Le worker LNS ameliore les solutions trouvees par la recherche par defaut. C'est la ou vous obtenez les plus gros gains.
• 4 a 8 workers : amelioration forte. Les workers supplementaires executent des variations des strategies principales (LNS avec differentes tailles de destruction, recherche aleatoire avec differentes politiques de redemarrage). La recherche devient plus robuste et moins susceptible de rester bloquee.
• 8 a 16 workers : amelioration moderee. Les workers supplementaires executent principalement plus de variations des strategies existantes. Vous gagnez 10-20% en qualite de solution et temps de resolution, ce qui compte pour les grands problemes mais n'est pas transformateur.
• Au-dela de 16 : amelioration marginale. CP-SAT dispose d'un nombre fini de strategies distinctes. Au-dela de 16 workers, vous executez principalement des doublons avec des graines aleatoires legerement differentes. Le pool de solutions partage devient le goulot d'etranglement car les workers passent plus de temps a se synchroniser qu'a chercher.

La diversite des strategies de recherche compte plus que le parallelisme brut. Huit workers executant huit strategies differentes surpasseront seize workers executant huit strategies deux fois.

Considerations memoire

Chaque worker maintient son propre arbre de recherche, ses structures de propagation et sa base de clauses. La consommation memoire evolue de maniere a peu pres lineaire avec le nombre de workers.

Taille du modele	1 worker	4 workers	8 workers	16 workers
100 employes	200-400 Mo	500 Mo - 1 Go	1-2 Go	2-3 Go
200 employes	400-800 Mo	1-2 Go	2-4 Go	4-6 Go
300 employes	600 Mo - 1 Go	1.5-3 Go	2-4 Go	4-8 Go

Pour un serveur de planification dedie executant un modele de 300 employes avec 8 workers, prevoyez 4 Go de RAM minimum, 8 Go recommandes. Avec 16 workers, 8 Go minimum, 16 Go recommandes. Le systeme d'exploitation et les autres processus ont aussi besoin de memoire.

La consommation memoire depend aussi du temps de resolution. Les executions plus longues accumulent plus de clauses apprises, qui consomment de la memoire. Si vous constatez une croissance memoire dans le temps, vous pouvez definir une limite de base de clauses ou reduire la limite de temps.

En pratique, 16 Go de RAM suffisent pour tout probleme de planification de moins de 300 employes avec 8 workers. Cela tient confortablement sur un serveur on-premise standard.

Configuration pratique

La configuration recommandee pour un serveur de planification en production :

from ortools.sat.python import cp_model

solver = cp_model.CpSolver()
solver.parameters.num_workers = 8
solver.parameters.max_time_in_seconds = 300
solver.parameters.log_search_progress = True

Choisir num_workers

Reglez num_workers sur le nombre de coeurs CPU physiques de votre serveur. Pas les coeurs logiques (hyperthreading) mais les coeurs physiques. Les workers CP-SAT sont CPU-bound, et l'hyperthreading apporte un benefice minimal pour la resolution de contraintes.

Pour un serveur de planification dedie, 8 coeurs est le point optimal. Cela capture l'essentiel du benefice du parallelisme (le saut de 4 a 8 est encore significatif), tout en gardant les couts materiels raisonnables. Passer a 16 coeurs donne 10-20% d'amelioration pour environ le double du cout.

Surveiller la progression de la recherche

Activez log_search_progress = True pour voir quels workers trouvent des solutions et quand. Les logs affichent des lignes comme :

#1  0.5s  best:120000  next:[95000,120000]  lns
#3  1.2s  best:95000   next:[88000,95000]   default
#5  2.8s  best:88000   next:[85000,88000]   core

Cela vous indique quelles strategies de recherche sont productives. Si le LNS trouve la plupart des ameliorations, le probleme beneficie de la recherche locale. Si la recherche par defaut domine, le probleme a une bonne structure que le branch-and-bound peut exploiter. Ces informations vous aident a ajuster les limites de temps et a comprendre votre probleme.

Limite de temps

Avec 8 workers, les limites de temps typiques par taille de probleme :

• 100 employes : 2-3 minutes suffisent generalement
• 150 employes : 5 minutes
• 200 employes : 10 minutes
• 300 employes : 15-20 minutes

Le comportement anytime de CP-SAT signifie que vous obtenez toujours la meilleure solution trouvee jusque-la, meme si vous arretez tot. Une limite de temps plus courte donne un score legerement moins bon, pas un resultat vide. Cela rend securise de definir des limites agressives pendant les tests et plus longues pour les executions en production.