CP-SAT Assignment Example¶

Overview¶

This example demonstrates using OR-Tools CP-SAT (Constraint Programming) solver with LumiX for combinatorial optimization. CP-SAT excels at pure integer and binary problems like assignment, scheduling, and routing.

The worker-task assignment problem optimally assigns tasks to workers to minimize total cost while respecting capacity constraints.

Problem Description¶

Assign tasks to workers to minimize total cost while respecting constraints.

Objective: Minimize total assignment cost.

Constraints:

Task coverage: Each task assigned to exactly one worker
Worker capacity: Each worker has maximum number of tasks they can handle
Skill matching: Costs vary based on worker-task compatibility

Mathematical Formulation¶

Decision Variables:

\[x_{w,t} \in \{0,1\}, \quad \forall w \in \text{Workers}, t \in \text{Tasks}\]

where \(x_{w,t} = 1\) if worker \(w\) is assigned to task \(t\).

Objective Function:

\[\text{Minimize} \quad \sum_{w \in \text{Workers}} \sum_{t \in \text{Tasks}} \text{cost}_{w,t} \cdot x_{w,t}\]

where \(\text{cost}_{w,t} = \text{hourly\_rate}_w \times \text{duration}_t \times \text{skill\_factor}\).

Constraints:

Task Coverage (exactly one worker per task):

\[\sum_{w \in \text{Workers}} x_{w,t} = 1, \quad \forall t \in \text{Tasks}\]
Worker Capacity:

\[\sum_{t \in \text{Tasks}} x_{w,t} \leq \text{max\_tasks}_w, \quad \forall w \in \text{Workers}\]

Key Features¶

Binary Assignment Variables¶

Multi-indexed binary variables for (worker, task) pairs:

    1. How to use CP-SAT solver with LumiX
    2. How to create binary variables for assignment problems
    3. How to use cartesian product indexing for worker-task pairs
    4. How to formulate coverage and capacity constraints
    5. How to interpret assignment problem solutions

See Also:
    - Example 02 (driver_scheduling): Multi-model indexing with dates
    - Example 01 (production_planning): Single-model indexing basics

Key Points:

CP-SAT requires integer variables (use .binary() not .continuous())
Cartesian product creates one variable per (worker, task) pair
Efficient for combinatorial optimization

Equality Constraints¶

Each task assigned to exactly one worker:

solver_to_use = "cpsat"

# ==================== MODEL BUILDING ====================


def build_assignment_model() -> Tuple[LXModel, LXVariable]:
    """Build the worker-task assignment optimization model using CP-SAT.

    This function constructs an integer programming model to minimize the total
    cost of assigning tasks to workers while respecting task coverage requirements
    and worker capacity constraints.

The .eq().rhs(1) ensures exactly one assignment per task.

Integer Cost Coefficients¶

CP-SAT works best with integer coefficients:

def get_assignment_cost(worker: Worker, task: Task) -> int:
    base_cost = worker.hourly_rate * task.duration_hours

    # Skill matching bonus/penalty
    if task.required_skill in worker.skills:
        return int(base_cost * 0.8)  # 20% discount
    else:
        return int(base_cost * 1.2)  # 20% penalty

CP-SAT Solver Options¶

Configure CP-SAT solver parameters:

solution = optimizer.solve(
    model,
    time_limit=10.0,           # Maximum solve time (seconds)
    num_search_workers=4,      # Parallel search threads
    log_search_progress=True   # Display search progress
)

Running the Example¶

Prerequisites:

pip install lumix
pip install ortools

Run:

cd examples/05_cpsat_assignment
python cpsat_assignment.py

Expected Output:

======================================================================
LumiX Example: Worker-Task Assignment with CP-SAT
======================================================================

Workers:
----------------------------------------------------------------------
  Alice       : $50/hr, max 3 tasks
  Bob         : $40/hr, max 4 tasks
  Charlie     : $60/hr, max 2 tasks

Tasks:
----------------------------------------------------------------------
  Database Migration       : 8h, priority 9/10
  API Development          : 12h, priority 8/10
  UI Redesign              : 6h, priority 7/10

======================================================================
SOLUTION
======================================================================
Status: OPTIMAL
Total Cost: $1,680
Solve Time: 0.123s

Optimal Assignment:
----------------------------------------------------------------------
  Alice        → Database Migration        (8h, $320)
  Alice        → UI Redesign               (6h, $240)
  Bob          → API Development           (12h, $384)
  Charlie      → Testing & QA              (10h, $480)

Worker Utilization:
----------------------------------------------------------------------
  Alice       : 2/3 tasks ( 66.7% capacity)
  Bob         : 2/4 tasks ( 50.0% capacity)
  Charlie     : 1/2 tasks ( 50.0% capacity)

Complete Code Walkthrough¶

Step 1: Create Assignment Variables¶

    1. How to use CP-SAT solver with LumiX
    2. How to create binary variables for assignment problems
    3. How to use cartesian product indexing for worker-task pairs
    4. How to formulate coverage and capacity constraints
    5. How to interpret assignment problem solutions

See Also:
    - Example 02 (driver_scheduling): Multi-model indexing with dates
    - Example 01 (production_planning): Single-model indexing basics

Step 2: Set Objective¶

    continuous variables, use solvers like OR-Tools LP, Gurobi, or CPLEX.
"""

