Skip to main content
SpringerLink
Log in

Bundle methods for sum-functions with “easy” components: applications to multicommodity network design

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function where some of the components are “easy”, that is, they are Lagrangian functions of explicitly known compact convex programs. This corresponds to a stabilized partial Dantzig–Wolfe decomposition, where suitably modified representations of the “easy” convex subproblems are inserted in the master problem as an alternative to iteratively inner-approximating them by extreme points, thus providing the algorithm with exact information about a part of the dual objective function. The resulting master problems are potentially larger and less well-structured than the standard ones, ruling out the available specialized techniques and requiring the use of general-purpose solvers for their solution; this strongly favors piecewise-linear stabilizing terms, as opposed to the more usual quadratic ones, which in turn may have an adverse effect on the convergence speed of the algorithm, so that the overall performance may depend on appropriate tuning of all these aspects. Yet, very good computational results are obtained in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Astorino, A., Frangioni, A., Gaudioso, M., Gorgone, E.: Piecewise quadratic approximations in convex numerical optimization. SIAM J. Optim. 21(4), 1418–1438 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  2. Babonneau, F., Vial, J.-P.: ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. Math. Program. 120(1), 179–210 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bacaud, L., Lemaréchal, C., Renaud, A., Sagastizábal, C.: Bundle methods in stochastic optimal power management: a disaggregated approach using preconditioners. Comput. Optim. Appl. 20, 227–244 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bahiense, L., Maculan, N., Sagastizábal, C.: The volume algorithm revisited: relation with bundle methods. Math. Program. 94(1), 41–70 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31, 167–175 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Ben Amor, H., Desrosiers, J., Frangioni, A.: On the choice of explicit stabilizing terms in column generation. Discret. Appl. Math. 157(6), 1167–1184 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, Engineering Applications. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2001)

    Book  Google Scholar 

  8. Bertsekas, D.P., Nedić, A.: Incremental subgradient methods for nondifferentiable optimization. SIAM J Optim. 12(1), 109–138 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  9. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997)

    MATH  Google Scholar 

  10. Borghetti, A., Frangioni, A., Lacalandra, F., Nucci, C.A.: Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment. IEEE Trans. Power Syst. 18(1), 313–323 (2003)

    Article  Google Scholar 

  11. Briant, O., Lemaréchal, C., Meurdesoif, P., Michel, S., Perrot, N., Vanderbeck, F.: Comparison of bundle and classical column generation. Math. Program. 113(2), 299–344 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  12. Cappanera, P., Frangioni, A.: Symmetric and asymmetric parallelization of a cost-decomposition algorithm for multi-commodity flow problems. INFORMS J. Comput. 15(4), 369–384 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  13. Crainic, T.G., Frangioni, A., Gendron, B.: Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems. Discret. Appl. Math. 112, 73–99 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  14. Crainic, T.G., Gendron, B., Hernu, G.: A slope scaling/lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design. J. Heuristics 10(5), 525–545 (2004)

    Article  MATH  Google Scholar 

  15. d’Antonio, G., Frangioni, A.: Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Optim. 20(1), 357–386 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  16. du Merle, O., Goffin, J.-L., Vial, J.-P.: On improvements to the analytic center cutting plane method. Comput. Optim. Appl. 11(1), 37–52 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  17. Emiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning. Comput. Optim. Appl. 46, 305–332 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  18. Fabian, C.I., Szoke, Z.: Solving two-stage stochastic programming problems with level decomposition. Comput. Manag. Sci. 4(4), 313–353 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  19. Feltenmark, S., Kiwiel, K.: Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems. SIAM J. Optim. 10(3), 697–721 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. Frangioni, A.: Solving semidefinite quadratic problems Within nonsmooth optimization algorithms. Comput. Oper. Res. 21, 1099–1118 (1996)

    Article  MathSciNet  Google Scholar 

  21. Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13(1), 117–156 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  22. Frangioni, A.: About Lagrangian methods in integer optimization. Ann. Oper. Res. 139, 163–193 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  23. 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)

    Article  MATH  MathSciNet  Google Scholar 

  24. Frangioni, A., Gendron, B.: A stabilized structured Dantzig–Wolfe decomposition method. Math. Program. (2013)

  25. Frangioni, A., Gentile, C.: Solving nonlinear single-unit commitment problems with ramping constraints. Oper. Res. 54(4), 767–775 (2006)

    Article  MATH  Google Scholar 

  26. Frangioni, A., Gentile, C.: Experiments with a hybrid interior point/combinatorial approach for network flow problems. Optim. Methods Softw. 22(4), 573–585 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  27. Frangioni, A., Gorgone, E.: Generalized Bundle Methods for Sum-Functions with “Easy” Components: Applications to Multicommodity Network Design. Technical Report 12–12, Dipartimento di Informatica, Università di Pisa (2012)

  28. Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2–3), 375–388 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  29. Frangioni, A., Manca, A.: A computational study of cost reoptimization for min cost flow problems. INFORMS J. Comput. 18(1), 61–70 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  30. Ghamlouche, I., Crainic, T.G., Gendreau, M.: Path relinking, cycle-based neighborhoods and capacitated multicommodity network design. Ann. Oper. Res. 131(1–4), 109–133 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  31. Ghamlouche, I., Crainic, T.G., Gendron, B.: Cycle-based neighborhoods for fixed-charge capacitated multicommodity network design. Oper. Res. 51(4), 655–667 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  32. Goffin, J.-L., Vial, J.-P.: Convex nondifferentiable optimization: a survey focussed on the analytic center cutting plane method. Optim. Methods Softw. 17(5), 805–867 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  33. Gondzio, J., González-Brevis, P., Munari, P.: New Developments in the Primal-dual Column Generation Technique. Technical Report ERGO-11-001, School of Mathematics, The University of Edinburgh (2011)

  34. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  35. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II—Advanced Theory and Bundle Methods, volume 306 of Grundlehren Math. Wiss. Springer, New York (1993)

    Google Scholar 

  36. Holmberg, K., Yuan, D.: A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48(3), 461–481 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  37. Jones, K.L., Lustig, I.J., Farwolden, J.M., Powell, W.B.: Multicommodity network flows: the impact of formulation on decomposition. Math. Program. 62, 95–117 (1993)

    Article  MATH  Google Scholar 

  38. Kiwiel, K., Lemaréchal, C.: An inexact bundle variant suited to column generation. Math. Program. 118, 177–206 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  39. Kiwiel, K.C.: A bundle Bregman proximal method for convex nondifferentiable optimization. Math. Program. 85, 241–258 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  40. Kiwiel, K.C.: A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming. SIAM J. Optim. 17(4), 1015–1034 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  41. Kiwiel, K.C.: An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems. Math. Program. 130(1), 59–84 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  42. Kliewer, G., Timajev, L.: Relax-and-Cut for Capacitated Network Design. In Algorithms—ESA 2005, volume 3669/2005 of Lecture Notes in Computer Science, pages 47–58. Springer, Berlin (2005)

  43. Lemaréchal, C.: Lagrangian relaxation. In: Jünger, M., Naddef, D. (eds.) Computational Combinatorial Optimization, pp. 115–160. Springer, Heidelberg (2001)

    Google Scholar 

  44. Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69, 111–147 (1995)

    Article  MATH  Google Scholar 

  45. Lemaréchal, C., Ouorou, A., Petrou, G.: A bundle-type algorithm for routing in telecommunication data networks. Comput. Optim. Appl. 44(3), 385–409 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  46. Lemaréchal, C., Renaud, A.: A geometric study of duality gaps, with applications. Math. Program. 90, 399–427 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  47. Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  48. Nemirovski, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization, volume XV of Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1983)

    Google Scholar 

  49. Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  50. Nesterov, Y.: Barrier subgradient method. Math. Program. (2013)

  51. Oliveira, W., Sagastizábal, C., Scheimberg, S.: Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21(2), 517–544 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  52. Oskoorouchi, M.R., Goffin, J.-L.: The analytic center cutting plane method with semidefinite cuts. SIAM J. Optim. 13(4), 1029–1053 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  53. Ouorou, A.: A proximal cutting plane method using Chebychev center for nonsmooth convex optimization. Math. Program. 119(2), 239–271 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  54. Ouorou, A.: The proximal Chebychev center cutting plane algorithm for convex additive functions. Math. Program. (2013)

  55. Ruszczynski, A.: Decompostion Methods, Volume 10 of Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2003)

    Google Scholar 

  56. Sagastizábal, C.: Composite proximal bundle method. Math. Program. (2013)

  57. 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)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We are grateful to the anonymous Referees and to the Editor for their insightful comments. The first author gratefully acknowledges financial support of the Italian Ministry of Education, University and Research (MIUR) under grant PRIN 2009XN4ZRR. The second author thanks the financial support of European Commission through the European Social Fund and of the Regione Calabria under grant POR Calabria FSE 2007/2013.

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127 , Pisa, Italy

    Antonio Frangioni

  2. Dipartimento di Elettronica Informatica e Sistemistica, Università della Calabria, 87036 , Rende, CS, Italy

    Enrico Gorgone

Authors
  1. Antonio Frangioni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Enrico Gorgone
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antonio Frangioni.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Frangioni, A., Gorgone, E. Bundle methods for sum-functions with “easy” components: applications to multicommodity network design. Math. Program. 145, 133–161 (2014). https://doi.org/10.1007/s10107-013-0642-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-013-0642-3

Keywords

Mathematics Subject Classification (2000)

Search

Navigation