Learning Constraint Programming

Hi, dear reader!

CP

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:

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:

What Is Constraint Programming? Finally!

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

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:

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!