The Elegance of Optimization: The Reduced Cost Criterion in Flow Problems

In the context of a Minimum Cost Flow (MCF) problem, and assuming that a feasible flow \(x\) has been found, the optimization criterion of a reduced-cost algorithm \(\overline{c_{ij}}\) establishes a necessary and sufficient condition for this flow \(x\) to be optimal.

Which of the following conditions is true for an optimal feasible flow \(x\) with respect to the reduced cost \(\overline{c_{ij}}\)​ of an arc \(i,j\) in the residual graph \(G_x\)​?

Answer Options:

A. For every arc \(i,j\) in the residual graph \(G_x\)​, the reduced cost \(\overline{c_{ij}}\) \(=\) \(c_{ij}\) \(+\) \(\pi_{i}\) \(-\) \(\pi_{j}\) must be strictly positive \(\overline{c_{ij}}\)​ \(\gt 0\), where \(\pi\) is the dual potential function.

B. The flow \(x\) is optimal if and only if the residual graph \(G_x\)​ contains at least one strictly negative cost cycle.

C. For every edge \(i,j\) in the residual graph \(G_x\)​, the reduced cost \(\overline{c_{ij}}\) must be nonnegative (\(\overline{c_{ij}}\) \(\ge\) \(0\).

D. The flow \(x\) is optimal if and only if the value of the flow of \(x\) is equal to the capacity of any cut \(S,T\) of the original graph \(G\).

E. None of the above

Original idea by: Juan Jose Rodriguez Rodriguez