Skip to main content

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 UNKNOWN outcome.

Formulation before solver choice​

For the optimal instance, x,y∈{0,1,2,3}x,y\in\{0,1,2,3\}, x+y=3x+y=3, and the objective is to maximize 2x+y2x+y points. A second model imposes contradictory requirements z=0z=0 and z=1z=1 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, or UNKNOWN without a solution.
  • FEASIBLE means 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.