Constraint Programming

In CP, you define what must hold, not how to compute it. A model consists of:

• Variables: decision points with finite domains (e.g., a delivery truck's next stop from a set of 50 locations)
• Domains: the possible values each variable can take
• Constraints: logical or arithmetic relations linking variables (e.g., all_different, cumulative, element)

The solver autonomously determines the search strategy, freeing the developer from procedural algorithm design.

Propagation is the core inference mechanism that actively prunes impossible values from variable domains before search begins.

• When a variable's domain shrinks, constraints are re-evaluated to propagate the consequences
• Arc consistency algorithms like AC-3 ensure every value in a binary constraint has support
• Global constraints (e.g., alldifferent) use specialized, efficient propagation algorithms
• Propagation dramatically reduces the search space, often by orders of magnitude, before any branching occurs

Global constraints encapsulate recurring combinatorial substructures with dedicated, high-performance filtering algorithms.

• alldifferent(x1, x2, ..., xn): enforces that all variables take distinct values, using bipartite matching for propagation
• cumulative(tasks, heights, capacity): models resource usage over time, essential for scheduling
• element(index, array, value): links an index variable to an array lookup, enabling variable indexing
• circuit(successors): enforces a Hamiltonian cycle, critical for TSP and VRP formulations

These constraints provide both expressive power and computational efficiency.

After propagation reaches a fixpoint, the solver branches on remaining undecided variables using depth-first search with chronological backtracking.

• Variable ordering heuristics: choose the most constrained variable first (e.g., smallest domain, first-fail principle)
• Value ordering heuristics: try values most likely to succeed first (e.g., indomain_min)
• When a dead-end is reached (empty domain), the solver backtracks to the last choice point
• Lazy clause generation: modern CP solvers (e.g., OR-Tools CP-SAT) learn nogoods from failures, combining CP propagation with SAT-style clause learning for dramatic speedups

CP and Mixed-Integer Linear Programming (MILP) excel in different problem structures:

• CP strengths: highly combinatorial problems with complex logical constraints, sequencing, and scheduling (e.g., VRP with time windows, employee rostering)
• MILP strengths: problems with a strong linear relaxation and continuous variables (e.g., network flow, production planning)
• CP weakness: problems where the objective function drives the search and there is no tight combinatorial structure
• Modern solvers like OR-Tools CP-SAT integrate both paradigms, using linear relaxation for the objective while applying CP propagation for feasibility

CP is the dominant paradigm for complex scheduling due to its native handling of temporal and resource constraints:

• Interval variables: represent tasks with optional execution, start/end times, and duration
• Precedence constraints: enforce end_before_start or start_before_start relationships
• Cumulative resource constraints: limit concurrent resource consumption (e.g., a fleet of 10 trucks cannot be assigned to more than 10 simultaneous deliveries)
• Alternative resources: model a task that can execute on one of several machines
• Real-world example: optimizing a Dial-a-Ride Problem (DARP) with maximum ride time constraints and heterogeneous vehicle fleets

When exact CP solvers hit a computational wall on massive-scale problems, metaheuristics take over. These are high-level search strategies that find near-optimal solutions quickly:

• Adaptive Large Neighborhood Search (ALNS): Iteratively destroys and repairs parts of a solution, using CP-like propagation to ensure feasibility during repair.
• Genetic Algorithms: Evolve populations of routes using crossover and mutation.
• Simulated Annealing: Escapes local optima by probabilistically accepting worse solutions. CP is often embedded inside these frameworks to verify constraint satisfaction during the search.

The foundational exact algorithm shared by both CP and MILP solvers. The process systematically partitions the search space (branching) and computes bounds on the best possible solution in each partition. In CP, bounding is often done via constraint propagation—deducing that certain variable assignments are impossible and pruning them. In MILP, bounding relies on solving a relaxed linear program. Modern solvers blur the line, using propagation to tighten MILP bounds and linear relaxations to guide CP search.

A Digital Twin is a virtual replica of a physical logistics network that mirrors its real-time state. CP solvers are embedded within the twin to answer complex what-if questions: 'If I add this new order, can I still satisfy all delivery windows?' The twin feeds the current state (vehicle positions, pending orders, traffic) into the CP model, which then finds a feasible or optimal re-plan. This enables prescriptive analytics—not just predicting a delay, but automatically computing the best re-routing action.