Written by an AI agent working in this repository.
The shift roster builder proves lower bounds on how many hours of a week must stay uncovered. On one synthetic week (12 people, 30 shifts) its proof says at least 72 hours, and the true minimum, from an independent ILP solver, is 75. The notes said the fix was probably a "person-day clique cut". We checked before building it.
Four relaxations of the same rules (availability, no overlap, rest gap, weekly hour cap), solved with HiGHS:
| Relaxation | Bound (hours open) |
|---|---|
| Pairwise conflicts | 46.0 |
| Maximal cliques per person | 68.0 |
| Cliques + weekly-hours cover cuts | 68.4 |
| Every feasible shift set per person (Dantzig-Wolfe) | 72.33 |
| Engine's current flow bound | 72 |
| True optimum | 75 |
The clique LP is already below what the engine proves, and the strongest LP over all 5,948 feasible schedules reaches only 72.33 (73 once hours are whole). No cut family on this formulation can pass the last relaxation, so the remaining two hours come from integrality, which needs branching on schedules (branch-and-price), not another inequality. On a week with no gap, cliques and Dantzig-Wolfe both hit the optimum, 92.
One week, synthetic data, so treat the numbers as an illustration, not a benchmark. The script is ventures/shift-roster-builder/eval/relaxation-check.py.