Past exam of the mathematics course of the University of Cambridge / 2023 / ib / Paper 1 / 7H (Optimisation)

The minimum-cost flow problem chooses, for each directed edge $(i,j)\in E$, a flow $x_{ij}$ and solvessubject toFeasibility requires ${\sum }_i{b}_i=0$.

Set $y_{ij}=x_{ij}-M_{ij}$. Thenand its balance vector isThe objective becomes $\sum C_{ij}{y}_{ij}$ plus the constant $\sum C_{ij}{M}_{ij}$. Translation by $M$ is a bijection between feasible flows and preserves their ordering by cost, so the transformed zero-lower-bound problem is equivalent.