×

Large-scale optimization with the primal-dual column generation method. (English) Zbl 1334.90072

Summary: The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation process. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems.

MSC:

90C06 Large-scale problems in mathematical programming
49M27 Decomposition methods
90C25 Convex programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Altman, A., Kiwiel, K.C.: A note on some analytic center cutting plane methods for convex feasibility and minimization problems. Comput. Optim. Appl. 5(2), 175-180 (1996) · Zbl 0859.90102 · doi:10.1007/BF00249055
[2] Alvelos, F., Valério de Carvalho, J.M.: An extended model and a column generation algorithm for the planar multicommodity flow problem. Networks 50(1), 3-16 (2007) · Zbl 1119.90064 · doi:10.1002/net.20161
[3] Ariyawansa, K., Felt, A.J.: On a new collection of stochastic linear programming test problems. INFORMS J. Comput. 16(3), 291-299 (2004) · Zbl 1239.90081 · doi:10.1287/ijoc.1030.0037
[4] Babonneau, F.; Beltran, C.; Haurie, A.; Tadonki, C.; Vial, JP; Kontoghiorghes, EJ (ed.); Gatu, C. (ed.); Amman, H. (ed.); Rustem, B. (ed.); Deissenberg, C. (ed.); Farley, A. (ed.); Gilli, M. (ed.); Kendrick, D. (ed.); Luenberger, D. (ed.); Maes, R. (ed.); Maros, I. (ed.); Mulvey, J. (ed.); Nagurney, A. (ed.); Nielsen, S. (ed.); Pau, L. (ed.); Tse, E. (ed.); Whinston, A. (ed.), Proximal-ACCPM: a versatile oracle based optimisation method, No. 9, 67-89 (2007), Berlin · Zbl 1118.90056 · doi:10.1007/3-540-36626-1_4
[5] Babonneau, F., du Merle, O., Vial, J.P.: Solving large-scale linear multicommodity flow problems with an active set strategy and proximal-ACCPM. Oper. Res. 54(1), 184-197 (2006) · Zbl 1167.90661 · doi:10.1287/opre.1050.0262
[6] Babonneau, F., Vial, J.P.: ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. Math. Program. 120, 179-210 (2009) · Zbl 1169.90023 · doi:10.1007/s10107-007-0151-3
[7] Bach, F.R., Lanckriet, G.R.G., Jordan, M.I.: Multiple kernel learning, conic duality, and the SMO algorithm. In: Proceedings of the twenty-first international conference on Machine learning, ICML ’04, p. 6. ACM, New York (2004) · Zbl 1016.90077
[8] Bahn, O., Merle, O., Goffin, J.L., Vial, J.P.: A cutting plane method from analytic centers for stochastic programming. Math. Program. 69, 45-73 (1995) · Zbl 0855.90093
[9] Ben-Hur, A., Weston, J.: A user’s guide to support vector machines. In: Data Mining Techniques for the Life Sciences, pp. 223-239. Springer, Berlin (2010) · Zbl 1167.90661
[10] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4, 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[11] Birge, J.R., Dempster, M.A., Gassmann, H.I., Gunn, E.A., King, A.J., Wallace, S.W.: A standard input format for multiperiod stochastic linear programs. COAL Newsl. 17, 1-19 (1987)
[12] Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3), 384-392 (1988) · Zbl 0647.90066 · doi:10.1016/0377-2217(88)90159-2
[13] Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, Berlin (1997) · Zbl 0892.90142
[14] Briant, O., Lemaréchal, C., Meurdesoif, P., Michel, S., Perrot, N., Vanderbeck, F.: Comparison of bundle and classical column generation. Math. Program. 113, 299-344 (2008) · Zbl 1152.90005 · doi:10.1007/s10107-006-0079-z
[15] Castro, J.: Solving difficult multicommodity problems with a specialized interior-point algorithm. Ann. Oper. Res. 124, 35-48 (2003) · Zbl 1053.90010 · doi:10.1023/B:ANOR.0000004761.99649.a5
[16] Castro, J., Cuesta, J.: Improving an interior-point algorithm for multicommodity flows by quadratic regularizations. Networks 59(1), 117-131 (2012) · Zbl 1245.90081 · doi:10.1002/net.20483
[17] Dantzig, G.B.: Linear Programming and its Extensions. Princeton University Press, Princeton (1963) · Zbl 0108.33103
[18] Dantzig, G.B., Madansky, A.: On the solution of two-stage linear programs under uncertainty. In: Proceedings Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 165-176. University of California Press, Berkeley (1961) · Zbl 0104.14401
[19] Dantzig, G.B., Wolfe, P.: The decomposition algorithm for linear programs. Econometrica 29(4), 767-778 (1961) · Zbl 0104.14305 · doi:10.2307/1911818
[20] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[21] Ellison, E., Mitra, G., Zverovich, V.: FortSP: A Stochastic Programming Solver. OptiRisk Systems, UK (2010)
[22] Ford, L.R., Fulkerson, D.R.: A suggested computation for maximal multi-commodity network flows. Manag. Sci. 5(1), 97-101 (1958) · Zbl 0995.90516 · doi:10.1287/mnsc.5.1.97
[23] Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13, 117-156 (2002) · Zbl 1041.90037 · doi:10.1137/S1052623498342186
[24] Frangioni, A., Gallo, G.: A bundle type dual-ascent approach to linear multicommodity min-cost flow problems. INFORMS J. Comput. 11(4), 370-393 (1999) · Zbl 1034.90534 · doi:10.1287/ijoc.11.4.370
[25] Frangioni, A., Gendron, B.: A stabilized structured Dantzig-Wolfe decomposition method. Math. Program. 140(1), 45-76 (2013) · Zbl 1272.90029 · doi:10.1007/s10107-012-0626-8
[26] Frank, A., Asuncion, A.: UCI machine learning repository (2010). http://archive.ics.uci.edu/ml · Zbl 0856.90088
[27] Geoffrion, A.M.: Elements of large-scale mathematical programming Part I: concepts. Manag. Sci. 16(11), 652-675 (1970) · Zbl 0209.22801 · doi:10.1287/mnsc.16.11.652
[28] Geoffrion, A.M.: Elements of large-scale mathematical programming Part II: synthesis of algorithms and bibliography. Manag. Sci. 16(11), 676-691 (1970) · Zbl 0209.22801 · doi:10.1287/mnsc.16.11.676
[29] Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849-859 (1961) · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[30] Goffin, J.L., Gondzio, J., Sarkissian, R., Vial, J.P.: Solving nonlinear multicommodity flow problems by the analytic center cutting plane method. Math. Program. 76, 131-154 (1996) · Zbl 0881.90050
[31] Goffin, J.L., Haurie, A., Vial, J.P.: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 38(2), 284-302 (1992) · Zbl 0762.90050 · doi:10.1287/mnsc.38.2.284
[32] Goffin, J.L., Luo, Z.Q., Ye, Y.: Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J. Optim. 6(3), 638-652 (1996) · Zbl 0856.90088 · doi:10.1137/S1052623493258635
[33] Goffin, J.L., Vial, J.P.: Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method. Optim. Methods Softw. 17, 805-868 (2002) · Zbl 1065.90060 · doi:10.1080/1055678021000060829a
[34] Gondzio, J.: Warm start of the primal-dual method applied in the cutting-plane scheme. Math. Program. 83, 125-143 (1998) · Zbl 0920.90102
[35] Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218(3), 587-601 (2012) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017
[36] Gondzio, J., González-Brevis, P.: A new warmstarting strategy for the primal-dual column generation method. Math. Program. 152(1-2), 113-146 (2015). doi:10.1007/s10107-014-0779-8 · Zbl 1327.90389
[37] Gondzio, J., González-Brevis, P., Munari, P.: New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224(1), 41-51 (2013) · Zbl 1292.90318 · doi:10.1016/j.ejor.2012.07.024
[38] Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Technical Report 96.6, Logilab (1996) · Zbl 0995.90516
[39] Gönen, M., Alpaydin, E.: Multiple kernel learning algorithms. J. Mach. Learn. Res. 12, 2211-2268 (2011) · Zbl 1280.68167
[40] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Springer, Berlin (1993) · Zbl 0795.49002
[41] Holmes, D.: A (PO)rtable (S)tochastic programming (T)est (S)et (POSTS) (1995). Available in: http://users.iems.northwestern.edu/ jrbirge/html/dholmes/post.html. Accessed April 2013
[42] Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, New York (1994) · Zbl 0812.90122
[43] Kelley, L.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053
[44] Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46, 105-122 (1990) · Zbl 0697.90060 · doi:10.1007/BF01585731
[45] Kiwiel, K.C.: Complexity of some cutting plane methods that use analytic centers. Math. Program. 74(1), 47-54 (1996) · Zbl 0868.90110 · doi:10.1007/BF02592145
[46] Lanckriet, G., Cristianini, N., Bartlett, P., Ghaoui, L., Jordan, M.: Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res. 5, 27-72 (2004) · Zbl 1222.68241
[47] Larsson, T., Yuan, D.: An augmented lagrangian algorithm for large scale multicommodity routing. Comput. Optim. Appl. 27, 187-215 (2004) · Zbl 1044.90010 · doi:10.1023/B:COAP.0000008652.29295.eb
[48] Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1-3), 111-147 (1995) · Zbl 0857.90102 · doi:10.1007/BF01585555
[49] Lemaréchal, C., Ouorou, A., Petrou, G.: A bundle-type algorithm for routing in telecommunication data networks. Comput. Optim. Appl. 44, 385-409 (2009) · Zbl 1181.90059 · doi:10.1007/s10589-007-9160-7
[50] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1-3), 193-228 (1998) · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[51] Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007-1023 (2005) · Zbl 1165.90578 · doi:10.1287/opre.1050.0234
[52] Marsten, R.E., Hogan, W.W., Blankenship, J.W.: The boxstep method for large-scale optimization. Oper. Res. 23(3), 389-405 (1975) · Zbl 0372.90078 · doi:10.1287/opre.23.3.389
[53] Martinson, R.K., Tind, J.: An interior point method in Dantzig-Wolfe decomposition. Comput. Oper. Res. 26, 1195-1216 (1999) · Zbl 1016.90077 · doi:10.1016/S0305-0548(98)00101-4
[54] McBride, R.D.: Progress made in solving the multicommodity flow problem. SIAM J. Optim. 8(4), 947-955 (1998) · Zbl 0912.90128 · doi:10.1137/S1052623496304542
[55] du Merle, O., Villeneuve, D., Desrosiers, J., Hansen, P.: Stabilized column generation. Discrete Math. 194(1-3), 229-237 (1999) · Zbl 0949.90063 · doi:10.1016/S0012-365X(98)00213-1
[56] Mitchell, J.E., Borchers, B.: Solving real-world linear ordering problems using a primal-dual interior point cutting plane method. Ann. Oper. Res. 62, 253-276 (1996) · Zbl 0848.90086 · doi:10.1007/BF02206819
[57] Munari, P., Gondzio, J.: Using the primal-dual interior point algorithm within the branch-price-and-cut method. Comput. Oper. Res. 40(8), 2026-2036 (2013) · Zbl 1348.90478 · doi:10.1016/j.cor.2013.02.028
[58] Neame, P.: Nonsmooth dual methods in integer programming. Ph.D. thesis, University of Melbourne, Department of Mathematics and Statistics (2000) · Zbl 1167.90661
[59] Ouorou, A., Mahey, P., Vial, J.P.: A survey of algorithms for convex multicommodity flow problems. Manag. Sci. 46(1), 126-147 (2000) · Zbl 1231.90110 · doi:10.1287/mnsc.46.1.126.15132
[60] Rakotomamonjy, A., Bach, F., Canu, S., Grandvalet, Y.: SimpleMKL. J. Mach. Learn. Res. 9, 2491-2521 (2008) · Zbl 1225.68208
[61] Ruszczyński, A.: A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35, 309-333 (1986) · Zbl 0599.90103 · doi:10.1007/BF01580883
[62] Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2(1), 121-152 (1992) · Zbl 0761.90090 · doi:10.1137/0802008
[63] Sonnenburg, S., Rätsch, G., Henschel, S., Widmer, C., Behr, J., Zien, A., de Bona, F., Binder, A., Gehl, C., Franc, V.: The SHOGUN machine learning toolbox. J. Mach. Learn. Res. 11, 1799-1802 (2010) · Zbl 1242.68003
[64] Sonnenburg, S., Rätsch, G., Schäfer, C., Schölkopf, B.: Large scale multiple kernel learning. J. Mach. Learn. Res. 7, 1531-1565 (2006) · Zbl 1222.90072
[65] Suzuki, T., Tomioka, R.: SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels. Mach. Learn. 85, 77-108 (2011) · Zbl 1237.68166 · doi:10.1007/s10994-011-5252-9
[66] Van Slyke, R., Wets, R.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4), 638-663 (1969) · Zbl 0197.45602 · doi:10.1137/0117061
[67] Vanderbeck, F.; Desaulniers, G. (ed.); Desrosiers, J. (ed.); Solomon, MM (ed.), Implementing mixed integer column generation, 331-358 (2005), USA · Zbl 1246.90108 · doi:10.1007/0-387-25486-2_12
[68] Vapnik, V.: Statistical Learning Theory. Wiley, New York (1998) · Zbl 0935.62007
[69] Wentges, P.: Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Int. Trans. Oper. Res. 4(2), 151-162 (1997) · Zbl 0886.90107
[70] Xu, Z., Jin, R., King, I., Lyu, M.: An extended level method for efficient multiple kernel learning. Adv. Neural Inf. Process. Syst. 21, 1825-1832 (2009) · Zbl 1170.35396
[71] Zien, A., Ong, C.S.: Multiclass multiple kernel learning. In: Proceedings of the 24th International Conference on Machine Learning. ICML ’07, pp. 1191-1198. ACM, New York (2007)
[72] Zverovich, V., Fábián, C.I., Ellison, E.F., Mitra, G.: A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition. Math. Program. Comput. 4, 211-238 (2012) · Zbl 1275.90050 · doi:10.1007/s12532-012-0038-z
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.