Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A new warmstarting strategy for the primal-dual column generation method

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

Abstract

This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additionally, the strategy ensures that the duality gap of the warmstart is bounded by the old duality gap multiplied with a (small) constant, which depends on the relation between the old and modified problems. Computational experiments demonstrate the gains achieved when compared to a coldstart approach.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  2. Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)

    Book  Google Scholar 

  3. Benson, H.Y., Shanno, D.F.: An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming. Comput. Optimiz. Appl. 38(3), 371–399 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Gondzio, J.: Warm start of the primal-dual method applied in the cutting-plane scheme. Math. Program. 83, 125–143 (1998)

    MathSciNet  MATH  Google Scholar 

  5. Freund, R.M.: A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”. Math. Program. 52, 441–466 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  6. Engau, A., Anjos, M.F., Vannelli, A.: On interior-point warmstarts for linear and combinatorial optimization. SIAM J. Optimiz. 20(4), 1828–1861 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Mitchell, J.E.: Karmarkar’s algorithm and combinatorial optimization problems. Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University (1988)

  8. Mitchell, J.E., Todd, M.J.: Solving combinatorial optimization problems using Karmarkar’s algorithm. Math. Program. 56, 245–284 (1992)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  10. Goffin, J.L., Vial, J.P.: Multiple cuts in the analytic center cutting plane method. SIAM J. Optimiz. 11(1), 266–288 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Goffin, J.L., Haurie, A., Vial, J.P.: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 38(2), 284–302 (1992)

    Article  MATH  Google Scholar 

  12. Oskoorouchi, M.R., Ghaffari, H.R., Terlaky, T., Aleman, D.M.: An interior point constraint generation algorithm for semi-infinite optimization with health-care application. Oper. Res. 59(5), 1184–1197 (2011)

    Article  MathSciNet  Google Scholar 

  13. Fliege, J.: An efficient interior-point method for convex multicriteria optimization problems. Math. Oper. Res. 31(4), 825–845 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optimiz. 12(3), 782–810 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. John, E., Yildirim, E.A.: Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension. Comput. Optimiz. Appl. 41, 151–183 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gondzio, J., Grothey, A.: Reoptimization with the primal-dual interior point method. SIAM J. Optimiz. 13(3), 842–864 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Gondzio, J., Grothey, A.: A new unblocking technique to warmstart interior point methods based on sensitivity analysis. SIAM J. Optimiz. 19(3), 1184–1210 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Skajaa, A., Andersen, E., Ye, Y.: Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems. Math. Program. Comput. 5(1), 1–25 (2013)

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

    Article  MATH  Google Scholar 

  20. Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007–1023 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. Martinson, R.K., Tind, J.: An interior point method in Dantzig-Wolfe decomposition. Comput. Oper. Res. 26, 1195–1216 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)

    Article  MathSciNet  Google Scholar 

  23. Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M.M.: Vehicle routing problem with time windows. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 67–98. Springer, USA (2005)

    Chapter  Google Scholar 

  24. Trigeiro, W.W., Thomas, L.J., McClain, J.O.: Capacitated lot sizing with setup times. Manag. Sci. 35(3), 353–366 (1989)

    Article  Google Scholar 

  25. Dantzig, G.B., Wolfe, P.: The decomposition algorithm for linear programs. Econometrica 29(4), 767–778 (1961)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  27. Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138–1162 (1970)

    Article  MathSciNet  Google Scholar 

  28. Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees: part II. Math. Program. 1(1), 6–25 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  29. Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789–810 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  30. Nunez, M.A., Freund, R.M.: Condition measures and properties of the central trajectory of a linear program. Math. Program. 83, 1–28 (1998)

    MathSciNet  MATH  Google Scholar 

  31. Gondzio, J.: HOPDM (version 2.12)—a fast LP solver based on a primal-dual interior point method. Eur. J. Oper. Res. 85, 221–225 (1995)

    Article  MATH  Google Scholar 

  32. Gondzio, J., Sarkissian, R.: Column generation with a primal-dual method. Technical Report 96.6, Logilab (1996)

  33. Leão, A.A.S.: Geração de colunas para problemas de corte em duas fases. Master’s thesis, ICMC—University of Sao Paulo, Brazil (2009)

  34. Righini, G., Salani, M.: New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3), 155–170 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  35. Feillet, D., Dejax, P., Gendreau, M., Gueguen, C.: An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle-routing problems. Networks 44, 216–229 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  36. Colombo, M., Gondzio, J.: Further development of multiple centrality correctors for interior point methods. Comput. Optimiz. Appl. 41(3), 277–305 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  37. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We would like to thank the referees for their useful comments and suggestions which allowed us to improve the quality and presentation of this paper. Pablo González-Brevis would like to thank the support given by Facultad de Ingeniería, Universidad del Desarrollo and Beca Presidente de la República (CONICYT) from Chile. Jacek Gondzio was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) under grant EP/G060169/1.

Author information

Authors and Affiliations

  1. School of Mathematics, Maxwell Institute, The University of Edinburgh, Mayfield Road, Edinburgh, EH9 3JZ, UK

    Jacek Gondzio

  2. School of Engineering, Universidad del Desarrollo, Av. Sanhueza 1750, Pedro de Valdivia, Concepción, Chile

    Pablo González-Brevis

Authors
  1. Jacek Gondzio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pablo González-Brevis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo González-Brevis.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gondzio, J., González-Brevis, P. A new warmstarting strategy for the primal-dual column generation method. Math. Program. 152, 113–146 (2015). https://doi.org/10.1007/s10107-014-0779-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0779-8

Keywords

Mathematics Subject Classification (2010)

Search

Navigation