Auditing a CP-SAT Scheduling Model

Read a CP-SAT solver log for a scheduling model and compute the diagnostic metrics that determine whether the solution can be trusted: the relative optimality gap, the presolve reduction ratio, and the conflicts-per-branch ratio. Use these metrics to identify the bottleneck of an unfinished or under-performing run.

Step 1 of 157%

Tutorial

Status and the Relative Optimality Gap

When CP-SAT terminates on an optimization model, the log reports two key quantities:

The best objective $B^\ast$ — the value of the incumbent (the best feasible solution found so far).
The best bound $\underline{B}$ — a proven lower bound on the true optimum (for a minimization problem).

By construction, $\underline{B} \le z^\ast \le B^\ast,$ where $z^\ast$ is the true optimum.

The relative optimality gap is

\text{gap} \;=\; \frac{B^\ast - \underline{B}}{\max(\varepsilon,\ |B^\ast|)},

where $\varepsilon > 0$ is a small constant that prevents division by zero. With status OPTIMAL, the gap is exactly $0$ . With status FEASIBLE (a limit such as time or branch count was hit before the gap could close), the relative gap quantifies how far the incumbent could be from the true optimum in the worst case.

For example, if a minimization log reports best: 240, bound: 216, then

\text{gap} \;=\; \frac{240 - 216}{240} \;=\; \frac{24}{240} \;=\; 0.10 \;=\; 10\%.

The incumbent is at most $10\%$ above the true optimum.