12 KiB
name, description
| name | description |
|---|---|
| formal-csp-modeling | Modeling scheduling problems (meetings, courses, jobs) |
CSP Modeling
Scope: Constraint satisfaction problem modeling, variables, domains, constraints, problem formulation Lines: ~330 Last Updated: 2025-10-18
When to Use This Skill
Activate this skill when:
- Modeling scheduling problems (meetings, courses, jobs)
- Solving allocation problems (resources, tasks, assignments)
- Implementing puzzle solvers (Sudoku, N-Queens, graph coloring)
- Formulating planning problems with constraints
- Converting real-world problems to CSP representation
- Designing constraint-based optimization systems
- Building configuration or layout generation systems
Core Concepts
CSP Components
Variables: Decision points in the problem
- Represent unknowns to be assigned values
- Example: Square positions in Sudoku, class time slots
- Choose granularity carefully (too fine = slow, too coarse = inflexible)
- Notation: X = {X₁, X₂, ..., Xₙ}
Domains: Possible values for each variable
- Finite set of values each variable can take
- Example: {1-9} for Sudoku, {Mon-Fri} for scheduling
- Can be discrete (integers, colors) or continuous (ranges)
- Notation: D = {D₁, D₂, ..., Dₙ} where Dᵢ is domain for Xᵢ
Constraints: Rules limiting variable assignments
- Unary: Single variable (X₁ ≠ 5)
- Binary: Two variables (X₁ ≠ X₂)
- N-ary: Multiple variables (X₁ + X₂ + X₃ = 10)
- Global: Complex patterns (AllDifferent, Cardinality)
- Notation: C = {C₁, C₂, ..., Cₘ}
Constraint Types
Explicit constraints: Enumerate allowed/forbidden tuples
# Binary constraint: allowed pairs
constraint = {(1, 2), (1, 3), (2, 3), (2, 4)}
Implicit constraints: Expressed as functions/predicates
# Mathematical constraint
def constraint(x1, x2):
return x1 + x2 <= 10
Global constraints: High-level patterns
AllDifferent(X): All variables have different valuesCardinality(X, v, min, max): Value v appears min-max timesCumulative(tasks, resources): Resource usage constraints- More efficient than decomposing into binary constraints
Constraint Graph
Structure: Graph representation of CSP
- Nodes: Variables
- Edges: Binary constraints between variables
- Hyperedges: N-ary constraints (multiple variables)
- Used for algorithm selection and analysis
Properties:
- Tree-structured: O(n·d²) solvable
- Width k: Complexity depends on tree decomposition
- Sparse vs dense affects algorithm choice
Patterns
Pattern 1: N-Queens Problem
from constraint import Problem, AllDifferentConstraint
def solve_n_queens(n):
"""Place n queens on n×n board with no attacks."""
problem = Problem()
# Variables: One per queen (row), domain: column positions
cols = range(n)
for row in range(n):
problem.addVariable(row, cols)
# Constraint: No two queens in same column
problem.addConstraint(AllDifferentConstraint(), cols)
# Constraint: No diagonal attacks
for row1 in range(n):
for row2 in range(row1 + 1, n):
# |row1 - row2| != |col1 - col2|
problem.addConstraint(
lambda c1, c2, r1=row1, r2=row2:
abs(r1 - r2) != abs(c1 - c2),
(row1, row2)
)
return problem.getSolutions()
When to use:
- Placement problems with non-overlapping constraints
- Board game configuration
- Layout generation with separation rules
Pattern 2: Sudoku Solver
from constraint import Problem, AllDifferentConstraint
def solve_sudoku(grid):
"""Solve 9×9 Sudoku puzzle."""
problem = Problem()
# Variables: Each cell (row, col)
cells = [(r, c) for r in range(9) for c in range(9)]
for r, c in cells:
if grid[r][c] == 0:
# Empty cell: domain 1-9
problem.addVariable((r, c), range(1, 10))
else:
# Pre-filled cell: fixed value
problem.addVariable((r, c), [grid[r][c]])
# Row constraints
for r in range(9):
problem.addConstraint(
AllDifferentConstraint(),
[(r, c) for c in range(9)]
)
# Column constraints
for c in range(9):
problem.addConstraint(
AllDifferentConstraint(),
[(r, c) for r in range(9)]
)
# 3×3 box constraints
for box_r in range(3):
for box_c in range(3):
cells_in_box = [
(r, c)
for r in range(box_r * 3, box_r * 3 + 3)
for c in range(box_c * 3, box_c * 3 + 3)
]
problem.addConstraint(
AllDifferentConstraint(),
cells_in_box
)
solutions = problem.getSolutions()
return solutions[0] if solutions else None
Benefits:
- Declarative problem specification
- Automatic constraint propagation
- Easy to add new constraint types
Pattern 3: Graph Coloring
from constraint import Problem, AllDifferentConstraint
def color_graph(graph, num_colors):
"""Assign colors to graph nodes (no adjacent same color)."""
problem = Problem()
# Variables: Graph nodes
nodes = list(graph.keys())
colors = range(num_colors)
for node in nodes:
problem.addVariable(node, colors)
# Constraints: Adjacent nodes different colors
for node, neighbors in graph.items():
for neighbor in neighbors:
if node < neighbor: # Avoid duplicate constraints
problem.addConstraint(
lambda c1, c2: c1 != c2,
(node, neighbor)
)
return problem.getSolutions()
# Example: Map coloring
us_map = {
'WA': ['OR', 'ID'],
'OR': ['WA', 'ID', 'NV', 'CA'],
'CA': ['OR', 'NV', 'AZ'],
# ... more states
}
solutions = color_graph(us_map, num_colors=4)
When to use:
- Register allocation in compilers
- Frequency assignment in wireless networks
- Time slot assignment avoiding conflicts
Pattern 4: Scheduling with OR-Tools
from ortools.sat.python import cp_model
def schedule_jobs(jobs, machines):
"""Schedule jobs on machines minimizing makespan."""
model = cp_model.CpModel()
# Variables: start_time and machine for each job
starts = {}
machines_assigned = {}
for job_id, duration in jobs.items():
starts[job_id] = model.NewIntVar(0, 1000, f'start_{job_id}')
machines_assigned[job_id] = model.NewIntVar(
0, len(machines) - 1, f'machine_{job_id}'
)
# Constraint: Jobs on same machine don't overlap
intervals_per_machine = [[] for _ in machines]
for job_id, duration in jobs.items():
for machine_id in range(len(machines)):
# Create interval for job on this machine
interval = model.NewOptionalIntervalVar(
starts[job_id],
duration,
starts[job_id] + duration,
machines_assigned[job_id] == machine_id,
f'interval_{job_id}_{machine_id}'
)
intervals_per_machine[machine_id].append(interval)
# NoOverlap constraint per machine
for machine_id in range(len(machines)):
model.AddNoOverlap(intervals_per_machine[machine_id])
# Objective: Minimize makespan
makespan = model.NewIntVar(0, 1000, 'makespan')
for job_id, duration in jobs.items():
model.Add(makespan >= starts[job_id] + duration)
model.Minimize(makespan)
# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
schedule = {
job_id: {
'start': solver.Value(starts[job_id]),
'machine': solver.Value(machines_assigned[job_id])
}
for job_id in jobs
}
return schedule, solver.Value(makespan)
return None, None
Benefits:
- Optimization objectives (minimize/maximize)
- Optional intervals for flexible scheduling
- Built-in NoOverlap global constraint
Pattern 5: Resource Allocation
from constraint import Problem, ExactSumConstraint
def allocate_resources(tasks, resources, capacity):
"""Assign tasks to resources respecting capacity limits."""
problem = Problem()
# Variables: Resource assignment per task
for task in tasks:
problem.addVariable(task, resources)
# Constraint: Each resource has capacity limit
for resource in resources:
# Count tasks assigned to this resource
tasks_on_resource = [
task for task in tasks
]
# Custom constraint checking capacity
def capacity_constraint(*assignments):
count = sum(1 for a in assignments if a == resource)
return count <= capacity[resource]
problem.addConstraint(
capacity_constraint,
tasks_on_resource
)
return problem.getSolutions()
# Example usage
tasks = ['T1', 'T2', 'T3', 'T4', 'T5']
resources = ['R1', 'R2', 'R3']
capacity = {'R1': 2, 'R2': 2, 'R3': 1}
solutions = allocate_resources(tasks, resources, capacity)
When to use:
- Server assignment with load limits
- Classroom allocation for courses
- Worker assignment to shifts
Quick Reference
CSP Formulation Checklist
1. Identify variables: What are you deciding?
2. Define domains: What values can each variable take?
3. Specify constraints:
- Unary: Variable must/cannot be X
- Binary: Relationships between pairs
- N-ary: Relationships among groups
- Global: High-level patterns
4. Choose optimization objective (if needed)
5. Select appropriate solver library
Common Global Constraints
| Constraint | Meaning | Use Case |
|---|---|---|
AllDifferent(X) |
All variables different | Sudoku, N-Queens |
AllEqual(X) |
All variables equal | Consistent labeling |
Cardinality(X, v, min, max) |
Value v appears min-max times | Workforce limits |
Sum(X) = k |
Variables sum to k | Budget constraints |
NoOverlap(intervals) |
Intervals don't overlap | Scheduling |
Cumulative(tasks, limit) |
Resource usage ≤ limit | Machine capacity |
Element(index, array, value) |
array[index] = value | Lookup constraints |
Modeling Guidelines
✅ DO: Use global constraints when possible (more efficient)
✅ DO: Minimize domain sizes (smaller = faster)
✅ DO: Add redundant constraints if they prune search space
✅ DO: Choose variable granularity carefully
❌ DON'T: Model everything as binary constraints
❌ DON'T: Use variables when constants suffice
❌ DON'T: Ignore problem structure (tree, bipartite, etc.)
❌ DON'T: Over-constrain (making problem unsatisfiable)
Anti-Patterns
❌ Over-constraining: Adding contradictory constraints
# Problem has no solution
problem.addConstraint(lambda x: x > 10)
problem.addConstraint(lambda x: x < 5)
✅ Check constraint consistency before solving
❌ Decomposing global constraints unnecessarily
# Inefficient: AllDifferent as pairwise inequality
for i in range(n):
for j in range(i + 1, n):
problem.addConstraint(lambda xi, xj: xi != xj, (i, j))
✅ Use AllDifferentConstraint() directly
❌ Wrong variable choice
# Bad: Boolean variables for multi-valued decisions
# is_blue, is_red, is_green (3 variables per item)
✅ Use single variable with domain {blue, red, green}
❌ Ignoring problem symmetry
# N-Queens: All solutions are rotations/reflections
# Returns 92 solutions for 8-Queens (only 12 unique)
✅ Add symmetry-breaking constraints or post-process
❌ Missing implied constraints
# Scheduling: Only NoOverlap constraint
# Missing: Task precedence, resource limits
✅ Add all relevant constraints for complete model
Related Skills
constraint-propagation.md- Reducing domains using constraintsbacktracking-search.md- Searching for CSP solutionssat-solving-strategies.md- Boolean satisfiability (special case of CSP)optimization-modeling.md- Adding objective functions to CSPsgraph-algorithms.md- Graph coloring and CSP structure
Last Updated: 2025-10-18 Format Version: 1.0 (Atomic)