×

zbMATH — the first resource for mathematics

A generic view of Dantzig–Wolfe decomposition in mixed integer programming. (English) Zbl 1109.90062
Summary: The Dantzig-Wolfe reformulation principle is presented based on the concept of generating sets. The use of generating sets allows for an easy extension to mixed integer programming. Moreover, it provides a unifying framework for viewing various column generation practices, such as relaxing or tightening the column generation subproblem and introducing stabilization techniques.

MSC:
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barnhart, C.; Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P.; Vance, P.H., Branch-and-price: column generation for huge integer programs, Oper. res., 46, 316-329, (1998) · Zbl 0979.90092
[2] O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot, F. Vanderbeck, Comparison of bundle and classical column generation, INRIA Working paper 5453, January 2005.
[3] Z. Degraeve, R. Jans, A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot Sizing Problem with Set Up Times, ERIM Report Series Research in Management, ERS-2003-010-LIS, 2003. · Zbl 1167.90321
[4] G. Desaulniers, J. Desrosiers, M.M. Solomon (Eds.), Column Generation, Springer, Berlin, 2005. · Zbl 1084.90002
[5] Fekete, S.P.; Schepers, J., New classes of lower bounds for bin packing problems, Math. programming, 91, 11-31, (2001) · Zbl 1051.90020
[6] Geoffrion, A., Lagrangian relaxation for integer programming, Math. programming study, 2, 82-114, (1974)
[7] Lemaréchal, C., Lagrangian relaxation, () · Zbl 1052.90065
[8] M.E. Lübbecke, J. Desrosiers, Selected topics in column generation, Oper. Res. 2005. · Zbl 1165.90578
[9] Martin, R.K., Generating alternative mixed-integer programming models using variable redefinition, Oper. res., 35, 6, 820-831, (1987) · Zbl 0638.90076
[10] K. Monneris, Problème de production par lots avec temps de mise en route par une méthode de branch-and-price, Rapport de stage de DEA, Université Bordeaux 1, juin 2002.
[11] N. Perrot, Integer programming column generation strategies for the cutting stock problem and its variants, Ph.D. Thesis, University Bordeaux 1 (2005).
[12] Savelsbergh, M.W.P., Preprocessing and probing techniques for mixed integer programming problems, ORSA J. computing, 6, 445-454, (1994) · Zbl 0814.90093
[13] Savelsbergh, M.W.P.; Sol, M., The general pickup and delivery problem, Transportation sci., 29, 1, 17-29, (1995) · Zbl 0826.90049
[14] Thizy, J.-M., Analysis of Lagrangian decomposition for the multi-item capacitated lot-sizing problem, Infor, 29, 4, 271-283, (1991) · Zbl 0778.90008
[15] Valério de Carvalho, J.M., Using extra dual cuts to accelerate column generation, INFORMS J. computing, 17, 2, (2005) · Zbl 1239.90089
[16] van den Akker, J.M.; Hurkens, C.A.J.; Savelsbergh, M.W.P., Time-indexed formulations for machine scheduling problems: column generation, INFORMS J. computing, 12, 111-124, (1998) · Zbl 1034.90004
[17] Vanderbeck, F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. programming, 86, 565-594, (1999) · Zbl 0949.90066
[18] Vanderbeck, F., On dantzig – wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm, Oper. res., 48, 1, 111-128, (2000) · Zbl 1106.90360
[19] F. Vanderbeck, Implementing mixed integer column generation, in: G. Desaulniers, J. Desrosiers, M.M. Solomon (Eds.), Column Generation, Springer, Berlin, 2005. · Zbl 1246.90108
[20] M. van Vyve, A solution approach of production planning problems based on compact formulations of lot-sizing models, Ph.D. Thesis, Université Catholique de Louvain, juin 2003. · Zbl 1078.90510
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.