Constraint Programming
Constraint programming focuses on relationships among finite-domain variables: all-different rules, implications, intervals, optional activities, and combinatorial logic. Search can prove a result, find only a feasible result, or stop without either.
Prerequisites
Complete routing and time windows.
Learning goals
- Declare finite integer domains and logical constraints explicitly.
- Interpret every CP-SAT status before reading variable values.
- Reproduce a deterministic single-worker search configuration.
- Separate proven infeasibility from a time-limited
UNKNOWNoutcome.
Formulation before solver choice
For the optimal instance, , , and the objective is to maximize points. A second model imposes contradictory requirements and on one Boolean variable. A third copy of the first model has a zero-second limit.
CP-SAT accepts integer variables and integer constraint coefficients. Decimal quantities must be scaled to integers with a declared precision policy. The run sets one search worker and a fixed seed; multiple workers can change search order, and repeatability is not a cross-version guarantee.
Worked example
from ortools.sat.python import cp_model
def configured_solver(time_limit=None):
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 1
solver.parameters.random_seed = 0
if time_limit is not None:
solver.parameters.max_time_in_seconds = time_limit
return solver
optimal_model = cp_model.CpModel()
x = optimal_model.new_int_var(0, 3, "x")
y = optimal_model.new_int_var(0, 3, "y")
optimal_model.add(x + y == 3)
optimal_model.maximize(2 * x + y)
optimal_solver = configured_solver()
optimal_status = optimal_solver.solve(optimal_model)
infeasible_model = cp_model.CpModel()
z = infeasible_model.new_bool_var("z")
infeasible_model.add(z == 0)
infeasible_model.add(z == 1)
infeasible_solver = configured_solver()
infeasible_status = infeasible_solver.solve(infeasible_model)
limited_solver = configured_solver(time_limit=0.0)
limited_status = limited_solver.solve(optimal_model)
print(f"optimal_status={optimal_solver.status_name(optimal_status)} x={optimal_solver.value(x)} y={optimal_solver.value(y)} objective_points={optimal_solver.objective_value:.0f}")
print(f"contradiction_status={infeasible_solver.status_name(infeasible_status)} proven_infeasible=True")
print(f"zero_second_status={limited_solver.status_name(limited_status)} solution_available=False")
Expected output:
optimal_status=OPTIMAL x=3 y=0 objective_points=6
contradiction_status=INFEASIBLE proven_infeasible=True
zero_second_status=UNKNOWN solution_available=False
OPTIMAL permits reading the returned values and objective. INFEASIBLE means the encoded contradiction is proven infeasible. UNKNOWN means the zero-second run ended at its time limit before finding a solution or proving infeasibility; it is not evidence that no solution exists. A production limit should be chosen from a latency budget, not copied from this boundary demonstration.
Limitations and common mistakes
- Never read variable values after
INFEASIBLE,MODEL_INVALID, orUNKNOWNwithout a solution. FEASIBLEmeans a solution exists but optimality is not proven; report the bound or gap when available.- Fixed seeds and one worker improve repeatability but do not promise identical behavior across versions or platforms.
- Constraint propagation cannot repair missing or mistranslated rules.
- Zero seconds is a deterministic status example, not a benchmark or realistic search budget.
Practice
Replace the zero-second limit with a declared test budget and add many Boolean variables. Record status, objective, best bound, wall time, solver version, worker count, and seed; explain why repeated timing on one machine is still not a scale guarantee.
Next steps
Move from finite-domain combinatorics to smooth but potentially non-convex objectives in nonlinear optimization.
Primary sources
Checked 2026-10-19: Google OR-Tools 9.15, CP-SAT status semantics, constraint-optimization guide, v9.15 release and Python 3.14 support, and Python installation requirements.