Learning Constraint Programming

Bonjour, cher lecteur !

Il paraît que tu souhaites apprendre la programmation par contraintes. :)

TL;DR : Cet article présente la programmation par contraintes et propose une liste de ressources pour l'apprendre. Passe directement aux ressources si tu veux aller à l'essentiel.

Qu'est-ce qu'un problème combinatoire ?

Un problème combinatoire consiste à sélectionner, ordonner, regrouper ou affecter des objets appartenant à un ensemble fini, tout en respectant un ensemble de conditions ou de contraintes. ScienceDirect

Une solution candidate est une combinaison des éléments du problème qui peut être examinée au cours de la recherche. Une solution valide est une solution candidate qui satisfait toutes les conditions imposées.

Pour une introduction plus détaillée, consulte Introduction: Combinatorial Problems and Search, page 4, par Holger H. Hoos et Thomas Stützle.

Les problèmes combinatoires apparaissent dans de nombreux domaines de l'informatique et dans de nombreuses applications concrètes, notamment :

la recherche du circuit le plus court ou le moins coûteux, comme dans le problème du voyageur de commerce (TSP) ;
la recherche de modèles de formules propositionnelles, comme dans les problèmes de satisfaisabilité booléenne (SAT) ;
la planification, l'ordonnancement et la création d'emplois du temps ;
le routage de paquets de données sur Internet ;
la prédiction de structures protéiques.

Qu'est-ce que l'optimisation combinatoire ?

L'optimisation combinatoire consiste à rechercher la meilleure solution parmi un ensemble fini, et souvent extrêmement vaste, de possibilités.

Une solution doit d'abord satisfaire les contraintes du problème. Parmi toutes les solutions réalisables, on cherche ensuite celle qui minimise ou maximise une fonction objectif, par exemple un coût, une distance, une durée ou un profit.

Ce domaine se situe à l'intersection des mathématiques, de l'informatique et de la recherche opérationnelle. Son objectif est non seulement de concevoir des algorithmes efficaces, mais aussi d'évaluer ou de certifier la qualité des solutions qu'ils produisent.

Pour aller plus loin, consulte les ressources de l'EPFL et de DeepAI.

L'optimisation combinatoire intervient notamment dans :

la logistique et l'optimisation des chaînes d'approvisionnement ;
la conception de réseaux aériens ;
l'affectation de taxis ou de véhicules de transport ;
la planification des livraisons de colis ;
l'affectation optimale de tâches à des personnes ;
la conception de réseaux de distribution d'eau ;
certains problèmes de sciences de la Terre, comme l'optimisation du débit des réservoirs.

Qu'est-ce que la programmation par contraintes ? Enfin !

La programmation par contraintes, ou CP pour Constraint Programming, est un paradigme permettant de résoudre des problèmes combinatoires en décrivant :

les variables du problème ;
les valeurs possibles de ces variables, appelées domaines ;
les contraintes que les solutions valides doivent satisfaire ;
éventuellement, un objectif à minimiser ou à maximiser.

Au lieu de décrire une suite d'instructions permettant de construire une solution, on décrit les propriétés que celle-ci doit posséder. Un solveur de contraintes utilise ensuite des techniques telles que la propagation de contraintes et la recherche pour trouver une ou plusieurs solutions.

La programmation par contraintes peut donc servir aussi bien à résoudre des problèmes de satisfaction de contraintes que des problèmes d'optimisation.

Consulte :

Quand utiliser la programmation par contraintes — et quand l'éviter

Utiliser la CP lorsque le problème se décrit plus naturellement par ses conditions

Un bon indice que la CP est adaptée est qu'il est plus naturel de décrire les conditions que doit satisfaire une solution valide que d'écrire les étapes nécessaires pour la construire.

Prenons un problème d'ordonnancement : chaque tâche doit commencer après celles dont elle dépend, deux tâches utilisant la même machine ne doivent pas se chevaucher, chaque employé a une disponibilité limitée et certaines opérations doivent avoir lieu dans une fenêtre de temps donnée. Ces règles se traduisent directement en contraintes. Le modèle indique ce qui doit être respecté, tandis que le solveur détermine comment explorer les affectations possibles.

La CP est donc particulièrement intéressante lorsque :

