Column (and Row) Generation Algorithms

For integer programs (IPs) that take the form of a relatively simple integer program with additional complicating constraints, the Dantzig–Wolfe reformulation or Master problem is introduced, in which the simple integer program is represented representing using the extreme points of its convex hull. A column generation approach is then used to solve the linear programming (LP) relaxation of the Master problem. This linear program is equivalent to the Lagrangiandual obtained by dualizing the complicating constraints. The integer Master problem is then solved using a branch-and-price algorithm in which the linear programming Master is solved implicitly or explicitly at each node of the enumeration tree. We then adapt the algorithm to deal with multiple and identical subproblems, and then discuss ways to accelerate the solution of both the LP and IP parts of a branch-and-price algorithm. Finally a branch-cut-and-price algorithm combining both column and cut generation is presented for the capacitated vehicle routing problem.