Constraint Programming with OR-Tools CP-SAT

This notebook demonstrates the power of Constraint Programming (CP) using Google's OR-Tools CP-SAT solver for solving complex optimization problems. The notebook contains two main examples that showcase different approaches to constraint modeling.

🧩 What is Constraint Programming?

Constraint Programming is a declarative programming paradigm where you describe what must be true (constraints) rather than how to compute a solution. You define:

• Decision variables and their domains (e.g., x ∈ {0,…,9})
• Constraints that restrict which combinations of values are allowed
• Optional objective to minimize/maximize (e.g., total cost, performance)

The solver then searches for assignments that satisfy all constraints and optimizes the objective.

🔧 OR-Tools CP-SAT Solver

The Google OR-Tools CP-SAT solver is a modern, open-source constraint programming engine that excels at solving discrete, combinatorial problems. It combines:

• Constraint Programming (CP): For modeling complex logical constraints
• Boolean Satisfiability (SAT): For efficient search algorithms
• Pseudo-Boolean (PB): For handling weighted constraints
• Linear Constraint Generation (LCG): For advanced optimization

Key Features

• Integer-only variables: Works over integers (scale fractional values by multiplying)
• Multiple constraint types: AllDifferent, arithmetic, logical, cardinality
• Optimization support: Minimize/maximize objectives
• Solution enumeration: Find all feasible solutions
• Performance tuning: Configurable search strategies and time limits

Solver Status Values

Status	Description
OPTIMAL	An optimal feasible solution was found
FEASIBLE	A feasible solution was found, but may not be optimal
INFEASIBLE	The problem was proven infeasible
MODEL_INVALID	The model has errors
UNKNOWN	The solver couldn't determine feasibility

📚 Examples in This Notebook

1. 🧩 Sudoku Puzzle (Fixed Constraints)

Problem Type: Pure constraint satisfaction with fixed, immutable constraints

Objective: Find a valid solution that satisfies all Sudoku rules

Constraints (Fixed):

• Each row must contain digits 1–9 exactly once
• Each column must contain digits 1–9 exactly once
• Each 3×3 box must contain digits 1–9 exactly once
• Given clues fix specific cell values

Key Characteristics:

• ✅ Constraints are immutable - cannot be relaxed or modified
• ✅ Single objective - find any valid solution
• ✅ Deterministic rules - Sudoku rules are well-defined
• ✅ No trade-offs - either satisfies all constraints or fails

Code Structure:

def build_sudoku_model(puzzle_9x9):
    model = cp_model.CpModel()
    X = [[model.NewIntVar(1, 9, f"x_{r}_{c}") for c in range(9)] for r in range(9)]
    
    # Fixed constraints - never change
    for r in range(9):
        model.AddAllDifferent(X[r])  # Row constraint
    for c in range(9):
        model.AddAllDifferent([X[r][c] for r in range(9)])  # Column constraint
    # ... more fixed constraints
    
    return model, X

2. 🎯 Campaign Optimization (Flexible Constraints)

Problem Type: Multi-objective optimization with business-adjustable constraints

Objective: Maximize performance_weight × projected_performance + spend_weight × total_spend

Constraints (Business-Adjustable):

• Budget Constraint: Σ budget_alloc_i ≤ total_budget (adjustable budget)
• Cardinality Constraint: Σ x_i ≤ K (adjustable number of keywords)
• Per-keyword Cap: budget_alloc_i ≤ max_cap_ratio × total_budget (adjustable caps)
• Minimum Budget: budget_alloc_i ≥ min_budget × x_i (adjustable minimums)

Key Characteristics:

• 🔧 Constraints are flexible - can be adjusted based on business needs
• 🎯 Multi-objective - balance performance vs. budget utilization
• 📊 Business-driven - constraints reflect real-world limitations
• ⚖️ Trade-offs - different constraint settings produce different solutions

Code Structure:

def solve_budget_allocation_prop(preprocessed_df, budget_usd=1500.0, K=10, max_cap_ratio=0.15):
    # Flexible constraints - can be adjusted
    budget_cents = int(round(budget_usd * 100))  # Adjustable budget
    cap_cents = int(max_cap_ratio * budget_cents)  # Adjustable cap
    
    # Business constraints that can change
    m.Add(sum(x) == K)  # Adjustable cardinality
    m.Add(b1[i] <= cap_cents * x1[i])  # Adjustable per-keyword cap
    m.Add(T1 == sum(b1))  # Adjustable total spend

🔄 Comparison: Fixed vs. Flexible Constraints

Aspect	Sudoku (Fixed)	Campaign Optimization (Flexible)
Constraint Nature	Immutable rules	Business-adjustable parameters
Objective	Find any valid solution	Optimize multiple objectives
Solution Space	Binary (valid/invalid)	Continuous spectrum of solutions
Business Impact	None - pure logic	Direct impact on ROI and performance
Parameter Tuning	Not applicable	Critical for business success
Constraint Relaxation	Impossible	Common business practice

🚀 Getting Started

Prerequisites

pip install ortools pandas numpy python-dateutil

Basic Usage

from ortools.sat.python import cp_model

# 1. Create model
model = cp_model.CpModel()

# 2. Define variables
x = model.NewIntVar(0, 10, "x")
y = model.NewBoolVar("y")

# 3. Add constraints
model.Add(x <= 5)
model.Add(y == 1).OnlyEnforceIf(x > 3)

# 4. Set objective (optional)
model.Maximize(x)

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

# 6. Check results
if status == cp_model.OPTIMAL:
    print(f"x = {solver.Value(x)}")

📊 Business Applications

The flexible constraint approach is particularly valuable for:

• Marketing Campaign Optimization: Budget allocation, keyword selection
• Resource Planning: Staff scheduling, inventory management
• Production Planning: Machine scheduling, capacity planning
• Financial Portfolio Optimization: Asset allocation, risk management
• Supply Chain Optimization: Route planning, warehouse allocation

🎯 Key Insights

1. Fixed Constraints: Use when you have well-defined, immutable rules (puzzles, games, mathematical problems)

2. Flexible Constraints: Use when you have business parameters that can be adjusted to find optimal trade-offs

3. Multi-objective Optimization: Combine multiple goals using weighted objectives

4. Constraint Tuning: Experiment with different constraint settings to understand their impact on solutions

5. Solution Analysis: Always analyze how constraint changes affect your business metrics

📖 Additional Resources

• OR-Tools Documentation
• CP-SAT Solver Guide
• Constraint Programming Examples
• OR-Tools GitHub Repository

🤝 Contributing

Feel free to extend this notebook with additional examples or improve the existing implementations. The goal is to demonstrate the power and flexibility of constraint programming for real-world optimization problems.