Optimizing with column generation

This is a two-part textbook about Column Generation: advanced Branch-Cut-and-Price algorithms.

Column generation is a method to solve linear programming problems with a very large number of variables. It dynamically generates variables (and the corresponding matrix columns, hence the name) by solving auxiliary optimization problems known as pricing subproblems. Column generation can also be very effective in integer programming, forming the backbone of algorithms like Branch-and-Price and Branch-Cut-and-Price.

Part I, Column generation basics:

1. The revised simplex algorithm
2. Dantzig-Wolfe decomposition and column generation for linear programming.
3. Integer programming review.
4. Dantzig-Wolfe decomposition and column generation for integer programming.
5. Lagrangian relaxation and column generation.

Part II, Topics in column generation:

6. Column generation based heuristics.
7. Column generation convergence.
8. Advanced branching.
9. The dynamic programming labeling algorithm for the RCSP.
10. Non-robust cuts.
11. Reduced cost fixing and related techniques.
12. Additional case studies.
13. Software for column generation.

Website: Optimizing with column generation.