Column Generation and Branch-and-Price Algorithm¶
Column generation is an algorithm used to solve large scale optimization problems which involve a large number of variables. Instead of solving the problem in its entirety, column generation begins with a restricted version of the problem containing only a subset of variables. It then iteratively introduces new variables (or columns) that have the potential to improve the solution, based on the problem’s structure and constraints.
In practice, column generation is particularly effective for problems with block-angular structures, such as cutting stock, vehicle routing, and generalized assignment problems. The method splits the problem into a master problem, which handles the selection of variables, and a pricing problem, which identifies the most promising variables to add to the master problem. These subproblems are solved iteratively until no further improvements are possible.
Block-angular matrix structure particularly suited for column generation.¶
The Branch-and-Price algorithm extends column generation to integer programming. While column generation operates on the linear relaxation of the problem, Branch-and-Price integrates it into a Branch-and-Bound framework to handle integer constraints. This combination allows efficient exploration of the solution space while exploiting the power of decomposition techniques. Each node of the Branch-and-Bound tree employs column generation to solve the relaxed problem, providing tight bounds for pruning and accelerating convergence.
In this series of tutorials, we will see how column generation and, more precisely, Dantzig-Wolfe decomposition can be implemented in idol.
Hint
For more details on column generation, we refer to the book [13].