Introduction pratique à la programmation par contraintes avec CP-SAT et Python

 (pganalyze.com)
1 points par GN⁺ 2024-07-05 | 1 commentaires | Partager sur WhatsApp
  • La programmation par contraintes (CP) est une approche déclarative qui modélise les problèmes d’optimisation discrète non pas avec du code procédural, mais avec des variables, des domaines et des contraintes, afin que le solveur trouve une solution qui respecte les conditions
  • Le cœur du modèle repose sur les variables, qui représentent les valeurs à trouver, les domaines, qui définissent l’ensemble des valeurs possibles, et les contraintes, qui limitent les relations entre les variables ; si nécessaire, une fonction objectif permet de choisir une meilleure solution
  • L’exemple du partage du prix de bonbons entre Alice, Bob et Carol montre, via alldifferent, maximum et minimize, comment passer d’une solution valide à une solution plus équitable
  • L’exemple concret construit, avec le solveur open source CP-SAT de Google OR-Tools et Python, un planning hebdomadaire pour 4 employés sur 7 jours, 3 rotations et 2 rôles
  • On peut ajouter progressivement au même modèle des contraintes comme une limite de 40 heures par semaine, un emploi du temps de cours, des combinaisons de personnes qui ne doivent pas travailler ensemble, une répartition équitable du travail le week-end, des demandes de congés et une minimisation des écarts du nombre de shifts

La logique de base de la programmation par contraintes

  • La programmation par contraintes (CP) est un paradigme déclaratif pour résoudre des problèmes d’optimisation discrète
  • En programmation impérative, on écrit pas à pas la procédure pour atteindre un résultat, tandis que l’approche déclarative décrit les conditions du résultat souhaité et laisse le système d’exécution trouver ce résultat
  • Dans l’exemple d’une liste d’adultes, un code impératif parcourt une liste de personnes et vérifie Age >= 18, alors qu’un SQL déclaratif exprime directement la condition avec SELECT person_name FROM people WHERE age >= 18;
  • La CP décrit elle aussi le résultat souhaité sous forme de modèle, dont les composants clés sont les variables, les domaines et les contraintes
    • Les variables indiquent ce qu’il faut trouver
    • Les domaines sont les ensembles de valeurs que peuvent prendre les variables
    • Les contraintes limitent les relations entre les variables

Variables, domaines, contraintes et fonction objectif

  • Une solution est une affectation dans laquelle chaque variable prend une valeur de son domaine tout en satisfaisant toutes les contraintes
  • L’exemple des bonbons consiste à faire contribuer Alice, Bob et Carol, qui ont chacun au maximum 20 dollars, pour acheter des bonbons à 50 dollars
    • Les variables a, b et c sont les montants payés par chaque personne
    • Le domaine des trois variables est {0, ..., 20}
    • a + b + c == 50 fixe le total
    • a >= b impose qu’Alice paie au moins autant que Bob
    • c % 5 == 0 limite le montant de Carol à un multiple de 5
    • Pour éviter que deux personnes paient la même somme, on peut utiliser a != b, a != c, b != c
  • Les conditions qui portent sur plusieurs variables peuvent être exprimées via des contraintes globales (global constraints) ; alldifferent(a, b, c) impose par exemple que les trois variables aient toutes des valeurs différentes
  • Le solveur prend le modèle en entrée et renvoie une solution valide
    • La solution d’exemple a = 19, b = 11, c = 20 satisfait toutes les contraintes
    • Mais comme Carol paie presque le double de Bob, il peut exister une solution plus équilibrée
  • La fonction objectif permet, parmi les solutions qui satisfont les contraintes, de minimiser ou maximiser une expression donnée
    • On introduit une nouvelle variable x comme plus grande contribution et on utilise maximum(x, [a, b, c])
    • En appliquant minimize: x, on obtient a = 18, b = 17, c = 15, x = 18
    • L’écart entre la contribution la plus élevée et la plus faible passe ainsi de 9 dollars à 3 dollars

