zbMATH — the first resource for mathematics

On the choice of explicit stabilizing terms in column generation. (English) Zbl 1169.90395
Summary: Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be solved. Although successfully employed in many applications, these approaches suffer from well-known instability issues that somewhat limit their efficiency. Building on the theory developed for nondifferentiable optimization algorithms, a large class of stabilized column generation algorithms can be defined which avoid the instability issues by using an explicit stabilizing term in the dual; this amounts at considering a (generalized) augmented Lagrangian of the primal master problem. Since the theory allows for a great degree of flexibility in the choice and in the management of the stabilizing term, one can use piecewise-linear or quadratic functions that can be efficiently dealt with using off-the-shelf solvers. The practical effectiveness of this approach is demonstrated by extensive computational experiments on large-scale Vehicle and Crew Scheduling problems. Also, the results of a detailed computational study on the impact of the different choices in the stabilization term (shape of the function, parameters), and their relationships with the quality of the initial dual estimates, on the overall effectiveness of the approach are reported, providing practical guidelines for selecting the most appropriate variant in different situations.

90C05 Linear programming
Full Text: DOI
[1] Oukil, A.; Ben Amor, H.; Desrosiers, J., Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems, Computers & operations research, 33, 4, 910-927, (2006)
[2] Babonneau, F.; Beltran, C.; Haurie, A.; Tadonki, C.; Vial, J.-Ph., Proximal-ACCPM: A versatile oracle based optimization method, (), 67-89 · Zbl 1118.90056
[3] Bacaud, L.; Lemaréchal, C.; Renaud, A.; Sagastizábal, C., Bundle methods in stochastic optimal power management: A disaggregated approach using preconditioners, Computational optimization and applications, 20, 227-244, (2001) · Zbl 0990.90085
[4] Ben Amor, H.; Desrosiers, J., A proximal trust region algorithm for column generation stabilization, Computers & operations research, 33, 4, 910-927, (2006) · Zbl 1079.90097
[5] H. Ben Amor, Stabilisation de l’Algorithme de Génération de Colonnes, Ph.D. Thesis, Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, QC, Canada, 2002
[6] Briant, O.; Lemaréchal, C.; Meurdesoif, Ph.; Michel, S.; Perrot, N.; Vanderbeck, F., Comparison of bundle and classical column generation, Mathematical programming, 113, 2, 299-344, (2008) · Zbl 1152.90005
[7] Carpaneto, D.; Dall’Amico, M.; Fischetti, M.; Toth, P., A branch and bound algorithm for the multiple depot vehicle scheduling problem, Networks, 19, 531-548, (1989) · Zbl 0672.90073
[8] Dantzig, G.B.; Wolfe, P., The decomposition principle for linear programs, Operations research, 8, 1, 101-111, (1960) · Zbl 0093.32806
[9] Desaulniers, G.; Desrosiers, J.; Ioachim, I.; Solomon, M.M.; Soumis, F.; Villeneuve, D., A unifed framework for deterministic time constrained vehicle routing and crew scheduling problems, (), 57-93 · Zbl 0966.90007
[10] du Merle, O.; Villeneuve, D.; Desrosiers, J.; Hansen, P., Stabilized column generation, Discrete mathematics, 194, 229-237, (1999) · Zbl 0949.90063
[11] Frangioni, A., Solving semidefinite quadratic problems within nonsmooth optimization algorithms, Computers & operations research, 23, 1099-1118, (1996) · Zbl 0871.90059
[12] Frangioni, A., Generalized bundle methods, SIAM journal on optimization, 13, 1, 117-156, (2002) · Zbl 1041.90037
[13] Frangioni, A., About Lagrangian methods in integer optimization, Annals of operations research, 139, 163-193, (2005) · Zbl 1091.90048
[14] Freiling, R.; Wagelmans, A.P.M.; Paixao, A., An overview of models and techniques for integrating vehicle and crew scheduling, (), 441-460 · Zbl 0948.90015
[15] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem, Operations research, 11, 849-859, (1961) · Zbl 0096.35501
[16] Haase, K.; Desaulniers, G.; Desrosiers, J., Simultaneous vehicle and crew scheduling in urban mass transit systems, Transportation science, 35, 3, 286-303, (2001) · Zbl 1069.90528
[17] Hadjar, A.; Marcotte, O.; Soumis, F., A branch-and-cut algorithm for the mutiple depot vehicle scheduling problem, Operations research, 54, 1, 130-149, (2006) · Zbl 1167.90509
[18] Hiriart-Urruty, J.-B.; Lemaréchal, C., Convex analysis and minimization algorithms, ()
[19] Kiwiel, K., A bundle Bregman proximal method for convex nondifferentiable optimization, Mathematical programming, 85, 241-258, (1999) · Zbl 0955.90101
[20] Kim, S.; Chang, K.N.; Lee, J.Y., A descent method with linear programming subproblems for nondifferentiable convex optimization, Mathematical programming, 71, 17-28, (1995) · Zbl 0855.90101
[21] Kelley, J.E., The cutting-plane method for solving convex programs, Journal of the SIAM, 8, 703-712, (1960) · Zbl 0098.12104
[22] Lemaréchal, C., Bundle methods in nonsmooth optimization, () · Zbl 0398.90088
[23] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New cariants of bundle methods, Mathematical programming, 69, 111-147, (1995)
[24] Lemaréchal, C., Lagrangian relaxation, (), 115-160
[25] C. Lemaréchal, K. Kiwiel, An inexact conic bundle variant suited to column generation, Mathematical Programming (2008) (in press) · Zbl 1163.65039
[26] Marsten, R.E.; Hogan, W.W.; Blankenship, J.W., The BOXSTEP method for large-scale optimization, Operations research, 23, 3, 389-405, (1975) · Zbl 0372.90078
[27] A. Ouorou, A proximal cutting plane method using Chebychev center for nonsmooth convex optimization, Mathematical Programming, (2008) (in press) · Zbl 1173.90009
[28] Pinar, M.C.; Zenios, S.A., On smoothing exact penalty functions for convex constrained optimization, SIAM journal on optimization, 4, 486-511, (1994) · Zbl 0819.90072
[29] Ribeiro, C.C.; Soumis, F., A column generation approach to the multi-depot vehicle scheduling problem, Operations research, 42, 1, 41-52, (1994) · Zbl 0798.90038
[30] Rockafellar, R.T., Monotone operators and the proximal point algorithm, SIAM journal on control and optimization, 14, 5, 877-898, (1976) · Zbl 0358.90053
[31] Rousseau, L.M.; Gendreau, M.; Feillet, D., Interior point stabilization in column generation, Operations research letters, 35, 5, 660-668, (2007) · Zbl 1149.90099
[32] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM journal on optimization, 2, 121-152, (1992) · Zbl 0761.90090
[33] Teboulle, M., Convergence of proximal-like algorithms, SIAM journal on optimization, 7, 1069-1083, (1997) · Zbl 0890.90151
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.