Verifying Correctness of a Benders or Column Generation Implementation

Decomposition methods like Benders decomposition and column generation are easy to implement almost correctly. A single sign error in a cut, a wrong dual handoff, or an omitted column can silently corrupt the algorithm while still producing plausible-looking output. To catch these bugs, we monitor invariants — properties any correct run must satisfy at every iteration.

The first invariant follows from the relaxation property. In Benders decomposition for a minimization problem, the master problem is a relaxation of the original. Each Benders cut removes master solutions whose recourse cost was underestimated, but never excludes the true optimum. Therefore, if $z_k$ denotes the master objective at iteration $k$, we have

$$z_1 \leq z_2 \leq z_3 \leq \cdots,$$

i.e., $z_k$ is monotonically non-decreasing. If any consecutive pair satisfies $z_{k+1} < z_k$, the implementation is buggy — usually the cut at iteration $k$ was added with the wrong inequality direction, the wrong sign on the dual multipliers, or to the wrong row of the master.

For instance, an output trace $z_1 = 10,\, z_2 = 14,\, z_3 = 12$ flags a bug at iteration $k=3$, because the master objective cannot lose value as cuts are appended.