Construire un modèle de planning avec CP-SAT et Python

  • L’exemple concret consiste à générer le planning hebdomadaire d’une petite boutique
    • La boutique est ouverte tous les jours de 8 h à 20 h
    • Chaque journée comporte trois shifts : Morning, Afternoon et Evening, de 4 heures chacun
    • Il existe deux rôles : Cashier et Restocker
    • Les employés sont Phil, Emma, David et Rebecca
  • CP-SAT est un solveur CP open source inclus dans OR-Tools de Google
  • Un modèle vide se crée avec cp_model.CpModel() dans ortools.sat.python
  • Les rôles possibles par employé sont les suivants
    • Phil : Restocker
    • Emma : Cashier, Restocker
    • David : Cashier, Restocker
    • Rebecca : Cashier
  • Le planning est représenté par des variables booléennes combinant employé, rôle, jour et shift
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] vaut 1 si Emma travaille comme Restocker le lundi soir, sinon 0
    • model.new_bool_var() crée une variable dont le domaine est {0, 1}

Contraintes de base du planning

  • Comme il faut exactement un caissier à chaque créneau, la somme du rôle Cashier doit être égale à 1 pour chaque jour et chaque shift
  • Pour le réassort, un seul shift par jour est nécessaire ; la somme complète du rôle Restocker sur chaque journée est donc fixée à 1
  • Pour éviter qu’un shift Evening de réassort un jour soit suivi d’un shift Morning de réassort le lendemain, on impose que la somme de ces deux affectations ne dépasse pas 1
  • Un employé ne peut pas occuper deux rôles sur le même shift ; la somme des rôles par employé, jour et shift doit donc être inférieure ou égale à 1
  • Pour empêcher l’affectation à des rôles non autorisés, toutes les variables correspondant à des rôles impossibles pour cet employé sont fixées à 0
  • Le maximum de travail quotidien est de 8 heures, soit 2 shifts
    • Affecter à la fois Morning et Evening le même jour créerait 4 heures d’inactivité pendant Afternoon
    • En limitant la somme des affectations Morning et Evening à 1 par employé et par jour, on empêche à la fois plus de 2 shifts par jour et ce trou en milieu de journée

Exécution du solveur et premiers résultats

  • Pour résoudre le modèle, on crée cp_model.CpSolver() puis on appelle solver.solve(model)
  • Une fois la solution obtenue, on lit les valeurs des variables schedule avec solver.value(...)
  • Le planning initial satisfait toutes les contraintes de base, mais Rebecca se retrouve avec 14 shifts sur la semaine
  • Pour éviter les heures supplémentaires, on ajoute une contrainte limitant le travail hebdomadaire de chaque employé à 40 heures, soit 10 shifts
  • Phil étant étudiant à temps plein, on lui impose exactement 4 shifts par semaine, et on lui interdit de travailler les matins et après-midis en semaine à cause de ses cours
  • Pour que Phil et Emma ne travaillent pas sur le même shift, on limite la somme de leurs affectations à 1 pour chaque jour et chaque shift
  • Comme personne n’aime travailler le week-end, on ajoute une contrainte répartissant les 8 shifts totaux du samedi et du dimanche en 2 shifts chacun entre les quatre employés

États de solution : OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • Le solveur prend le modèle en entrée et renvoie un état ainsi qu’une solution
  • OPTIMAL signifie qu’il a trouvé une solution pour laquelle il n’en existe pas de meilleure
    • Par exemple, si x + y >= 5 et qu’on minimise x + y, alors (x, y) = (5, 0) est une solution optimale
    • (x, y) = (3, 2) peut aussi être optimal, car il a la même valeur d’objectif
  • INFEASIBLE signifie qu’aucune affectation de valeurs ne peut satisfaire les contraintes
    • Par exemple, si x ∈ {0, ..., 10} mais que l’on exige x >= 15, le problème est impossible
  • Si le solveur est interrompu par une limite de temps à cause de la taille du problème ou de la complexité de la fonction objectif, deux états sont possibles
    • FEASIBLE : une solution satisfaisant les contraintes a été trouvée, sans garantie d’optimalité
    • UNKNOWN : aucune solution n’a été trouvée et on ne sait pas non plus si une solution existe

