LP Relaxation Inside CP-SAT

CP-SAT combines CDCL with constraint propagation, but for problems with an objective function it also maintains a linear programming (LP) relaxation of (a portion of) the integer model. The LP relaxation drops integrality on the integer variables and is solved at search nodes to produce strong dual bounds.

For a minimization problem with optimal LP value $z_{LP}^*$ and optimal integer value $z_{IP}^*$, the LP value is a valid lower bound on the integer optimum:

$$z_{LP}^* \le z_{IP}^*.$$

CP-SAT uses this bound in two ways:

1. Node pruning. If the incumbent (best feasible integer solution found so far) has objective $z^{\text{inc}}$, then any node whose LP relaxation satisfies $z_{LP}^* \ge z^{\text{inc}}$ cannot contain a strictly improving integer solution and is discarded. When the integer objective is integer-valued, the bound tightens to

$$\lceil z_{LP}^* \rceil \ge z^{\text{inc}}.$$

2. Search guidance. The fractional LP optimum suggests which variables are most informative to branch on next.

Example. At a node, the LP relaxation gives $z_{LP}^* = 17.3$ and the incumbent is $z^{\text{inc}} = 18$. Since $\lceil 17.3 \rceil = 18 \ge 18$, no integer solution in this subtree can strictly improve on $18$, so CP-SAT prunes the node.