constraint-programming

name

constraint-programming

description

When the user wants to solve complex scheduling, allocation, or combinatorial problems using constraint programming (CP). Also use when the user mentions "constraint programming," "CP-SAT," "constraint satisfaction," "all-different constraint," "global constraints," "propagation," "search strategies," or when the problem has complex logical constraints, scheduling with disjunctive resources, or allocation problems. For MIP, see optimization-modeling. For metaheuristics, see metaheuristic-optimization.

Constraint Programming

You are an expert in constraint programming for supply chain optimization. Your goal is to help solve complex combinatorial problems using constraint propagation, global constraints, and intelligent search strategies that excel where traditional MIP struggles.

Initial Assessment

Before applying constraint programming, understand:

1. Problem Characteristics

   • Type? (scheduling, allocation, sequencing, assignment)
   • Constraints complex or logical? (if-then, all-different, etc.)
   • Variables: discrete domains?
   • Many feasibility constraints vs. optimization?

2. Why Constraint Programming

   • MIP formulation too weak?
   • Scheduling with disjunctive resources?
   • Complex logical constraints?
   • Need to find feasible solution quickly?

3. Problem Size

   • Number of variables?
   • Domain sizes?
   • Number of constraints?
   • Time limit for solving?

4. Technical Environment

   • CP solver available? (OR-Tools, Gecode, MiniZinc)
   • Need integrated with other systems?
   • Optimization or just feasibility?

---

Constraint Programming Fundamentals

Core Concepts

Variables: Decision variables with discrete domains

# Example: Variable x can take values 1, 2, or 3
x ∈ {1, 2, 3}

Constraints: Relations that must hold between variables

# Example: x + y ≤ 10
# Example: AllDifferent([x, y, z])

Propagation: Reduce variable domains based on constraints

# If x + y ≤ 10 and x = 8, then propagate y ≤ 2

Search: Systematic exploration with backtracking

# Try x = 1, check consistency, recurse
# If inconsistent, backtrack and try x = 2

---

Job Shop Scheduling with CP

Implementation with OR-Tools CP-SAT

from ortools.sat.python import cp_model
import matplotlib.pyplot as plt
import numpy as np
from typing import List, Tuple, Dict

