Large-scale optimization with the primal-dual column generation method
Tóm tắt
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.
Tài liệu tham khảo
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)
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)
Ariyawansa, K., Felt, A.J.: On a new collection of stochastic linear programming test problems. INFORMS J. Comput. 16(3), 291–299 (2004)
Babonneau, F., Beltran, C., Haurie, A., Tadonki, C., Vial, J.P.: Proximal-ACCPM: a versatile oracle based optimisation method. In: Kontoghiorghes, E.J., Gatu, C., Amman, H., Rustem, B., Deissenberg, C., Farley, A., Gilli, M., Kendrick, D., Luenberger, D., Maes, R., Maros, I., Mulvey, J., Nagurney, A., Nielsen, S., Pau, L., Tse, E., Whinston, A. (eds.) Optimisation, Econometric and Financial Analysis, Advances in Computational Management Science, vol. 9, pp. 67–89. Springer, Berlin (2007)
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)
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)
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)
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)
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)
Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4, 238–252 (1962)
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)
Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3), 384–392 (1988)
Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, Berlin (1997)
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)
Castro, J.: Solving difficult multicommodity problems with a specialized interior-point algorithm. Ann. Oper. Res. 124, 35–48 (2003)
Castro, J., Cuesta, J.: Improving an interior-point algorithm for multicommodity flows by quadratic regularizations. Networks 59(1), 117–131 (2012)
Dantzig, G.B.: Linear Programming and its Extensions. Princeton University Press, Princeton (1963)
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)
Dantzig, G.B., Wolfe, P.: The decomposition algorithm for linear programs. Econometrica 29(4), 767–778 (1961)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Ellison, E., Mitra, G., Zverovich, V.: FortSP: A Stochastic Programming Solver. OptiRisk Systems, UK (2010)
Ford, L.R., Fulkerson, D.R.: A suggested computation for maximal multi-commodity network flows. Manag. Sci. 5(1), 97–101 (1958)
Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13, 117–156 (2002)
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)
Frangioni, A., Gendron, B.: A stabilized structured Dantzig–Wolfe decomposition method. Math. Program. 140(1), 45–76 (2013)
Frank, A., Asuncion, A.: UCI machine learning repository (2010). http://archive.ics.uci.edu/ml
Geoffrion, A.M.: Elements of large-scale mathematical programming Part I: concepts. Manag. Sci. 16(11), 652–675 (1970)
Geoffrion, A.M.: Elements of large-scale mathematical programming Part II: synthesis of algorithms and bibliography. Manag. Sci. 16(11), 676–691 (1970)
Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)
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)
Goffin, J.L., Haurie, A., Vial, J.P.: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 38(2), 284–302 (1992)
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)
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)
Gondzio, J.: Warm start of the primal-dual method applied in the cutting-plane scheme. Math. Program. 83, 125–143 (1998)
Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218(3), 587–601 (2012)
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
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)
Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Technical Report 96.6, Logilab (1996)
Gönen, M., Alpaydin, E.: Multiple kernel learning algorithms. J. Mach. Learn. Res. 12, 2211–2268 (2011)
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Springer, Berlin (1993)
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
Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, New York (1994)
Kelley, L.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703–712 (1960)
Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46, 105–122 (1990)
Kiwiel, K.C.: Complexity of some cutting plane methods that use analytic centers. Math. Program. 74(1), 47–54 (1996)
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)
Larsson, T., Yuan, D.: An augmented lagrangian algorithm for large scale multicommodity routing. Comput. Optim. Appl. 27, 187–215 (2004)
Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1–3), 111–147 (1995)
Lemaréchal, C., Ouorou, A., Petrou, G.: A bundle-type algorithm for routing in telecommunication data networks. Comput. Optim. Appl. 44, 385–409 (2009)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1–3), 193–228 (1998)
Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007–1023 (2005)
Marsten, R.E., Hogan, W.W., Blankenship, J.W.: The boxstep method for large-scale optimization. Oper. Res. 23(3), 389–405 (1975)
Martinson, R.K., Tind, J.: An interior point method in Dantzig–Wolfe decomposition. Comput. Oper. Res. 26, 1195–1216 (1999)
McBride, R.D.: Progress made in solving the multicommodity flow problem. SIAM J. Optim. 8(4), 947–955 (1998)
du Merle, O., Villeneuve, D., Desrosiers, J., Hansen, P.: Stabilized column generation. Discrete Math. 194(1–3), 229–237 (1999)
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)
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)
Neame, P.: Nonsmooth dual methods in integer programming. Ph.D. thesis, University of Melbourne, Department of Mathematics and Statistics (2000)
Ouorou, A., Mahey, P., Vial, J.P.: A survey of algorithms for convex multicommodity flow problems. Manag. Sci. 46(1), 126–147 (2000)
Rakotomamonjy, A., Bach, F., Canu, S., Grandvalet, Y.: SimpleMKL. J. Mach. Learn. Res. 9, 2491–2521 (2008)
Ruszczyński, A.: A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35, 309–333 (1986)
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)
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)
Sonnenburg, S., Rätsch, G., Schäfer, C., Schölkopf, B.: Large scale multiple kernel learning. J. Mach. Learn. Res. 7, 1531–1565 (2006)
Suzuki, T., Tomioka, R.: SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels. Mach. Learn. 85, 77–108 (2011)
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)
Vanderbeck, F.: Implementing mixed integer column generation. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 331–358. Springer, USA (2005)
Vapnik, V.: Statistical Learning Theory. Wiley, New York (1998)
Wentges, P.: Weighted Dantzig–Wolfe decomposition for linear mixed-integer programming. Int. Trans. Oper. Res. 4(2), 151–162 (1997)
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)
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)
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)