Constraint Programming — DO Concepts

Core idea

Constraint Programming (CP) solves combinatorial problems by declaring what must be true — constraints over decision variables — and letting a solver find values that satisfy all of them. The solver alternates between two operations: propagation (eliminating values from variable domains that cannot appear in any valid solution) and search (trying an assignment, then propagating its consequences).

Unlike Mixed-Integer Programming (MIP), which relaxes integer requirements to get continuous bounds and uses those bounds to prune the search tree, CP works directly in discrete domains. It has no objective function in the traditional sense — it finds a feasible solution, or proves none exists. When used for optimisation, CP adds a bound constraint and iterates.

CP's strength is rich constraint expressiveness. Global constraints like AllDifferent (no two variables take the same value) or Cumulative (resource capacity over time) encode entire families of problems in one declaration, enabling powerful propagation that MIP cannot replicate with linear constraints alone.

CP vs MIP — when to use each

Use CP when

The problem has rich combinatorial structure (scheduling, sequencing, configuration), feasibility is the hard part, or natural constraints don't linearise cleanly. CP excels at nurse rostering, job shop scheduling, and exam timetabling.

Use MIP when

The objective is linear or quadratic and the LP relaxation provides useful bounds. MIP excels at network design, production planning, and problems where strong lower bounds accelerate proof of optimality.

Concrete example

Scenario — nurse shift scheduling

A hospital has 10 nurses and must cover 3 shifts per day for 7 days. Each nurse must have at least 2 rest days, cannot work two consecutive night shifts, and must not work a night shift followed by a morning shift the next day.

How CP solves it: Each day-shift slot is a variable with domain {Nurse 1, …, Nurse 10}. The solver propagates: assigning Nurse A to Monday night immediately eliminates Nurse A from Tuesday morning and Tuesday night. Each assignment reduces remaining domains, often ruling out large branches of the search tree before any explicit search.

Why not MIP? The "no consecutive nights" rule and coverage requirements can be linearised, but the propagation CP achieves through global constraints finds infeasibility far earlier in the search — typically 10–100x faster on pure scheduling instances.

Where this shows up

Nurse rostering

The canonical CP application. Rich contractual constraints map directly to CP's global constraint library.

Job shop scheduling

Machine assignment and sequencing with disjunctive constraints. CP's Disjunctive global constraint handles this natively.

Exam timetabling

No student sits two exams simultaneously; rooms have capacity. AllDifferent and Cumulative constraints apply directly.

LNS repair step

In Large Neighbourhood Search, CP is commonly used as the exact repair solver for the destroyed subproblem.

Configuration

Product configurators with compatibility rules — which components can coexist. Pure feasibility, no cost objective needed.

Crew scheduling

Airline and rail crew assignment with rest rules, qualification constraints, and union agreements.

One-line version

CP propagation often finds infeasibility faster than MIP branch-and-bound. The choice between CP and MIP depends on whether the problem has more combinatorial structure (favour CP) or a tighter linear relaxation (favour MIP).

Related concepts