Principles of Mathematics in Operations Research

Solutions 265

Fig. S.16. The optimum solution for our multi-commodity flow instance

In a sense, we partition the optimization problem into two levels: Main /
Subproblem, or Master / Slave, or Superior / Inferior; where the subproblem
has a structure that can be exploited easily. The main problem generates dual
variables and the subproblem generates new primal variables; and the loop
stops when primal-dual conditions are satisfied.
The dual to the above column generation approach gives rise to the sep-
aration problem, where we are about to solve LP with large number of rows
(equations). We first solve over restricted subset of rows (analogous to solving
over subset of columns) and ask oracle if other rows are satisfied. If so, we
are done; if not, we ask the oracle to return a separating hyperplane that
has current rows satisfied in one half space and a violation in the other. This
approach leads to Bender's decomposition.