Demandes de congés et répartition équitable

  • Si l’on ajoute la contrainte selon laquelle Emma veut être absente du lundi au vendredi, l’état du solveur devient INFEASIBLE
    • Car il est impossible de compléter le planning sans violer d’autres contraintes
  • Si l’on remplace cette condition par un repos du lundi au mercredi seulement, le planning redevient réalisable
    • Phil travaille exactement 4 shifts comme souhaité
    • Emma en prend 6, David 10 et Rebecca 8
  • Pour rendre plus équilibré le nombre de shifts entre Emma, David et Rebecca, on ajoute une fonction objectif
    • On crée des variables entières total_shifts représentant le nombre total de shifts de chaque employé
    • model.new_int_var(0, 10, ...) crée une variable entière pouvant prendre des valeurs de 0 à 10
    • Phil étant à temps partiel, on l’exclut et on suit les nombres minimal et maximal de shifts avec model.add_min_equality(...) et model.add_max_equality(...)
    • model.minimize(max_shifts - min_shifts) minimise l’écart entre le nombre maximal et minimal de shifts
  • Le résultat final est de 4 shifts pour Phil, 6 pour Emma, 9 pour David et 9 pour Rebecca
    • Emma tombe à 6 shifts parce qu’elle a 3 jours de repos
    • David et Rebecca sont répartis à parts égales avec 9 shifts chacun

Code d’exemple et sujet suivant

  • Ce modèle génère un planning qui satisfait à la fois les besoins du gérant de la boutique et ceux des employés
  • On peut continuer à ajouter des contraintes au même modèle CP pour vérifier si de nouvelles demandes sont possibles, puis utiliser une fonction objectif pour trouver, parmi les solutions réalisables, une répartition plus équitable
  • Le code d’exemple est disponible sur le GitHub de pganalyze
  • Le prochain article portera sur l’utilisation de la programmation par contraintes pour la sélection d’index dans Postgres

À lire aussi