les décisions sont discrètes et reliées par des règles logiques riches ;
le problème comporte des contraintes d'ordonnancement, de routage, d'affectation, de placement ou de configuration ;
des contraintes globales comme allDifferent, cumulative, noOverlap ou circuit permettent d'exprimer une structure importante ;
il est important de trouver une solution réalisable, de prouver qu'il n'en existe aucune ou de prouver l'optimalité ;
les exigences changent souvent et le modèle doit rester facile à faire évoluer.

Rester prudent face aux très grandes instances

La taille d'une instance ne suffit pas, à elle seule, à déterminer si la CP sera efficace. Un grand modèle doté de contraintes fortes peut être résolu rapidement, car la propagation élimine de nombreuses valeurs impossibles avant la recherche. À l'inverse, un modèle plus petit avec des contraintes faibles, de grands domaines ou beaucoup de symétries peut produire un arbre de recherche immense.

Une approche CP générique peut rencontrer des difficultés face à des millions de variables, une propagation faible, des interactions très denses ou des exigences strictes de temps réel. Si le problème est principalement linéaire et continu, la programmation linéaire ou linéaire en nombres entiers peut être plus adaptée. Un problème possédant une structure particulière peut aussi mieux se prêter aux algorithmes de flot, aux solveurs SAT ou CP-SAT, à la programmation dynamique ou à une heuristique spécialisée.

Pour les instances à grande échelle, la réponse pratique n'est souvent pas d'abandonner la CP, mais de la combiner avec la décomposition, la rupture de symétries, des contraintes redondantes, la recherche à grand voisinage, la recherche locale ou la programmation mathématique. La bonne question n'est donc pas seulement « Quelle est la taille de l'instance ? », mais aussi « Quelle part de sa structure le solveur peut-il exploiter ? »

L'apprentissage peut guider la recherche

L'une des orientations récentes les plus intéressantes consiste à associer l'apprentissage automatique à la recherche combinatoire. Pendant la recherche, un solveur choisit successivement une variable, une valeur, une branche ou un voisinage à explorer. Ces décisions reposent traditionnellement sur des heuristiques génériques ou conçues manuellement. Lorsque de nombreuses instances similaires sont disponibles, un modèle peut plutôt apprendre quelles décisions conduisent le plus souvent à de bonnes solutions.

L'idée centrale n'est pas nécessairement de remplacer le solveur. La composante apprise oriente la recherche vers les régions prometteuses, tandis que le solveur de contraintes continue à garantir la faisabilité, à calculer des bornes et, lorsque la recherche est menée à son terme, à fournir des garanties exactes.

Par exemple, SeaPearl explore l'apprentissage par renforcement pour prendre les décisions de branchement au sein d'un solveur CP. D'autres travaux emploient des réseaux de neurones sur graphes comme heuristiques globales pour la satisfaction de contraintes, tandis que des recherches plus récentes utilisent l'apprentissage par renforcement pour réduire les arbres de recherche de la CP sur des problèmes d'ordonnancement.

Cette approche hybride est particulièrement prometteuse pour les familles de problèmes récurrents, dont les anciennes instances peuvent servir d'entraînement. Elle conserve toutefois certaines difficultés : l'entraînement peut être coûteux, les politiques apprises peuvent mal se généraliser à des instances différentes et l'inférence ajoute un surcoût. L'apprentissage reste donc un guide et non une garantie ; la recherche et la propagation demeurent essentielles.

Merci pour ta lecture !

Hi, dear reader!

I hear you want to learn constraint programming. :)

TL;DR: This article introduces constraint programming and provides a list of resources for learning it. Jump to the resources if you want to skip the definitions.

What Is a Combinatorial Problem?

A combinatorial problem involves selecting, arranging, grouping, or assigning objects from a finite set while respecting a collection of conditions or constraints. ScienceDirect

A candidate solution is any combination of the problem's components that may be considered during the search. A valid solution is a candidate that satisfies all the required conditions.

For a more detailed introduction, see Introduction: Combinatorial Problems and Search, page 4, by Holger H. Hoos and Thomas Stützle.

Combinatorial problems arise in many areas of computer science and in real-world applications, including:

