Cross-Checking the Optimum - Integer Programming & Branch-and-Bound

A solver answer becomes a certificate when independent computations agree. This repo's own exact arithmetic re-verifies every constraint on the decoded values — exposing one tight row — the solver's own bound meets its objective, and this repo's own general branch-and-bound reaches the same optimal value independently: three live legs.

highlighted = computed this step

Independent re-verification

This repo's own exact integer arithmetic re-checks the decoded values at every build: row_0 computes to 209 against its bound, row_1 to 284, row_2 to 211, and row_3 to 313, and the objective recomputes to 260. Why: an independent check must not reuse the solver's code path, and any violation would stop the build rather than let a wrong solution through.

\text{every row re-checked exactly}

The tight row

The slacks are 41, 1, 0, and 2: row_2 is tight, a binding constraint with zero slack, while the others have room. Why: a binding row is where the solution presses against the model — an honest detail the decoded values make visible for this particular optimal point, not a claim that every optimal solution to this instance shares it; an alternate optimum reached without the model file's hint has no tight row at all, and both are genuinely optimal at the same objective value.

\text{slack}=0\text{ on row\_}2

Three legs, all live

The certificate has three live legs: the re-verification above; the solver's best objective bound 260 meeting its objective 260; and this repo's own general-dimension branch-and-bound, independent of CP-SAT, reaching the same objective 260 after exploring 805 nodes of its own search tree. Why: a certificate leg is only as strong as its independence from what it checks — this branch-and-bound is engine machinery, not code written for this chapter, and shares no code path with CP-SAT; reaching the same objective by a genuinely different method is what turns three separate computations into one certificate.

\text{three independent legs, all live}

Diagram note

The table lists each constraint row with its recomputed left-hand side, its bound, and its slack; the tight row is visible as slack zero, by number rather than by highlight. Pixel positions are rounded for layout; every number shown is exact.

\text{slacks recomputed on every build}