Programmation par Contraintes
- Introduite par
- Rossi, van Beek & Walsh
- Année
- 2006
- Type
- Declarative combinatorial optimization
- Famille
- Mathematical programming
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La Programmation par Contraintes (PC) est un paradigme d'optimisation déclaratif dans lequel un problème est formulé comme un ensemble de variables, de domaines finis et de contraintes, et un solveur recherche systématiquement des affectations qui satisfont toutes les contraintes.
Formalisée de manière exhaustive par Rossi, van Beek et Walsh dans leur Handbook of Constraint Programming de 2006, la PC unifie l'élagage basé sur la propagation avec une recherche par retour arrière intelligente pour aborder les problèmes combinatoires dans les domaines de l'ordonnancement, de la planification et de la configuration.
L’intuition derrière la méthode
Imaginez la PC comme la résolution d'un puzzle complexe : chaque cellule est une variable avec un ensemble de valeurs légales, et chaque règle du puzzle est une contrainte. Plutôt que de deviner à l'aveugle, la PC utilise les règles pour éliminer immédiatement les valeurs impossibles des cellules voisines dès qu'une cellule est remplie. Cette propagation réduit considérablement l'espace de recherche, de sorte que le solveur n'explore que des combinaisons plausibles — effectuant un retour arrière et une révision uniquement lorsqu'il atteint une impasse.
Histoire
La Programmation par Contraintes est issue de la recherche en intelligence artificielle dans les années 1970 avec les premiers travaux sur la satisfaction de contraintes par Montanari et Mackworth. Elle a mûri au cours des années 1980 et 1990 avec le développement d'algorithmes de cohérence d'arc, de contraintes globales et de solveurs pratiques tels que CHIP et ILOG Solver. Le domaine a été consolidé de manière faisant autorité par Rossi, van Beek et Walsh dans le Handbook of Constraint Programming de 2006, qui reste la référence définitive, couvrant la théorie, les algorithmes et les applications en optimisation combinatoire.
Quand l’utiliser
La Programmation par Contraintes est la mieux adaptée aux problèmes combinatoires avec des contraintes complexes et hétérogènes — ordonnancement, élaboration d'horaires, configuration et routage — où la faisabilité est aussi importante que l'optimalité. Elle suppose que les problèmes peuvent être modélisés avec des domaines de variables discrets ou énumérables. La PC est moins efficace pour l'optimisation continue ou les programmes linéaires à grande échelle, où les solveurs de Programmation Linéaire ou de Programmation en Nombres Entiers Mixtes dominent généralement. Lorsque les contraintes sont très structurées et que la propagation peut élaguer de grandes portions de l'espace de recherche, la PC surpasse les métaheuristiques à usage général.
Limites et points d’attention
- Évolutivité : la recherche exponentielle dans le pire des cas rend la PC lente sur de très grandes instances avec une propagation faible.
- Nécessite une bonne modélisation : de mauvaises heuristiques d'ordonnancement des variables/valeurs ou des contraintes globales manquantes conduisent à des arbres de recherche inutilement grands.
- Domaines continus : la PC est nativement conçue pour les domaines discrets ; les problèmes continus nécessitent des extensions spécialisées ou des approches hybrides.
- Expertise du solveur : une utilisation efficace exige une familiarité avec les techniques de modélisation des contraintes et les bibliothèques de contraintes globales spécifiques au solveur.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Modélisation déclarative : les règles complexes du monde réel sont exprimées directement comme des contraintes sans spécifier la procédure de recherche.
- Élagage puissant : la propagation des contraintes élimine les régions infaisables tôt, réduisant souvent la recherche de plusieurs ordres de grandeur.
- Gère les contraintes hétérogènes : les contraintes logiques, arithmétiques, globales et définies par l'utilisateur coexistent naturellement dans un même modèle.
- Garantit la complétude : le solveur trouve une solution optimale ou prouve l'infaisabilité, contrairement aux méthodes heuristiques.
Applications
- Ordonnancement des employés et des infirmières : affecter le personnel aux quarts de travail tout en respectant les contraintes de disponibilité, de droit du travail et de compétences.
- Élaboration d'horaires : construire des horaires universitaires ou scolaires soumis aux contraintes de capacité des salles, de disponibilité des instructeurs et de programme d'études.
- Configuration : assembler des configurations de produits (ordinateurs, véhicules) à partir de catalogues de composants sous des contraintes de compatibilité et de ressources.
- Routage de véhicules et logistique : planifier des itinéraires de livraison soumis à des fenêtres de temps, des capacités de véhicules et des réglementations de conducteurs.
- Enchères combinatoires et allocation de ressources : attribuer des ressources à des soumissionnaires ou à des tâches sous des contraintes d'exclusivité et de budget.
Comment ça marche
Comment ça marche
Le problème est encodé comme un triplet de Problème de Satisfaction de Contraintes (PSC) composé de variables X, de leurs domaines finis D et d'un ensemble de contraintes C. Chaque variable x_i peut se voir attribuer n'importe quelle valeur de son domaine D_i. Les contraintes définissent des combinaisons de valeurs admissibles sur des sous-ensembles de variables, traduisant des règles du monde réel — limites de capacité, relations de précédence, conflits de ressources — en une structure mathématique sur laquelle le solveur peut raisonner.
Formule
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}Avant et pendant la recherche, le solveur applique la cohérence d'arc et d'autres algorithmes de cohérence locale pour élaguer les valeurs de domaine qui ne peuvent participer à aucune solution valide. Pour chaque paire de variables contraintes, la cohérence d'arc supprime les valeurs du domaine d'une variable pour lesquelles aucune valeur de support n'existe dans le domaine de l'autre. Cette propagation est déclenchée à plusieurs reprises après chaque affectation, réduisant drastiquement l'espace de recherche effectif.
Formule
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}Le solveur sélectionne une variable non affectée — généralement en utilisant des heuristiques telles que les valeurs restantes minimales ou le degré — et lui attribue provisoirement une valeur de son domaine élagué. La propagation s'exécute à nouveau ; si une contradiction est détectée (un domaine vide), le solveur effectue un retour arrière au point de choix le plus récent et essaie une autre valeur. Le saut arrière (backjumping) et l'enregistrement des "nogoods" peuvent accélérer davantage la récupération après les échecs.
Formule
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}Lorsque toutes les variables ont été affectées à des valeurs cohérentes avec chaque contrainte, l'affectation complète S* constitue une solution. Pour les problèmes d'optimisation, une fonction objectif guide la recherche vers la meilleure solution réalisable, et les stratégies de branch-and-bound resserrent progressivement la borne à mesure que de meilleures solutions sont trouvées, jusqu'à ce que l'optimum global soit certifié ou qu'une limite de temps soit atteinte.
Formule
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}Pièges courants
- Surcharger le modèle avec des contraintes redondantes ou conflictuelles amène le solveur à signaler incorrectement l'infaisabilité.
- Négliger les contraintes globales (par exemple, alldifferent, cumulative) manque des opportunités de propagation que les algorithmes spécialisés offrent gratuitement.
- Ignorer les heuristiques de recherche et se fier à l'ordonnancement par défaut des variables/valeurs peut gaspiller un temps exponentiel sur des ordonnancements pathologiques.
- Confondre la satisfaction de contraintes avec l'optimisation : oublier d'ajouter une fonction objectif et un resserrement des bornes ne donne que la première solution réalisable, pas la meilleure.
Questions fréquentes
En quoi la Programmation par Contraintes diffère-t-elle de la Programmation Linéaire en Nombres Entiers ?
Bien que les deux résolvent des problèmes combinatoires, la PLNE exige que toutes les contraintes et objectifs soient linéaires, permettant des bornes de relaxation LP efficaces. La PC n'impose aucune exigence de linéarité et repose plutôt sur la propagation des contraintes et la recherche systématique. La PC gère les contraintes logiques et globales complexes plus naturellement, tandis que la PLNE est souvent plus performante sur les problèmes avec une forte structure linéaire et un grand nombre de variables.
Que sont les contraintes globales et pourquoi sont-elles importantes ?
Les contraintes globales sont des contraintes de haut niveau sur un nombre arbitraire de variables — par exemple, alldifferent (toutes les variables prennent des valeurs distinctes) ou cumulative (l'utilisation des ressources à tout moment ne dépasse pas la capacité). Elles sont importantes car les solveurs implémentent des algorithmes de propagation dédiés et très efficaces pour chacune, réalisant un élagage bien plus fort que la décomposition de la même condition en de nombreuses contraintes binaires, ce qui laisserait une grande partie de l'espace de recherche inexplorée.
La Programmation par Contraintes peut-elle trouver des solutions optimales, ou seulement des solutions réalisables ?
La PC peut trouver des solutions optimales en combinant la recherche de faisabilité avec une fonction objectif. Le solveur utilise le branch-and-bound : une fois qu'une solution réalisable est trouvée, il ajoute une contrainte exigeant que toute solution ultérieure soit strictement meilleure, et ce, jusqu'à ce qu'aucune amélioration ne soit possible. Cela certifie l'optimalité. Si le temps d'exécution est limité, la meilleure solution trouvée jusqu'à présent est renvoyée comme une approximation.
Méthodes associées
Sources
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
ISBN : 978-0-444-52726-4Copié.