Optimization in CP-SAT: Objective Functions and the LP Relaxation

Recall from the CP-SAT Data Structures lesson that every integer variable in the solver is backed by a set of Boolean literals of the form x ≥ k — one literal per step of the domain. When the CP-SAT model includes a line such as:

model.Minimize(3 * x + 5 * y + 2 * z)

the solver does not keep 3*x + 5*y + 2*z as a symbolic expression. It encodes the objective as a weighted sum of those same indicator literals. ^{[OR-Tools CP-SAT source: sat/integer.h]}

Concretely, if x has domain [0, 5], the literals are (x ≥ 1), (x ≥ 2), …, (x ≥ 5). Each one carries weight 3 (the coefficient of x). The objective value at any assignment is:

$\text{obj} = 3 \cdot x + 5 \cdot y + 2 \cdot z = \underbrace{3 \cdot \mathbf{1}[x \geq 1] + 3 \cdot \mathbf{1}[x \geq 2] + \cdots}_{\text{literals for }x} + \underbrace{5 \cdot \mathbf{1}[y \geq 1] + \cdots}_{\text{literals for }y} + \cdots$

This is an order encoding — the value of an integer variable is the count of x ≥ k literals that are true, weighted by the objective coefficient.

integer_trail->Enqueue(
  IntegerLiteral::GreaterOrEqual(objective_var, V),
  /*reason=*/{} // no reason needed — it is a new decision
);

Here is the question that distinguishes CP-SAT from a plain CP solver: how low can the objective possibly go, given the constraints?

A CP propagator can tighten individual domain bounds, but it cannot answer that question globally without exploring the entire search tree. The LP relaxation can.

The LP relaxation of a MIP problem is the same problem with the integrality requirements dropped — variables are allowed to take any real value in their domain. The LP relaxation is:

1. Always feasible if the integer problem is feasible (real values are at least as flexible as integer ones).
2. Always at least as optimal as the integer problem — its optimal value is a lower bound (for minimization) on the integer optimum.
3. Solvable in polynomial time by the simplex method.

Inside CP-SAT, the LP relaxation is solved by Glop, Google’s own primal simplex solver, which is compiled directly into the OR-Tools binary. ^{[OR-Tools CP-SAT source: sat/linear_programming_constraint.cc]} Glop is invoked as a propagator — it slots into the same propagator registry that the cumulative and AtMostOne constraints use. At each node of the search tree, after CDCL makes a decision and runs unit propagation, the Glop propagator fires: it solves the LP restricted to the current partial assignment’s domain bounds, then:

• Uses the LP optimum to tighten ObjectiveVar’s lower bound.
• Uses the LP dual variables (shadow prices) to derive reduced cost bounds on individual variables, tightening their domains via LCG explanations.

This last point is the architectural elegance: the LP’s output feeds directly back into the LCG mechanism. The explanation for “variable x cannot exceed 3 in this subtree” is not an arbitrary assertion — it is derived from the LP dual solution and expressed as a conjunction of domain bound literals, exactly as a CP propagator’s Explain() would do.

The dual bound’s power becomes concrete in the branch-and-bound tree. Consider a minimization problem where the current best integer solution (incumbent) has objective value V*. At any node of the search tree, after Glop solves the LP for that node’s restricted domain:

• If LP_bound ≥ V*: this entire subtree is pruned. Every integer solution in it has objective value at least LP_bound ≥ V*, so none can improve on the incumbent. The solver backtracks immediately.
• If LP_bound < V*: the subtree might contain a better solution. The solver branches.

graph TD
  root["Root: LP_bound=10\nIncumbent=∞"]:::node
  n1["x≤2: LP=12\n≥ incumbent 15 → PRUNE"]:::pruned
  n2["x≥3: LP=10\n< incumbent 15"]:::node
  n3["y≤1: LP=14\n≥ incumbent 15 → PRUNE"]:::pruned
  n4["y≥2: LP=10\nNew incumbent=13"]:::node
  n5["z≤0: LP=13\n= incumbent → PRUNE"]:::pruned
  n6["z≥1: LP=10\nNew incumbent=11"]:::node

  root --> n1
  root --> n2
  n2 --> n3
  n2 --> n4
  n4 --> n5
  n4 --> n6

  classDef node fill:#1e3a5f,color:#cbd5e1,stroke:#334155
  classDef pruned fill:#7f1d1d,color:#fca5a5,stroke:#dc2626

The key insight — and the reason CP-SAT’s LP integration is an architectural decision, not an afterthought — is that the dual bound propagates into domain tightening before branching. When Glop reports that the LP optimum restricts x ≤ 3.7, the solver tightens ub(x) to 3 via an LCG explanation. That tightening fires unit propagation through the watch list (as seen in the CP-SAT Data Structures lesson), which may cascade into further propagations by other constraints — all before the next branch decision.

The LP relaxation’s dual bound is only as tight as the LP polytope is close to the integer hull — the smallest convex region that contains exactly the integer feasible points. If the LP polytope has large fractional corners, the dual bound is loose and pruning is weak.

Cutting planes close this gap by adding valid linear inequalities that cut off fractional regions of the LP polytope without removing any integer points. Each cut is a linear constraint that:

1. Is satisfied by every integer feasible point (it is valid).
2. Is violated by the current LP optimum (it actually cuts something off).

CP-SAT’s LP propagator (linear_programming_constraint.cc) injects several families of cuts: ^{[OR-Tools CP-SAT source: sat/linear_programming_constraint.cc]}

• Gomory mixed-integer cuts — derived directly from the LP simplex tableau. When the LP optimum has a fractional variable x_j = f + ⌊f⌋, the Gomory procedure generates a cut by rounding the tableau row containing x_j. These cuts are guaranteed to eliminate the current fractional LP optimum. ^{[Outline of an Algorithm for Integer Solutions to Linear Programs]}
• Cover cuts — for 0-1 knapsack sub-problems embedded in the LP. A cover is a set of binary variables whose sum of coefficients exceeds the knapsack capacity; at most one fewer than all of them can be 1.
• Clique cuts — for Boolean variables with at-most-one relationships. If a set of literals forms a clique in the conflict graph (any two are mutually exclusive), their sum is at most 1. These are cheap to generate and extremely effective for scheduling problems.

Each cut generated is added to the LP’s constraint matrix and also stored as a lazy clause in the CDCL clause database — so if the cut’s condition is later triggered purely by unit propagation, the LP does not need to be re-solved.