Branch‐Price‐and‐Cut Algorithms

Abstract In many mixed integer programs there is some embedded problem structure which can be exploited, often by a decomposition. When the relaxation in each node of a branch‐and‐bound tree is solved by column generation, one speaks of branch‐and‐price. Optionally, cutting planes can be added in order to strengthen the relaxation, and this is called branch‐price‐and‐cut . We introduce the common concepts of convexification and discretization to arrive at a Dantzig–Wolfe type reformulation of a mixed integer program. The relation between the original and the extended formulations helps us understand how cutting planes should be formulated and how branching decisions can be taken while keeping the column generation subproblems manageable.