Recherche Multi-Thread dans CP-SAT

Pas du parallélisme de données

Une idée reçue courante : quand vous configurez num_workers = 8 dans CP-SAT, le solveur ne découpe PAS votre problème de planification en 8 morceaux. Il n'assigne pas les employés 1-37 au worker 1 et les employés 38-75 au worker 2. Ce serait du parallélisme de données, et cela ne fonctionne pas pour la programmation par contraintes.

À la place, CP-SAT utilise du parallélisme de portfolio. Chaque worker exécute une stratégie de recherche différente sur le problème complet. Les 8 workers voient chaque employé, chaque shift, chaque contrainte. Ce qui diffère, c'est la manière dont ils explorent l'espace des solutions. Ils partagent leurs meilleures solutions et bornes en temps réel, de sorte que chaque découverte d'un worker bénéficie à tous les autres.

Cette distinction est importante car elle explique pourquoi ajouter des workers améliore la qualité des solutions, pas seulement la vitesse. Plus de workers signifie plus de stratégies de recherche diverses exécutées simultanément, ce qui augmente les chances de trouver de meilleures solutions.

Stratégies de recherche

CP-SAT exécute plusieurs stratégies de recherche simultanément, chacune adaptée à différents aspects du problème :

Recherche par défaut (branch-and-bound)

L'approche classique. Choisir une variable, essayer une valeur, propager les contraintes, revenir en arrière si ça échoue. CP-SAT utilise la réduction de domaine pour élaguer les valeurs impossibles avant de brancher. Cette stratégie est méthodique et exhaustive mais peut être lente sur les grands problèmes.

Large Neighborhood Search (LNS)

Partir de la meilleure solution courante, détruire un sous-ensemble aléatoire d'affectations (par exemple désaffecter 20% des paires employé-jour), puis réparer la partie détruite en gardant le reste fixe. Le LNS est excellent pour améliorer incrémentalement de bonnes solutions. C'est souvent lui qui trouve la meilleure solution finale dans les problèmes de planification.

Relaxation linéaire

Relâcher les variables booléennes en valeurs continues (autoriser 0.5 au lieu de seulement 0 ou 1), puis résoudre le programme linéaire résultant. La solution LP fournit une borne inférieure sur l'objectif. Cette borne indique à tous les autres workers : "aucune solution ne peut scorer en dessous de cette valeur", ce qui élague leurs arbres de recherche.

Recherche basée sur les cores

Trouver des cores insatisfaisables minimaux : de petits sous-ensembles de contraintes souples qui ne peuvent pas tous être satisfaits simultanément. Cette stratégie identifie quels compromis sont inévitables, aidant le solveur à se concentrer sur des améliorations réalistes plutôt que de poursuivre des objectifs impossibles.

Recherche fixe

Suivre un ordre fixe de variables, typiquement basé sur la structure du problème. Pour la planification, cela peut signifier affecter les shifts jour par jour ou employé par employé. Prévisible mais rapide, et trouve parfois de bonnes solutions que les stratégies aléatoires manquent.

Recherche aléatoire avec redémarrages

Prendre des décisions de branchement aléatoires, mais redémarrer fréquemment. Le caractère aléatoire apporte de la diversité, et les redémarrages empêchent la recherche de rester bloquée dans des régions improductives. Combinée avec les clauses apprises des redémarrages précédents, cette stratégie peut être étonnamment efficace.

Quand un worker trouve une meilleure solution, tous les autres mettent à jour leurs bornes immédiatement. Si le worker LNS améliore le score de 95 000 à 88 000, le worker branch-and-bound peut désormais élaguer tout sous-arbre qui donnerait un score supérieur à 88 000.

Comment les workers collaborent

Le mécanisme clé est un pool de solutions partage. Tous les workers lisent et écrivent dans le même 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 immédiatement visible par tous les autres workers. Le worker 3 (LNS) prend cette solution, en détruit et répare des parties, et trouve un score de 95 000. Maintenant tous les workers connaissent l'objectif : battre 95 000.

Le worker 2 (relaxation linéaire) calcule une borne inférieure de 82 000. Cela signifie qu'aucune solution ne peut scorer en dessous de 82 000. L'écart entre 95 000 (meilleur trouvé) et 82 000 (meilleur théorique) indique au solveur la marge d'amélioration restante.

Le worker 4 (LNS avec un schéma de destruction différent) trouve 88 000. Le worker 5 (basé sur les cores) identifie que 3 000 points de pénalité sont inévitables à cause de contraintes conflictuelles. La borne inférieure se resserre à 85 000. L'écart se réduit de 13 000 à 3 000.

Cette convergence se produit sans aucune coordination explicite entre les workers. Chaque worker fait simplement son travail, mais chaque amélioration se propage instantanément à tous les autres. L'effet est multiplicatif : chaque worker rend tous les autres workers plus efficaces en réduisant l'espace de recherche.

Impact de num_workers

Voici ce qui se passe quand on fait varier num_workers sur un problème réel de planification (200 employés, 30 jours, 50 types de shifts, limite de 5 minutes) :

Workers	Temps de résolution	Meilleur score	Amélioration vs 1 worker
1	30+ minutes	125 000	référence
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'amélioration de la qualité des solutions est substantielle : 8 workers trouvent un score 26% meilleur qu'un seul worker sur le même problème. Ce n'est pas qu'une question de vitesse. La diversité des stratégies de recherche découvre des solutions qu'une seule stratégie ne trouverait jamais dans un temps raisonnable.