finding the shortest or cheapest round trip, as in the travelling salesperson problem (TSP);
finding models of propositional formulae, as in Boolean satisfiability problems (SAT);
planning, scheduling, and timetabling;
routing data packets over the internet;
predicting protein structures.

What Is Combinatorial Optimisation?

Combinatorial optimisation is concerned with finding the best solution among a finite, and often extremely large, set of alternatives.

A solution must first satisfy the problem's constraints. Among all feasible solutions, we then look for one that minimises or maximises an objective function, such as cost, distance, time, or profit.

This field lies at the intersection of mathematics, computer science, and operations research. Its goal is not only to design efficient algorithms, but also to determine or certify the quality of the solutions they produce.

For further definitions, see the resources from EPFL and DeepAI.

Applications of combinatorial optimisation include:

logistics and supply-chain optimisation;
airline network design;
taxi and ride allocation;
package-delivery planning;
assigning jobs to people;
designing water-distribution networks;
earth-science problems such as reservoir flow-rate optimisation.

What Is Constraint Programming? Finally!

Constraint programming (CP) is a paradigm for solving combinatorial problems by describing:

the variables involved in the problem;
the possible values, or domains, of those variables;
the constraints that valid solutions must satisfy;
optionally, an objective to minimise or maximise.

Instead of describing a sequence of instructions for constructing a solution, we describe the properties that a solution must have. A constraint solver then uses techniques such as constraint propagation and search to find one or more solutions.

CP can therefore be used for both constraint-satisfaction and optimisation problems.

See:

When to Use CP — and When Not To

Use CP when the problem is easier to describe through conditions

A good sign that CP may be the right tool is that you can describe what a valid solution must satisfy more naturally than you can describe the steps needed to construct one.

Consider a scheduling problem: every task must start after its prerequisites, two tasks requiring the same machine must not overlap, each employee has a limited availability, and some operations must occur within a given time window. These statements translate directly into constraints. The model says what must hold, while the solver decides how to explore the possible assignments.

CP is therefore particularly attractive when:

decisions are discrete and interact through rich logical rules;
the problem contains scheduling, routing, assignment, packing, or configuration constraints;
global constraints such as allDifferent, cumulative, noOverlap, or circuit capture important structure;
finding a feasible solution, proving infeasibility, or proving optimality matters;
the requirements change often and the model needs to remain easy to extend.

Be careful with very large instances

The size of an instance alone does not determine whether CP will work well. A large model with strong constraints may be solved efficiently because propagation removes many impossible values before search. Conversely, a smaller model with weak constraints, large domains, or many symmetries may produce an enormous search tree.

Plain CP can struggle when there are millions of variables, very weak propagation, dense interactions, or strict real-time requirements. If the problem is mostly linear and continuous, linear or mixed-integer programming may be a better fit. Problems with a specialised structure may also benefit more from network-flow algorithms, SAT or CP-SAT solvers, dynamic programming, or a domain-specific heuristic.

For large-scale instances, the practical answer is often not to discard CP, but to combine it with decomposition, symmetry breaking, redundant constraints, large-neighbourhood search, local search, or mathematical programming. The right question is therefore not only "How large is the instance?", but also "How much structure can the solver exploit?"

Learning can guide the search

One of the most interesting recent directions combines machine learning with combinatorial search. During search, a solver repeatedly chooses a variable, a value, a branch, or a neighbourhood to explore. These decisions have traditionally been driven by generic or handcrafted heuristics. When many similar instances are available, a model can instead learn which decisions tend to lead towards good solutions.

The key idea is not necessarily to replace the solver. The learned component guides the search towards promising regions, while the constraint solver keeps enforcing feasibility, computing bounds, and, when the search is complete, providing exact guarantees.

For example, SeaPearl explores reinforcement learning for branching decisions inside a CP solver. Other work uses graph neural networks as global search heuristics for constraint satisfaction, while more recent research applies reinforcement learning to reduce CP search trees on scheduling problems.

This hybrid approach is especially promising for recurring problem families, where past instances provide useful training experience. It still comes with challenges: training can be expensive, learned policies may fail to generalise to different instances, and inference adds overhead. Learning is therefore a guide rather than a guarantee; search and propagation remain essential.

Thanks for reading!