from dataclasses import dataclass
from typing import Tuple

Step 3: Add Task Coverage Constraints¶

from sample_data import TASKS, WORKERS, Task, Worker, get_assignment_cost

solver_to_use = "cpsat"

# ==================== MODEL BUILDING ====================

def build_assignment_model() -> Tuple[LXModel, LXVariable]:
    """Build the worker-task assignment optimization model using CP-SAT.

    This function constructs an integer programming model to minimize the total
    cost of assigning tasks to workers while respecting task coverage requirements
    and worker capacity constraints.

Step 4: Add Worker Capacity Constraints¶

    Returns:
        A tuple containing:
            - LXModel: The optimization model with variables, objective, and constraints
            - LXVariable: The assignment variable family for solution access

    Example:
        >>> model, assignment = build_assignment_model()
        >>> print(model.summary())
        >>> optimizer = LXOptimizer().use_solver("cpsat")
        >>> solution = optimizer.solve(model)
        >>> # Access assignments
        >>> for (w_id, t_id), value in solution.get_mapped(assignment).items():
        ...     if value > 0.5:  # Assignment is active

Step 5: Solve and Access Solution¶

optimizer = LXOptimizer().use_solver("cpsat")
solution = optimizer.solve(model)

# Access multi-indexed assignments
for (worker_id, task_id), value in solution.get_mapped(assignment).items():
    if value > 0.5:  # Binary variable is "on"
        worker = worker_by_id[worker_id]
        task = task_by_id[task_id]
        print(f"{worker.name} → {task.name}")

Learning Objectives¶

After completing this example, you should understand:

CP-SAT Solver: When and why to use constraint programming
Binary Assignment: Modeling assignment problems with 0/1 variables
Equality Constraints: Using .eq() for exact assignment requirements
Integer Costs: Working with integer coefficients for CP-SAT
Solver Options: Configuring time limits and parallel search
Solution Interpretation: Extracting assignments from binary solutions

Common Patterns¶

Pattern 1: Binary Assignment Matrix¶

assignment = (
    LXVariable[Tuple[A, B], int]("assignment")
    .binary()
    .indexed_by_product(
        LXIndexDimension(A, lambda a: a.id).from_data(DATA_A),
        LXIndexDimension(B, lambda b: b.id).from_data(DATA_B)
    )
)

Pattern 2: Exactly-One Constraint¶

# Each B assigned to exactly one A
for b in B_SET:
    expr = LXLinearExpression().add_multi_term(
        assignment,
        coeff=lambda a, b_var: 1.0,
        where=lambda a, b_var: b_var.id == b.id
    )
    model.add_constraint(
        LXConstraint(f"coverage_{b.id}")
        .expression(expr)
        .eq()
        .rhs(1)
    )

Pattern 3: Capacity Constraint¶

# Each A can handle at most max[a] items from B
for a in A_SET:
    expr = LXLinearExpression().add_multi_term(
        assignment,
        coeff=lambda a_var, b: 1.0,
        where=lambda a_var, b: a_var.id == a.id
    )
    model.add_constraint(
        LXConstraint(f"capacity_{a.id}")
        .expression(expr)
        .le()
        .rhs(a.max_items)
    )

CP-SAT vs Linear Programming¶

When to Use CP-SAT¶

Use CP-SAT when:

✓ Pure integer/binary variables (no continuous)
✓ Combinatorial optimization (assignment, scheduling, routing)
✓ Logical constraints (AllDifferent, Circuit)
✓ Small to medium problems

Use LP/MIP when:

✗ Continuous variables needed
✗ Very large linear programs
✗ Need continuous relaxations

Performance Comparison¶

Problem Size	CP-SAT	MIP Solver
Small (< 100)	Very Fast	Very Fast
Medium (100-10k)	Fast	Fast to Medium
Large (> 10k)	Slow	Variable

Extending the Example¶

Try These Modifications¶

Add Skill Requirements: Multiple skills per task

.where_multi(lambda w, t: t.required_skill in w.skills)

Precedence Constraints: Some tasks must complete before others
Team Assignments: Assign groups of workers to tasks
Time Windows: Tasks must be done in certain periods
Preferences: Soft constraints for worker preferences

Next Steps¶

After mastering this example:

Example 02 (Driver Scheduling): Multi-model indexing foundation
Example 03 (Facility Location): Mixed-integer with Big-M
CP-SAT Documentation: OR-Tools CP-SAT advanced features

Files in This Example¶

cpsat_assignment.py - Main optimization model and solution display
sample_data.py - Data models (Worker, Task) and cost calculations
README.md - Detailed documentation and usage guide