Honest Solver Scope - Assignment & the Hungarian Method

Bringing in a solver does not retire the hand method. The Hungarian method remains exact on this instance, and the solver's real contribution is expressing larger instances and side-constraints in one model, within a clearly stated transfer boundary.

highlighted = computed this step

The hand method still applies

Nothing here replaces the earlier chapters: the Hungarian method is still exact on an instance of this size, and a rectangular matrix pads to square with a dummy task column of equal costs. Why: the reductions preserve the optimum exactly, and a dummy column simply absorbs the worker who sits idle.

\text{pad to square, then pivot as before}

What the solver adds

The solver scales differently, not better: larger matrices and side-constraints, such as a precedence rule between two tasks or a cap on how many tasks may go to one worker group, become extra model lines instead of a new hand pivot. Why: constraint solvers search with bounds, so added structure does not break the method the way it would break a hand-pivoted reduction.

\text{side-constraints are just more model lines}

Transfer boundary

The honest boundary: this chapter certifies one pinned five-by-four instance, cross-checked by enumeration, and says nothing about solver runtimes on larger data. Why: an optimum on a small instance is exact knowledge about that instance, not a performance promise about a different one. Pixel positions are rounded for layout; every number shown is exact.

\text{exact here; no runtime promise elsewhere}