class CPJobShopScheduler:
    """
    Job Shop Scheduling using Constraint Programming

    Problem: Schedule jobs on machines minimizing makespan
    Each job has sequence of operations on specific machines
    """

    def __init__(self,
                 jobs: List[List[Tuple[int, int]]],
                 time_limit_seconds: int = 60):
        """
        Initialize CP Job Shop Scheduler

        jobs: list of jobs, each job is list of (machine, duration)
              Example: [[(0, 3), (1, 2), (2, 2)],  # Job 0
                       [(0, 2), (2, 1), (1, 4)]]   # Job 1
        """

        self.jobs = jobs
        self.n_jobs = len(jobs)
        self.n_machines = max(max(op[0] for op in job) for job in jobs) + 1
        self.time_limit = time_limit_seconds

        # CP model
        self.model = cp_model.CpModel()

        # Decision variables
        self.job_starts = []  # [job][operation] -> start time variable
        .job_ends = []    
        .job_intervals = []  

        .makespan = 
        .solution = 

     ():
        

        
        horizon = (duration  job  .jobs
                      machine, duration  job)

        ()
        ()
        ()

        
         job_id, job  (.jobs):
            job_start_vars = []
            job_end_vars = []
            job_interval_vars = []

             op_id, (machine, duration)  (job):
                
                suffix = 

                
                start_var = .model.NewIntVar(, horizon, )

                
                end_var = .model.NewIntVar(, horizon, )

                
                interval_var = .model.NewIntervalVar(
                    start_var, duration, end_var, 
                )

                job_start_vars.append(start_var)
                job_end_vars.append(end_var)
                job_interval_vars.append(interval_var)

            .job_starts.append(job_start_vars)
            .job_ends.append(job_end_vars)
            .job_intervals.append(job_interval_vars)

        
         job_id  (.n_jobs):
             op_id  ((.jobs[job_id]) - ):
                .model.Add(
                    .job_ends[job_id][op_id] <=
                    .job_starts[job_id][op_id + ]
                )

        
        machine_to_intervals = [[]  _  (.n_machines)]

         job_id, job  (.jobs):
             op_id, (machine, duration)  (job):
                machine_to_intervals[machine].append(
                    .job_intervals[job_id][op_id]
                )

        
         machine  (.n_machines):
             machine_to_intervals[machine]:
                .model.AddNoOverlap(machine_to_intervals[machine])

        
        .makespan = .model.NewIntVar(, horizon, )

        
         job_id  (.n_jobs):
            last_op_idx = (.jobs[job_id]) - 
            .model.Add(
                .makespan >= .job_ends[job_id][last_op_idx]
            )

        .model.Minimize(.makespan)

        ()

     () -> :
        

        ()

        
        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = .time_limit

        
        solver.parameters.num_search_workers = 

        
        status = solver.Solve(.model)

        
         status == cp_model.OPTIMAL  status == cp_model.FEASIBLE:
            ()
            ()
            ()
            ()

            
            schedule = []
             job_id  (.n_jobs):
                 op_id, (machine, duration)  (.jobs[job_id]):
                    start = solver.Value(.job_starts[job_id][op_id])
                    end = solver.Value(.job_ends[job_id][op_id])

                    schedule.append({
                        : job_id,
                        : op_id,
                        : machine,
                        : start,
                        : end,
                        : duration
                    })

            .solution = {
                :   status == cp_model.OPTIMAL  ,
                : solver.Value(.makespan),
                : schedule,
                : solver.WallTime(),
                : solver.BestObjectiveBound(),
                : (solver.Value(.makespan) - solver.BestObjectiveBound()) /
                       solver.Value(.makespan) * 
            }

             .solution

        :
            ()
             {
                :   status == cp_model.INFEASIBLE  ,
                : ,
                : [],
                : solver.WallTime()
            }

     ():
        

          .solution   .solution[]:
            ()
            

        schedule = .solution[]

        fig, ax = plt.subplots(figsize=(, ))

        colors = plt.cm.Set3(np.linspace(, , .n_jobs))

         task  schedule:
            ax.barh(
                task[],
                task[],
                left=task[],
                height=,
                color=colors[task[]],
                edgecolor=,
                linewidth=
            )

            
            ax.text(
                task[] + task[] / ,
                task[],
                ,
                ha=,
                va=,
                fontsize=,
                fontweight=
            )

        ax.set_xlabel(, fontsize=)
        ax.set_ylabel(, fontsize=)
        ax.set_title(
            ,
            fontsize=
        )
        ax.set_yticks((.n_machines))
        ax.set_yticklabels([  i  (.n_machines)])
        ax.grid(, axis=, alpha=)

        
        legend_elements = [
            plt.Rectangle((,),,, fc=colors[i],
                         edgecolor=, label=)
             i  (.n_jobs)
        ]
        ax.legend(handles=legend_elements, loc=)

        plt.tight_layout()
        plt.show()



 __name__ == :
    
    jobs = [
        [(, ), (, ), (, ), (, ), (, ), (, )],
        [(, ), (, ), (, ), (, ), (, ), (, )],
        [(, ), (, ), (, ), (, ), (, ), (, )],
        [(, ), (, ), (, ), (, ), (, ), (, )],
        [(, ), (, ), (, ), (, ), (, ), (, )],
        [(, ), (, ), (, ), (, ), (, ), (, )]
    ]

    
    scheduler = CPJobShopScheduler(jobs, time_limit_seconds=)

    
    scheduler.build_model()
    result = scheduler.solve()

    
     result[]  [, ]:
        ()
        ()
        ()

        
        scheduler.plot_gantt()

---

Nurse Scheduling with Global Constraints

from ortools.sat.python import cp_model
from typing import List, Dict
import pandas as pd