Ensuite, l'amélioration de vitesse est super-linéaire jusqu'à 4 workers. Un worker a besoin de 30+ minutes ; 4 workers ont besoin de 12 minutes. C'est une accélération 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 qualité de solution.

Benchmarks

Mesures sur différentes tailles de problème sur un serveur standard (16 coeurs, 32 Go RAM), avec une limite de 10 minutes :

Employés	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 résolution / meilleur score (score plus bas = meilleur planning). "Timeout" signifie que le solveur n'a pas trouvé de solution satisfaisante dans la limite de temps avec un seul worker.

La ligne à 300 employés est particulièrement revelante. Un seul worker ne peut pas résoudre ce problème dans un temps raisonnable. Avec 4 workers, cela devient tractable. Avec 8, c'est pratique. L'écart entre 8 et 16 workers est modeste, suggérant que 8 workers captent l'essentiel du bénéfice pour cette taille de problème.

Rendements décroissants

La relation entre le nombre de workers et la performance suit une courbe de rendements décroissants :

• 1 à 4 workers : amélioration spectaculaire. Chaque nouveau worker ajoute une stratégie de recherche fondamentalement différente. Le worker de relaxation LP fournit des bornes que le worker branch-and-bound ne pourrait pas calculer seul. Le worker LNS améliore les solutions trouvées par la recherche par défaut. C'est là où vous obtenez les plus gros gains.
• 4 à 8 workers : amélioration forte. Les workers supplémentaires exécutent des variations des stratégies principales (LNS avec différentes tailles de destruction, recherche aléatoire avec différentes politiques de redémarrage). La recherche devient plus robuste et moins susceptible de rester bloquée.
• 8 à 16 workers : amélioration modérée. Les workers supplémentaires exécutent principalement plus de variations des stratégies existantes. Vous gagnez 10-20% en qualité de solution et temps de résolution, ce qui compte pour les grands problèmes mais n'est pas transformateur.
• Au-delà de 16 : amélioration marginale. CP-SAT dispose d'un nombre fini de stratégies distinctes. Au-delà de 16 workers, vous exécutez principalement des doublons avec des graines aléatoires légèrement différentes. Le pool de solutions partage devient le goulot d'étranglement car les workers passent plus de temps à se synchroniser qu'à chercher.

La diversité des stratégies de recherche compte plus que le parallélisme brut. Huit workers exécutant huit stratégies différentes surpasseront seize workers exécutant huit stratégies deux fois.

Considérations mémoire

Chaque worker maintient son propre arbre de recherche, ses structures de propagation et sa base de clauses. La consommation mémoire évolue de manière à peu près linéaire avec le nombre de workers.

Taille du modèle	1 worker	4 workers	8 workers	16 workers
100 employés	200-400 Mo	500 Mo - 1 Go	1-2 Go	2-3 Go
200 employés	400-800 Mo	1-2 Go	2-4 Go	4-6 Go
300 employés	600 Mo - 1 Go	1.5-3 Go	2-4 Go	4-8 Go

Pour un serveur de planification dédié exécutant un modèle de 300 employés avec 8 workers, prévoyez 4 Go de RAM minimum, 8 Go recommandes. Avec 16 workers, 8 Go minimum, 16 Go recommandes. Le système d'exploitation et les autres processus ont aussi besoin de mémoire.

La consommation mémoire dépend aussi du temps de résolution. Les exécutions plus longues accumulent plus de clauses apprises, qui consomment de la mémoire. Si vous constatez une croissance mémoire dans le temps, vous pouvez définir une limite de base de clauses ou réduire la limite de temps.

En pratique, 16 Go de RAM suffisent pour tout problème de planification de moins de 300 employés avec 8 workers. Cela tient confortablement sur un serveur standard, en local ou hébergé.

Configuration pratique

La configuration recommandée 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

Réglez 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 bénéfice minimal pour la résolution de contraintes.

Pour un serveur de planification dédié, 8 coeurs est le point optimal. Cela capture l'essentiel du bénéfice du parallélisme (le saut de 4 à 8 est encore significatif), tout en gardant les coûts matériels raisonnables. Passer à 16 coeurs donne 10-20% d'amélioration pour environ le double du coût.

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 stratégies de recherche sont productives. Si le LNS trouve la plupart des améliorations, le problème bénéficie de la recherche locale. Si la recherche par défaut domine, le problème a une bonne structure que le branch-and-bound peut exploiter. Ces informations vous aident à ajuster les limites de temps et à comprendre votre problème.

Limite de temps

Avec 8 workers, les limites de temps typiques par taille de problème :

• 100 employés : 2-3 minutes suffisent généralement
• 150 employés : 5 minutes
• 200 employés : 10 minutes
• 300 employés : 15-20 minutes

Le comportement anytime de CP-SAT signifie que vous obtenez toujours la meilleure solution trouvée jusque-là, même si vous arrêtez tôt. Une limite de temps plus courte donne un score légèrement moins bon, pas un résultat vide. Cela rend sécurisé de définir des limites agressives pendant les tests et plus longues pour les exécutions en production.