1 commentaires

 
GN⁺ 2024-07-05
Commentaires sur Hacker News

  • J’ai déjà utilisé des solveurs de contraintes, et ce qu’ils permettent de faire semblait vraiment magique. Le problème, c’est qu’il n’existe pas beaucoup de ressources adaptées aux débutants
    La plupart se limitent à résoudre des sudokus (le Hello World du domaine), ou bien à de la littérature de recherche primaire très technique réservée aux spécialistes du domaine
    C’est dommage, car si ces outils devenaient plus accessibles, ils pourraient probablement résoudre énormément de problèmes. Et par accessible, j’entends toujours qu’il faut un programmeur ; transformer un problème en DSL de contraintes n’est pas quelque chose que la plupart des gens savent bien faire

    • À mon avis, si ces outils ne sont pas suffisamment accessibles, c’est surtout parce que la plupart des solveurs reposent sur la programmation linéaire en nombres entiers mixte (MIP), ce qui oblige à exprimer le domaine sous forme d’équations mathématiques. Il faut donc que l’utilisateur connaisse à la fois le domaine et les mathématiques pour formuler correctement les contraintes
      Cela dit, les solveurs ne se limitent pas au MIP. Il existe aussi des solveurs de contraintes fondés sur la recherche locale, et cette approche n’impose pas de modéliser toutes les contraintes comme des relations ou des équations entre variables entières
      Dans un solveur par recherche locale, les contraintes sont généralement traitées comme des boîtes noires indiquant à quel point une solution donnée est bonne. Il est donc difficile de garantir l’optimalité sans tester toutes les solutions possibles, mais on trouve en général des solutions quasi optimales dans un délai raisonnable
      Timefold Solver fait partie de ces solveurs basés sur la recherche locale. L’utilisateur annote son domaine afin que le solveur sache quelles sont les variables et les valeurs possibles. Les contraintes manipulent donc des Shift et des Employee plutôt que des int, et peuvent aussi accéder à leurs méthodes
      Transparence : je travaille sur Timefold Solver
    • C’est exactement ça. La syntaxe ou l’API concrète d’un solveur de contraintes est si simple qu’on l’apprend très vite. Ce qui demande vraiment du temps et de l’expertise, c’est de modéliser le problème de cette manière, et il n’existe pratiquement aucun exemple de taille et de complexité réalistes auquel se référer
      J’ai environ cinq ans d’expérience à résoudre des problèmes de planification avec MiniZinc, mais malheureusement tout ce code est privé et ne sera jamais publié en open source
      J’aimerais créer un exemple complet de programmation par contraintes, incluant conteneurisation, visualisation et modélisation, mais le vrai obstacle est de trouver un problème qui vaille réellement la peine d’être résolu et pour lequel il existe des données open source exploitables
    • Je suis d’accord pour dire que la réduction est bien plus difficile que la théorie elle-même. « SAT/SMT by Example » de Dennis Yurichev (https://smt.st/) est une bonne ressource sur le sujet, mais elle est assez intimidante
    • Dire que « la plupart des ressources se limitent à résoudre des sudokus ou à de la littérature de recherche réservée aux experts du domaine » est très juste. J’ai essayé d’utiliser un solveur SAT dans un moteur de règles, et je n’avais absolument aucune idée de la manière de m’y prendre
      Après pas mal de déduction, j’ai fini par construire une preuve de concept de base, mais je n’ai pas réussi à la faire évoluer jusqu’au niveau réellement nécessaire. Le fossé entre une implémentation jouet et quelque chose de plus substantiel était énorme
    • J’ai codé pendant longtemps, même si je suis un peu rouillé maintenant. L’an dernier, j’ai créé un optimiseur d’équipes de foot avec OR-Tools de Google, avec des contraintes de choix comme jouer avec un ami et des conditions comme équilibrer le niveau entre les équipes
      Les LLM m’ont aidé à avancer assez vite dans une direction globalement correcte. Aujourd’hui, ils échouent encore à tomber juste exactement, mais ils m’ont suffisamment aidé pour que je puisse ensuite terminer le reste moi-même

  • L’essentiel, dans tout cela, est d’apprendre à modéliser quelque chose sous une forme que l’on peut envoyer à un solveur. Ensuite vient la manière de présenter la solution obtenue de façon compréhensible pour un humain
    Ce qui est dommage, c’est que la plupart des programmes cherchent à conserver les données dans une seule représentation, ce qui va à l’encontre de cette façon de penser. Dans la plupart des cas, ce n’est pas raisonnable, et cela entraîne beaucoup de contorsions pour adapter les algorithmes à la nouvelle représentation
    L’article aborde aussi ce point au début, en évoquant brièvement le déclaratif. Je regrette toujours que mon code ne transforme pas plus souvent les données d’une représentation à une autre. On peut ainsi obtenir des représentations très concises, avec en plus un double bénéfice : elles deviennent aussi plus rapides grâce à cette concision
    Bien sûr, je sais que cela décrit au fond beaucoup de pipelines de données : des architectures où l’on passe l’essentiel du temps à transformer les données et à les aiguiller vers différents lieux de calcul

  • Dans un livre que j’ai écrit il y a quelque temps et que je suis en train de réécrire, il y a un court chapitre sur l’utilisation de MiniZinc avec Python : https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc est un système de programmation par contraintes. Il existe aussi un bon cours Coursera qui utilise MiniZinc

    • Je serais curieux d’avoir le lien vers le cours Coursera

  • Après avoir étudié l’économétrie, j’ai beaucoup utilisé des solveurs au début des années 2000 pendant un master en recherche opérationnelle. Aujourd’hui, je travaille dans le logiciel web avec Python, et ça fait plaisir de voir un article approfondi sur ce sujet
    J’aime ce sujet, et la lecture de l’article m’a rappelé beaucoup de souvenirs. Cela m’a aussi rappelé que traduire les contraintes en modèle (variables, structure, etc.) représente 90 % du travail et constitue la partie la plus difficile

    • Pendant mon master, j’ai utilisé un programme appelé GAMS
      Sa syntaxe est entièrement en format libre
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • Les LLM peuvent être assez utiles pour transformer des contraintes en modèle. J’avais envie d’essayer un adaptateur qui convertirait depuis un LLM vers un modèle de contraintes
      Cela ressemble à un fruit assez facile à cueillir, mais je me demande si d’autres personnes en tireraient aussi profit
    • À mon avis, la partie la plus difficile est de faire tourner cela en production tout en minimisant le problème. Le faire passer à l’échelle et le rendre robuste face aux changements de données prend beaucoup de temps

  • Un client gère un camp sportif pour enfants. Les enfants peuvent indiquer les sports qu’ils veulent pratiquer et les amis avec lesquels ils aimeraient être dans le même groupe.
    Cela créait un problème de planification difficile à résoudre manuellement, et auparavant plusieurs semaines de travail humain y étaient consacrées chaque année. On lui a construit un système simple qui relie ses données à un optimiseur basé sur OR-Tools, et désormais la planification se fait en quelques clics.

    • Exactement. Si l’on encode correctement les données, les contraintes et la fonction d’utilité dans le système, on peut trouver très rapidement un grand nombre de solutions suffisamment bonnes.
      Je suis entraîneur dans une ligue de basket, avec 8 périodes. Aucun joueur ne peut jouer plus de 2 périodes de plus qu’un autre. Le nombre de compositions possibles par match, tout en respectant les contraintes de temps de jeu, est astronomique.
      Trouver un ensemble de compositions qui respecte les contraintes est très facile, mais trouver un ensemble optimal ou quasi optimal est très difficile. Cela devient encore plus intéressant quand il faut tenir compte des joueurs qui arrivent en retard ou qui ne viennent pas sans prévenir.
      *Ce n’est pas toujours entièrement faisable
    • Un billet de blog détaillant la façon dont cela a été fait aurait sans aucun doute énormément de succès.

  • Je me demande s’il existe des outils de CAO paramétrique qui fonctionnent principalement comme solveurs de contraintes.
    Il m’arrive trop souvent de devoir estimer à la louche des valeurs de paramètres qui ne m’intéressent pas au départ, et cela m’agace. Ce serait bien de pouvoir définir les paramètres qui m’intéressent comme contraintes et optimiser le reste.

  • Je me demande comment cette approche se compare à la programmation linéaire en nombres entiers mixtes. Et qu’en est-il pour les problèmes physiques ?

    • Beaucoup de problèmes peuvent être formulés avec les deux approches. En MILP, il y a toujours une fonction objectif, et les contraintes sont toujours des combinaisons linéaires des variables de décision.
      Gurobi est incroyablement rapide, si bien qu’il peut valoir la peine de tordre le problème pour le faire entrer de force dans un modèle MILP afin d’obtenir une solution.
    • CP-SAT étant réservé aux entiers, il ne me semble pas très adapté à la physique. On peut mettre des réels à l’échelle, mais ce n’est pas aussi bien que de manipuler directement des nombres à virgule flottante.
      L’avantage de CP-SAT est qu’il traite les variables et contraintes booléennes et entières bien plus efficacement qu’un solveur MIP, en particulier pour les contraintes de haut niveau comme all_different.
    • Je suppose que c’est globalement similaire. https://www.amazon.com/gp/product/1107658799/ est le dernier livre que j’ai lu sur ce sujet, et il aborde beaucoup des mêmes idées.
      En particulier, je considère que la partie de cet article qui cherche à minimiser une certaine valeur écrit directement la même chose.