class NurseSchedulingCP:
    """
    Nurse Scheduling using Constraint Programming

    Constraints:
    - Shift coverage requirements
    - No overlapping shifts for same nurse
    - Rest periods between shifts
    - Fair distribution of shifts
    - Skill requirements
    """

    def __init__(self,
                 num_nurses: int,
                 num_days: int,
                 shifts: List[str],
                 requirements: Dict,
                 time_limit: int = 60):
        """
        Initialize nurse scheduling model

        num_nurses: number of nurses
        num_days: scheduling horizon
        shifts: list of shift names (e.g., ['Morning', 'Evening', 'Night'])
        requirements: dict with {shift: required_nurses_per_day}
        """

        self.num_nurses = num_nurses
        self.num_days = num_days
        self.shifts = shifts
        self.num_shifts = len(shifts)
        self.requirements = requirements
        self.time_limit = time_limit

        self.model = cp_model.CpModel()
        self.schedule_vars = {}
        self.solution = None

    def build_model(self):
        """Build CP model for nurse scheduling"""

        print()
        ()
        ()

        
         n  (.num_nurses):
             d  (.num_days):
                 s  (.num_shifts):
                    .schedule_vars[(n, d, s)] = .model.NewBoolVar(
                        
                    )

        
         d  (.num_days):
             s  (.num_shifts):
                shift_name = .shifts[s]
                required = .requirements[shift_name]

                .model.Add(
                    (.schedule_vars[(n, d, s)]
                         n  (.num_nurses)) >= required
                )

        
         n  (.num_nurses):
             d  (.num_days):
                .model.Add(
                    (.schedule_vars[(n, d, s)]
                         s  (.num_shifts)) <= 
                )

        
        
        night_shift_idx = .shifts.index()    .shifts  -

         night_shift_idx >= :
             n  (.num_nurses):
                 d  (.num_days - ):
                    
                    night_works = .schedule_vars[(n, d, night_shift_idx)]

                     s  (.num_shifts):
                        .model.Add(
                            .schedule_vars[(n, d + , s)] == 
                        ).OnlyEnforceIf(night_works)

        
        
        min_shifts_per_nurse = (.num_days * (.requirements.values())) // .num_nurses - 
        max_shifts_per_nurse = min_shifts_per_nurse + 

         n  (.num_nurses):
            total_shifts = (
                .schedule_vars[(n, d, s)]
                 d  (.num_days)
                 s  (.num_shifts)
            )
            .model.Add(total_shifts >= min_shifts_per_nurse)
            .model.Add(total_shifts <= max_shifts_per_nurse)

        
        
         n  (.num_nurses):
             week  (.num_days // ):
                saturday = week *  + 
                sunday = week *  + 

                 saturday < .num_days  sunday < .num_days:
                    saturday_works = (
                        .schedule_vars[(n, saturday, s)]
                         s  (.num_shifts)
                    )
                    sunday_works = (
                        .schedule_vars[(n, sunday, s)]
                         s  (.num_shifts)
                    )

                    
                    

        ()

     () -> :
        

        ()

        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = .time_limit
        solver.parameters.num_search_workers = 

        status = solver.Solve(.model)

         status == cp_model.OPTIMAL  status == cp_model.FEASIBLE:
            ()
            ()

            
            schedule = []
             n  (.num_nurses):
                 d  (.num_days):
                     s  (.num_shifts):
                         solver.Value(.schedule_vars[(n, d, s)]) == :
                            schedule.append({
                                : n,
                                : d,
                                : .shifts[s]
                            })

            .solution = {
                :   status == cp_model.OPTIMAL  ,
                : schedule,
                : solver.WallTime()
            }

             .solution
        :
             {
                : ,
                : [],
                : solver.WallTime()
            }

     ():
        

          .solution   .solution[]:
            ()
            

        df_data = []
         item  .solution[]:
            df_data.append({
                : ,
                : item[],
                : item[]
            })

        df = pd.DataFrame(df_data)

        
        pivot = df.pivot_table(
            index=,
            columns=,
            values=,
            aggfunc=,
            fill_value=
        )

        ()
        (pivot)



 __name__ == :
    
    scheduler = NurseSchedulingCP(
        num_nurses=,
        num_days=,
        shifts=[, , ],
        requirements={
            : ,
            : ,
            : 
        },
        time_limit=
    )

    scheduler.build_model()
    result = scheduler.solve()

     result[]  [, ]:
        scheduler.print_schedule()

---

Global Constraints

AllDifferent Constraint

# Ensure all variables take different values
# Example: Assign workers to tasks, each worker gets different task
model.AddAllDifferent([task[worker] for worker in workers])

Cumulative Constraint

# Resource capacity constraint
# Sum of resource usage at any time ≤ capacity
from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Tasks with resource requirements
tasks = [...]
resource_usage = [...]
capacity = 10

# Create interval variables
intervals = []
demands = []

for i, (start, duration, demand) in enumerate(tasks):
    start_var = model.NewIntVar(0, 100, f'start_{i}')
    end_var = model.NewIntVar(0, 100, f'end_{i}')
    interval = model.NewIntervalVar(start_var, duration, end_var, f'interval_{i}')

    intervals.append(interval)
    demands.append(demand)

# Cumulative constraint
model.AddCumulative(intervals, demands, capacity)

Circuit Constraint

# Create Hamiltonian circuit (TSP, VRP)
# Variables represent next node in tour
model.AddCircuit([(i, next[i]) for i in nodes])

Table Constraint

# Variable tuple must match one of allowed tuples
# Example: (x, y, z) must be in {(1,2,3), (2,3,4), (3,4,5)}
allowed_tuples = [(1,2,3), (2,3,4), (3,4,5)]
model.AddAllowedAssignments([x, y, z], allowed_tuples)

Reservoir Constraint

# Track resource level over time (inventory, battery level)
# Starts at initial level, changes with events, stays within bounds
model.AddReservoirConstraint(
    times=[t1, t2, t3],
    demands=[d1, d2, d3],
    min_level=0,
    max_level=100
)

---

Search Strategies

Variable Selection

from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

# Define search strategy
model.AddDecisionStrategy(
    variables=[x, y, z],
    var_selection_strategy=cp_model.CHOOSE_FIRST,
    value_selection_strategy=cp_model.SELECT_MIN_VALUE
)

# Variable selection strategies:
# - CHOOSE_FIRST: static order
# - CHOOSE_LOWEST_MIN: smallest lower bound
# - CHOOSE_HIGHEST_MAX: largest upper bound
# - CHOOSE_MIN_DOMAIN_SIZE: smallest domain

Large Neighborhood Search (LNS)

# OR-Tools uses LNS automatically, but can customize
solver.parameters.num_search_workers = 8  # Parallel search
solver.parameters.log_search_progress = True

# Focus on improving incumbent
solver.parameters.optimize_with_core = True

---

CP vs MIP: When to Use CP

Use CP When:

• Complex logical constraints (if-then, reified constraints)
• Scheduling with disjunctive resources
• Finding feasible solution is primary goal
• Symmetry breaking difficult in MIP
• Need for global constraints (AllDifferent, Circuit)

Use MIP When:

• Linear objective and constraints
• Need dual bounds and gaps
• Warm starting important
• Well-studied problem class (network flow, etc.)

Use Hybrid When:

• Large problem with both CP and MIP characteristics
• CP for subproblem, MIP for master
• Decomposition possible

---

Tools & Libraries

Python CP Libraries

OR-Tools CP-SAT:

• Google's constraint solver
• Excellent performance
• Free and open-source
• Strong MIP-style search

MiniZinc:

• Modeling language for CP
• Multiple solver backends
• Good for prototyping

python-constraint:

• Simple CP library
• Good for learning
• Limited scalability

Commercial CP Solvers

IBM CPLEX CP Optimizer:

• Industrial-strength CP
• Integrated with CPLEX
• Scheduling-focused

Gecode:

• Open-source C++ CP toolkit
• Highly customizable
• Python bindings available

---

Common Challenges & Solutions

Challenge: Solution Quality Varies

Problem: CP finds feasible solution but quality varies run-to-run

Solutions:

• Run multiple times with different seeds
• Use LNS (large neighborhood search)
• Provide good initial solution
• Tune search strategies
• Use optimization objective (not just feasibility)

Challenge: No Solution Found

Problem: Solver returns infeasible or times out

Solutions:

• Relax constraints progressively
• Start with smaller problem
• Add solution hints
• Check for conflicting constraints
• Use relaxation variables with penalties

Challenge: Slow Performance

Problem: Solver takes too long

Solutions:

• Add implied constraints (redundant but helpful)
• Better search strategy
• Break symmetries
• Use cumulative/global constraints
• Parallelize search
• Time-limited solving

---

Best Practices

1. Model Incrementally: Start simple, add constraints gradually
2. Use Global Constraints: More efficient than decomposition
3. Break Symmetries: Add symmetry-breaking constraints
4. Provide Hints: Give solver good starting solution
5. Tune Search: Experiment with variable/value selection
6. Monitor Progress: Log search progress
7. Set Time Limits: Don't wait forever for optimality
8. Test on Small Instances: Verify model correctness

---

Output Format

CP Solution Report

Executive Summary:

• Problem solved
• Solution status (optimal/feasible/infeasible)
• Key results

Problem Details:

• Variables: count and types
• Constraints: count by type
• Global constraints used

Solution Quality:

Metric	Value
Status	OPTIMAL
Objective	145
Lower Bound	145
Gap	0%
Solve Time	12.3s
Failures	1,234
Branches	5,678

Solution:

• Detailed schedule/assignment
• Constraint satisfaction verification
• Resource utilization

---

Questions to Ask

1. What type of problem? (scheduling, allocation, routing)
2. What makes this hard? (logical constraints, disjunctive resources)
3. Is finding any feasible solution the goal, or optimization?
4. What are the key constraints?
5. How large is the problem?
6. Time limit for solving?
7. Need optimality guarantee or good-enough solution?

---

Related Skills

• optimization-modeling: For MIP approaches
• metaheuristic-optimization: For large-scale heuristics
• production-scheduling: For manufacturing scheduling
• route-optimization: For routing problems
• workforce-scheduling: For labor scheduling
• assembly-line-balancing: For line balancing
• job-shop-scheduling: For job shop problems