zbMATH — the first resource for mathematics

Implementing mixed integer column generation. (English) Zbl 1246.90108
Desaulniers, Guy (ed.) et al., Column generation. New York, NY: Springer (ISBN 0-387-25485-4/hbk). GERAD 25th Anniversary Series 5, 331-358 (2005).
Summary: We review the main issues that arise when implementing a column generation approach to solve a mixed integer program: setting-up the Dantzig-Wolfe reformulation, adapting standard MIP techniques to the context of column generation (branching, preprocessing, primal heuristics), and dealing with issues specific to column generation (initialization, stabilization, column management strategies). The description of the different features is done in generic terms to emphasize their applicability across problems. More hand-on experiences are reported in the literature in application specific context, f.i., see G. Desaulniers, J. Desrosiers and M. M. Solomon [Essays and surveys in metaheuristics. Boston: Kluwer Academic Publishers. Oper. Res./Comput. Sci. Interfaces Ser. 15, 309-324 (2002; Zbl 1017.90045)] for vehicle routing and crew scheduling applications. This paper summarizes recent work in the field, in particular that of F. Vanderbeck [Oper. Res. Lett. 34, No. 3, 296–306 (2006; Zbl 1109.90062), Automated Dantzig-Wolfe re-formulation or how to exploit simultaneously original formulation and column generation re-formulation. Working Paper, no. U-03.24, MAB, Université Bordeaux 1, France (2003)].
For the entire collection see [Zbl 1084.90002].

90C11 Mixed integer programming
PDF BibTeX Cite
Full Text: DOI