Constraint Optimization

Model and solve constraint satisfaction and optimization problems.

Installation

pip install ortools

Quick Start

from ortools.sat.python import cp_model

def create_cp_model():
    """Create a basic constraint programming model."""
    model = cp_model.CpModel()

    # Create variables
    x = model.NewIntVar(0, 100, 'x')
    y = model.NewIntVar(0, 100, 'y')

    # Add constraints
    model.Add(x + y <= 150)
    model.Add(x >= 10)

    # Set objective
    model.Maximize(2 * x + 3 * y)

    # Solve
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        return solver.Value(x), solver.Value(y)
    return None

Common Patterns

Variable Types

# Integer variable
x = model.NewIntVar(0, 100, 'x')

# Boolean variable
b = model.NewBoolVar('b')

# Interval variable (for scheduling)
interval = model.NewIntervalVar(start, size, end, 'interval')

# Optional interval
opt_interval = model.NewOptionalIntervalVar(start, size, end, presence, 'opt')

Constraint Types

# Linear constraints
model.Add(x + 2*y <= 100)
model.Add(x != y)

# Boolean constraints
model.AddBoolOr([b1, b2, b3])
model.AddBoolAnd([b1, b2])
model.AddImplication(b1, b2)  # if b1 then b2

# All different constraint
model.AddAllDifferent([x, y, z])

# Element constraint (indexing)
model.AddElement(index, values, target)  # target = values[index]

Capacity Constraints

def add_capacity_constraint(model, items, bins, capacities, weights):
    """Assign items to bins respecting capacity."""
    assignment = {}
    for item in items:
        assignment[item] = model.NewIntVar(0, len(bins)-1, f'item_{item}')

    for bin_id, capacity in enumerate(capacities):
        bin_items = []
        for item in items:
            is_in_bin = model.NewBoolVar(f'{item}_in_{bin_id}')
            model.Add(assignment[item] == bin_id).OnlyEnforceIf(is_in_bin)
            model.Add(assignment[item] != bin_id).OnlyEnforceIf(is_in_bin.Not())
            bin_items.append((is_in_bin, weights[item]))

        model.Add(sum(b * w for b, w in bin_items) <= capacity)

    return assignment

Precedence Constraints

def add_precedence(model, task_starts, task_durations, precedences):
    """Add precedence constraints: task A must finish before task B starts."""
    for (a, b) in precedences:
        model.Add(task_starts[a] + task_durations[a] <= task_starts[b])

Disjunctive Constraints (No Overlap)

def add_no_overlap(model, intervals):
    """Ensure intervals don't overlap (one resource)."""
    model.AddNoOverlap(intervals)

def add_no_overlap_2d(model, x_intervals, y_intervals):
    """Ensure 2D rectangles don't overlap."""
    model.AddNoOverlap2D(x_intervals, y_intervals)

Objective Functions

# Minimize
model.Minimize(total_cost)

# Maximize
model.Maximize(total_profit)

# Multi-objective (weighted sum)
model.Minimize(alpha * cost + beta * time)

# Minimize maximum (makespan)
makespan = model.NewIntVar(0, horizon, 'makespan')
for end in task_ends:
    model.Add(makespan >= end)
model.Minimize(makespan)

Solving and Solution Extraction

def solve_with_hints(model, hints):
    """Solve model with solution hints."""
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 60
    solver.parameters.num_search_workers = 8

    # Add hints
    for var, value in hints.items():
        model.AddHint(var, value)

    status = solver.Solve(model)

    return {
        'status': solver.StatusName(status),
        'objective': solver.ObjectiveValue() if status == cp_model.OPTIMAL else None,
        'time': solver.WallTime()
    }