×

zbMATH — the first resource for mathematics

Comparison of bundle and classical column generation. (English) Zbl 1152.90005
Summary: When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.

MSC:
90C25 Convex programming
90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher, K., Wolsey, L.A.: On Dual Solutions in Subgradient Optimization. Unpublished manuscript, CORE, Louvain-la-Neuve (1993)
[2] Augerat, P.: VRP problem instances (1995) http://www.branchandcut.org/VRP/data/
[3] Barahona F. and Anbil R. (2000). The volume algorithm: Producing primal solutions with a subgradient method. Math. Program. 87(3): 385–399 · Zbl 0961.90058
[4] Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990) http://mscmga.ms.ic.ac.uk/jeb/orlib/binpackinfo.html
[5] Ben-Amor, H., Desrosiers, J.: A proximal-like algorithm for column generation stabilization. Technical report G-2003-43, Les Cahiers du Gerad, Montréal (2003) · Zbl 1079.90097
[6] Benameur, W., Neto, J.: Acceleration of cutting plane and column generation algorithms: application to network design (to appear, 2006)
[7] Cheney E. and Goldstein A. (1959). Newton’s method for convex programming and Tchebycheff approximations. Numer. Math. 1: 253–268 · Zbl 0113.10703
[8] COmputational INfrastructure for Operations Research: http://www.coin-or.org
[9] Dash Optimization: Xpress-MP: User guide and reference manual, release 12 (2001) http://www.dashoptimization.com
[10] Degraeve Z. and Peeters M. (2003). Optimal integer solutions to industrial cutting stock problems: part 2: benchmark results. INFORMS J. Comput. 15(1–3): 58–81 · Zbl 1238.90129
[11] du Merle O., Villeneuve D., Desrosiers J. and Hansen P. (1999). Stabilized column generation. Disc. Math. 194(1–3): 229–237 · Zbl 0949.90063
[12] Ermol’ev Y.M. (1966). Methods of solution of nonlinear extremal problems. Kibernetica 2(4): 1–17
[13] Feillet D., Dejax P., Gendreau M. and Gueguen C. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44(3): 216–229 · Zbl 1056.90014
[14] Frangioni A. (2003). Generalized bundle methods. SIAM J. Optim. 13(1): 117–156 · Zbl 1041.90037
[15] Gau T. and Wäscher G. (1995). CUTGEN1: a problem generator for the standard one-dimensional cutting stock problem. Eur. J. Oper. Res. 84: 572–579 · Zbl 0918.90117
[16] Geoffrion A.M. (1974). Lagrangean relaxation for integer programming. Math. Program. Study 2: 82–114 · Zbl 0395.90056
[17] Goffin J.-L., Haurie A. and Vial J.-Ph. (1992). Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci. 38(2): 284–302 · Zbl 0762.90050
[18] Goffin J.-L., Luo Z.-Q. and Ye Y. (1996). Complexity analysis of an interior cutting plane for convex feasibility problems. SIAM J. Optim. 6(3): 638–652 · Zbl 0856.90088
[19] Goffin J.-L. and Vial J.-Ph. (2002). Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method. Optim. Methods Softw. 17(5): 805–867 · Zbl 1065.90060
[20] Held M. and Karp R. (1970). The traveling salesman problem and minimum spanning trees. Oper. Res. 18: 1138–1162 · Zbl 0226.90047
[21] Held M. and Karp R. (1971). The traveling salesman problem and minimum spanning trees: part II. Math. Program. 1(1): 6–25 · Zbl 0232.90038
[22] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin Heidelberg New York (1993, Two volumes)
[23] Hiriart-Urruty J.-B. and Lemaréchal C. (2001). Fundamentals of Convex Analysis. Springer, Berlin Heidelberg New York · Zbl 0998.49001
[24] Kelley J.E. (1960). The cutting plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8: 703–712 · Zbl 0098.12104
[25] Kim S., Chang K.N. and Lee J.Y. (1995). A descent method with linear programming subproblems for nondifferentiable convex optimization. Math. Program. 71(1): 17–28 · Zbl 0855.90101
[26] Kiwiel K.C. (1989). A dual method for certain positive semidefinite quadratic programming problems. SIAM J. Sci. Stat. Comput. 10(1): 175–186 · Zbl 0663.65063
[27] Kiwiel K.C. (1983). An aggregate subgradient method for nonsmooth convex minimization. Math. Program. 27: 320–341 · Zbl 0525.90074
[28] Kiwiel K.C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics 1133. Springer, Berlin Heidelberg New York · Zbl 0561.90059
[29] Kiwiel K.C. (1994). A Cholesky dual method for proximal piecewise linear programming. Numer. Math. 68: 325–340 · Zbl 0822.65038
[30] Kiwiel, K.C.: An inexact bundle approach to cutting stock problems. Technical report, Systems Research Institute, Warsaw. Submitted to INFORMS J. Comput. (2004) · Zbl 1243.90138
[31] Kiwiel K.C. (2006). A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16(4): 1007–1023 · Zbl 1104.65055
[32] Kiwiel, K.C., Lemaréchal, C.: An inexact conic bundle variant suited to column generation (in preparation) · Zbl 1163.65039
[33] Sagastizábal C., Bahiense L. and Maculan N. (2002). The volume algorithm revisited: relation with bundle methods. Math. Program. 94(1): 41–69 · Zbl 1023.90038
[34] Larsson T., Patriksson M. and Strömberg A.B. (1999). Ergodic, primal convergence in dual subgradient schemes for convex programming. Math. Program. 86(2): 283–312 · Zbl 0946.90059
[35] Lemaréchal, C.: An algorithm for minimizing convex functions. In: Rosenfeld, J.L. (ed.) Information Processing ’74, pp. 552–556. North Holland, Amsterdam (1974)
[36] Lemaréchal, C.: Nonsmooth optimization and descent methods. Research Report 78-4, IIASA (1978)
[37] Lemaréchal, C.: Lagrangian relaxation. In: Jünger, M., Naddef, D. (eds.) Computational Combinatorial Optimization, pp. 112–156. Springer, Berlin Heidelberg New York (2001) · Zbl 1052.90065
[38] Lemaréchal, C.: The omnipresence of Lagrange. 4OR 1(1), 7,25 (2003) · Zbl 1046.90064
[39] Lemaréchal C., Nemirovskii A.S. and Nesterov Yu.E. (1995). New variants of bundle methods. Math. Program. 69: 111–148 · Zbl 0857.90102
[40] Lemaréchal, C., Pellegrino, F., Renaud, A., Sagastizábal, C.: Bundle methods applied to the unit-commitment problem. In: Dolež al, J., Fidler, J. (eds.) System Modelling and Optimization, pp. 395–402. Chapman and Hall, London (1996) · Zbl 1055.90572
[41] Lemaréchal C. and Sagastizábal C. (1997). Variable metric bundle methods: from conceptual to implementable forms. Math. Program. 76(3): 393–410 · Zbl 0872.90072
[42] Marsten R.E., Hogan W.W. and Blankenship J.W. (1975). The boxstep method for large-scale optimization. Oper. Res. 23(3): 389–405 · Zbl 0372.90078
[43] Mehrotra A. and Trick M.A. (1996). A column generation approach to graph coloring. INFORMS J. Comput. 8(4): 344–354 · Zbl 0884.90144
[44] du Merle O., Villeneuve D., Desrosiers J. and Hansen P. (1999). Stabilized column generation. Discrete Math. 194: 229–237 · Zbl 0949.90063
[45] Nemirovskii, A.S., Yudin, D.: Informational complexity and efficient methods for the solution of convex extremal problems. Ékonomika i Mathematicheskie Metody 12, 357–369 (1976) (in Russian. English translation: Matekon 13, 3–25) · Zbl 0329.90054
[46] Nemirovskii, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics (1983). (Original Russian: Nauka, 1979)
[47] Nesterov Yu.E. (1995). Complexity estimates of some cutting plane methods based on the analytic barrier. Math. Program. 69(1): 149–176 · Zbl 0857.90103
[48] Nesterov Yu.E. and Vial J.-Ph. (1999). Homogeneous analytic center cutting plane methods for convex problems and variational inequalities. SIAM J. Optim. 9(3): 707–728 · Zbl 0971.65060
[49] Polyak B.T. (1967). A general method for solving extremum problems. Soviet Math. Doklady 8: 593–597 · Zbl 0177.15102
[50] Prim R.C. (1957). Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36: 1389–1401
[51] Rockafellar R.T. (1970). Convex Analysis. Princeton University Press, Princeton · Zbl 0193.18401
[52] Rockafellar R.T. (1973). A dual approach to solving nonlinear programming problems by constrained optimization. Math. Program. 5: 354–373 · Zbl 0279.90035
[53] Rousseau, L.-M., Gendreau, M., Feillet, D.: Interior point stabilization for column generation. Working paper 39, Centre de Recherche sur les Transports, Univ. Montréal (2003)
[54] Shor N. (1970). Utilization of the operation of space dilatation in the minimization of convex functions. Cybernetics 6(1): 7–15
[55] Shor N.Z. (1985). Minimization methods for non-differentiable functions. Springer, Berlin Heidelberg New York · Zbl 0561.90058
[56] Thiongane B., Nagih A. and Plateau G. (2004). Adapted step size in a 0-1 biknapsack lagrangean dual solving algoritm. Ann. Oper. Res. 139(1): 353–373 · Zbl 1091.90045
[57] Uzawa, H.: Iterative methods for concave programming. In: Arrow, K., Hurwicz, L., Uzawa, H. (eds.) Studies in Linear and Nonlinear Programming, pp. 154–165. Stanford University Press, Stanford (1959)
[58] Vanderbeck F. (2002). Extending Dantzig’s bound to the bounded multi-class binary knapsack problem. Math. Program. 94(1): 125–16 · Zbl 1023.90054
[59] Vanderbeck, F.: Dantzig-Wolfe re-formulation or how to exploit simultaneaously original formulation and column generation re-formulation. Working paper U-03.24, University Bordeaux 1, Talence (2003)
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.