Constraint Programming

In CP, you state what the problem is, not how to solve it. The model consists of:

• Variables: Decision points with finite domains (e.g., integers, sets)
• Constraints: Logical or arithmetic relations between variables (e.g., x + y < z, alldifferent(array))
• Objective: An optional expression to minimize or maximize

The solver handles the search strategy, freeing you from designing complex heuristics. This separation of model and algorithm allows rapid iteration on problem formulations.

The engine of CP efficiency. Propagation algorithms, or propagators, actively reduce the domains of variables by removing values that cannot participate in any solution.

• Arc Consistency: A fundamental propagation technique ensuring every value in a variable's domain has a supporting value in connected variables
• Global Constraints: Specialized propagators for common patterns like alldifferent, cumulative, or circuit that provide stronger, faster inference than decomposing them into basic constraints
• Propagation happens after every decision, pruning the search space dramatically before backtracking occurs

When propagation alone cannot find a solution or prove optimality, the solver performs a controlled search:

• Branching: Selects an unassigned variable and splits its domain (e.g., x ≤ 5 vs. x > 5)
• Backtracking: If a dead-end is reached (empty domain or violated constraint), the solver undoes decisions and tries alternatives
• Restart Strategies: Modern solvers periodically restart the search to escape unfruitful branches, guided by learned information from previous failures
• This combination of propagation and search is complete — it will find a solution if one exists or prove infeasibility

CP solvers provide a rich catalog of reusable, high-level constraints that capture common combinatorial structures:

• alldifferent: All variables in a collection must take distinct values — essential for scheduling and assignment
• cumulative: Models resource usage over time, ensuring tasks don't exceed capacity — foundational for job-shop scheduling
• element: Indexes into an array with a variable, linking discrete choices to costs or resources
• table: Enforces that a tuple of variables matches one of a set of allowed combinations
• These constraints encapsulate efficient propagation algorithms, letting modelers express complex logic concisely

To find not just any solution but the best one, CP uses branch-and-bound:

• Once a feasible solution is found, its objective value becomes a bound
• A new constraint is posted: future solutions must improve upon this bound (e.g., cost < best_cost)
• The search continues, tightening the bound each time a better solution is discovered
• When the search space is exhausted, the last recorded solution is proven optimal
• This method is particularly effective when combined with strong propagation that quickly detects suboptimal branches

Modern CP solvers don't operate in isolation. They integrate with other optimization paradigms:

• CP-MILP Decomposition: Use CP for feasibility and logical constraints, MILP for linear objectives and continuous variables
• Large Neighborhood Search (LNS): A metaheuristic where CP solves a partially relaxed subproblem to improve an existing solution iteratively
• Warm Starting: Injecting a known good solution from a heuristic to accelerate the branch-and-bound process
• This hybridization leverages the strengths of each technique, making CP applicable to massive-scale industrial problems like workforce scheduling and vehicle routing

Modeling intricate job shop scheduling problems where thousands of orders must be sequenced across hundreds of machines with limited capacity. CP handles non-linear constraints like sequence-dependent setup times, tooling availability, and operator skill requirements that MILP solvers struggle to formulate.

• Minimizes makespan and tardiness simultaneously
• Enforces complex precedence constraints between operations
• Handles cumulative resource limits (e.g., total power draw)

Assigning employees to shifts while respecting labor regulations, union rules, and individual preferences. CP solvers propagate constraints like 'no employee works more than 6 consecutive days' or 'at least 2 senior staff per night shift' to find feasible rosters in seconds.

• Balances fairness metrics across teams
• Models skill hierarchies (nurse, charge nurse, specialist)
• Adapts to sick leave and unexpected absences dynamically

Determining how to pack heterogeneous items into containers, trucks, or pallets to minimize wasted space and transportation cost. CP's global constraints for packing problems efficiently prune the search space where items have complex stacking rules, weight distributions, and fragility classifications.

• Handles 3D spatial constraints with rotation
• Enforces weight distribution for axle limits
• Respects hazardous material segregation rules

Choosing suppliers to fulfill multi-item purchase orders under volume discounts, minimum order quantities, and geographic sourcing requirements. CP models the combinatorial explosion of supplier-item combinations and finds cost-optimal allocations that satisfy all business rules.

• Models tiered pricing structures
• Enforces dual-sourcing for risk mitigation
• Respects carbon budget constraints per supplier

Scheduling preventive maintenance for critical infrastructure like power plants, refineries, or conveyor systems while ensuring continuous operations. CP coordinates overlapping resource requirements (cranes, specialized crews) and enforces safety intervals between conflicting tasks.

• Minimizes production loss during outages
• Models resource calendars with unavailability periods
• Handles conditional dependencies (task B only if task A reveals wear)

Solving Vehicle Routing Problems with complex side constraints that go beyond standard VRP solvers. CP handles time windows, driver hours-of-service regulations, compartmentalized vehicles for multi-temperature goods, and pickup-and-delivery pairings with precedence.

• Models heterogeneous fleets with different capacities
• Enforces customer priority and SLA tiers
• Integrates real-time traffic as soft constraints

The foundational mathematical structure underlying constraint programming. A CSP is defined by a set of variables, each with a domain of possible values, and a set of constraints that restrict allowable value combinations.

• Goal: Find any single valid assignment, not necessarily an optimal one.
• Difference from CP: CP extends CSPs by adding an objective function to optimize.
• Example: Sudoku is a pure CSP; scheduling a factory to minimize cost is a CP problem.

An alternative optimization paradigm that minimizes a linear objective function subject to linear constraints, where some variables are restricted to integer values. MILP uses a completely different solving mechanism than CP.

• Solver: Typically uses Branch and Bound with linear relaxations.
• Strength: Excels when the problem structure is predominantly linear.
• CP vs. MILP: CP is often superior for highly combinatorial, non-linear scheduling and routing problems with complex logical constraints.

A classic combinatorial optimization challenge and a prime application for constraint programming. The VRP seeks to determine the optimal set of routes for a fleet of vehicles to service a geographically dispersed set of customers.

• Constraints: Vehicle capacity, time windows, driver shift limits.
• Objective: Minimize total distance, time, or number of vehicles.
• CP Advantage: CP handles the complex logical side constraints (e.g., 'if customer A, then not customer B on same route') more naturally than MILP.

A manufacturing optimization problem where a set of jobs, each consisting of a sequence of operations, must be processed on a set of machines. Each operation requires a specific machine for a fixed duration.

• Constraints: Precedence (operation order), machine capacity (one job at a time).
• Objective: Typically minimize makespan (total completion time).
• CP Role: CP is a dominant technique here due to its ability to model disjunctive constraints (machine cannot process two jobs simultaneously) directly.

An exact algorithm paradigm for solving discrete optimization problems by systematically exploring a search tree. The algorithm partitions the solution space (branching) and calculates optimistic estimates (bounds) for each subproblem.

• Pruning: If a subproblem's best possible outcome is worse than the current best known solution, the entire branch is discarded.
• CP Integration: Modern CP solvers embed branch and bound to find optimal solutions, not just feasible ones, by minimizing an objective variable.

A method for solving complex problems by breaking them into simpler overlapping subproblems, solving each subproblem once, and storing the solution in a table for reuse. It relies on the principle of optimal substructure.

• Key Difference: CP is declarative (state the rules, solver finds the answer). DP is procedural (define the recursive relationship).
• Use Case: DP excels at problems like the Knapsack Problem or inventory optimization over time, while CP excels at highly constrained scheduling.