L'optimisation des contraintes, ou programmation de contraintes, est le nom donné à l'identification de solutions réalisables parmi un très grand nombre de candidats, où le problème peut être modélisé en fonction de contraintes arbitraires. Les problèmes de CP surviennent dans de nombreuses disciplines scientifiques et d'ingénierie. (Le terme "programmation" est un peu trompeur, de la même manière que le terme "ordinateur" signifiait autrefois "une personne qui fait des calculs". Ici, le terme "programmation" désigne l'organisation d'un plan, plutôt que la programmation dans un langage informatique.)
La CP est basée sur la faisabilité (trouver une solution réalisable) plutôt que sur l'optimisation (recherche d'une solution optimale), et se concentre sur les contraintes et les variables plutôt que sur la fonction objectif. En fait, un problème de CP peut même ne pas avoir de fonction objective. L'objectif peut être de réduire un très grand ensemble de solutions possibles à un sous-ensemble plus facile à gérer en ajoutant des contraintes au problème.
La planification des employés est un exemple de problème bien adapté à CP.
Ce problème survient lorsque les entreprises qui fonctionnent en continu, telles que les usines, doivent créer des plannings hebdomadaires pour leurs employés. Voici un exemple très simplifié: une entreprise exécute trois quarts de travail de 8 heures par jour et attribue trois de ses quatre employés à des quarts différents chaque jour, tout en laissant le quatrième jour de congé. Même dans ce petit cas, le nombre de plannings possibles est énorme: chaque jour, il y a 4! = 4 * 3 * 2 * 1 = 24 affectations possibles de collaborateurs ; le nombre d'emplois hebdomadaires possibles est donc de 247, soit plus de 4, 5 milliards.
Généralement, d'autres contraintes limitent le nombre de solutions réalisables. Par exemple, chaque employé doit travailler au moins un nombre minimum de jours par semaine. La méthode CP suit les solutions qui restent réalisables lorsque vous ajoutez de nouvelles contraintes, ce qui en fait un outil puissant pour résoudre des problèmes de planification importants et concrets.
La communauté CP est très active et très répandue dans le monde entier, avec des revues scientifiques dédiées, des conférences et un arsenal de différentes techniques de résolution. Elle a été appliquée avec succès à la planification, à la planification et à de nombreux autres domaines présentant des contraintes hétérogènes.
Outils
Google propose plusieurs solutions pour résoudre les problèmes liés à la propriété CP:
- Résolution de contrainte CP-SAT: outil de programmation de contraintes qui utilise des méthodes SAT (satisfiabilité).
- Outil de résolution de CP d'origine: résolveur de programmation de contraintes utilisé dans la bibliothèque de routage.
Si votre problème peut être modélisé avec un objectif linéaire et des contraintes linéaires, il s'agit d'un problème de programmation linéaire. Nous vous conseillons d'utiliser MPSolver. (Toutefois, les problèmes d'itinéraire sont généralement résolus à l'aide de notre bibliothèque de routage de véhicules, même s'ils peuvent être représentés avec un modèle linéaire.)
Exemples
La section suivante décrit le résolveur CP-SAT, le résolveur principal OR-Tools pour la programmation de contraintes. (SAT signifie satisfiability: le résolveur utilise des techniques pour résoudre les problèmes SAT avec des méthodes CP.)
Voici quelques exemples de problèmes de planification adaptés au résolveur CP-SAT:
Les deux problèmes CP classiques sont le problème N-queens et les énigmes cryptarithmétiques.