[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Mixed Integer Programming: Analyzing 12 Years of Progress

  • Chapter
Facets of Combinatorial Optimization

Abstract

Back in 2001, Bixby et al. (The Sharpest Cut: The Impact of Manfred Padberg and His Work, pp. 309–325, 2004) provided an analysis of the performance impact of the main mixed integer programming features and improvements up to CPLEX 8.0 for a workshop in honor of Manfred Padberg’s 60th birthday, which was later published in a Festschrift edited by Martin Grötschel (The Sharpest Cut: The Impact of Manfred Padberg and His Work, 2004). Now, 12 years later, Grötschel’s own 65th birthday celebration seems to be the ideal opportunity to provide an update on the state of affairs.

In this paper, we outline an unbiased way to analyze benchmark results and apply this scheme to assess the contribution of the main components in CPLEX 12.5 to the ability to solve MIPs. We highlight some of the more recent features, in particular the deterministic parallel optimizer.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Achterberg, T.: Conflict analysis in mixed integer programming. Discrete Optim. 4(1), 4–20 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007)

    Google Scholar 

  3. Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Achterberg, T.: LP basis selection and cutting planes. In: Mixed Integer Programming Workshop (MIP 2010) (2010)

    Google Scholar 

  5. Achterberg, T., Berthold, T.: Hybrid branching. In: van Hoeve, W.J., Hooker, J. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009). Lecture Notes in Computer Science, vol. 5547, pp. 309–311. Springer, Berlin (2009)

    Chapter  Google Scholar 

  6. Achterberg, T., Raack, C.: The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs. Math. Program. Comput. 2(2), 125–165 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Achterberg, T., Junglas, D., Wunderling, R.: Deterministic parallelization through atomic task computation. US Patent US20120311604 A1 (2011)

    Google Scholar 

  9. Achterberg, T., Berthold, T., Hendel, G.: Rounding and propagation heuristics for mixed integer programming. In: Klatte, D., Lüthi, H.J., Schmedders, K. (eds.) Operations Research Proceedings 2011, pp. 71–76. Springer, Berlin (2012)

    Chapter  Google Scholar 

  10. Achterberg, T., Sabharwal, A., Samulowitz, H.: Stronger inference through implied literals from conflicts and knapsack covers. In: Gomes, C., Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2013). Lecture Notes in Computer Science, vol. 5547. Springer, Berlin (2013)

    Google Scholar 

  11. Amdahl, G.: Validity of the single processor approach to achieving large-scale computing capabilities. In: AFIPS Conference Proceedings, vol. 30, pp. 483–485 (1965)

    Google Scholar 

  12. Bacchus, F.: Enhancing Davis Putnam with extended binary clause reasoning. In: Eighteenth National Conference on Artificial Intelligence, pp. 613–619. American Association for Artificial Intelligence, Menlo Park (2002)

    Google Scholar 

  13. Berthold, T.: Primal heuristics for mixed integer programs. Master’s thesis, Technische Universität Berlin (2006)

    Google Scholar 

  14. Bixby, R.E.: A brief history of linear and mixed-integer programming computation. In: Grötschel, M. (ed.) Optimization Stories, pp. 107–121. Deutsche Mathematiker-Vereinigung, Bielefeld (2012)

    Google Scholar 

  15. Bixby, R.E., Rothberg, E.: Progress in computational mixed integer programming—a look back from the other side of the tipping point. Ann. Oper. Res. 149(1), 37–41 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: MIP: theory and practice—closing the gap. In: Powell, M., Scholtes, S. (eds.) Systems Modelling and Optimization: Methods, Theory, and Applications, pp. 19–49. Kluwer Academic, Norwel (2000)

    Google Scholar 

  17. Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-integer programming: a progress report. In: Grötschel, M. (ed.) The Sharpest Cut: The Impact of Manfred Padberg and His Work. MPS-SIAM Series on Optimization, pp. 309–325. SIAM, Philadelphia (2004)

    Chapter  Google Scholar 

  18. Boehning, R.L., Butler, R.M., Gillett, B.E.: A parallel integer linear programming algorithm. Eur. J. Oper. Res. 34(3), 393–398 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  19. Cook, W.: Markowitz and Manne + Eastman + Land and Doig = branch and bound. In: Grötschel, M. (ed.) Optimization Stories, pp. 227–238. Deutsche Mathematiker-Vereinigung, Bielefeld (2012)

    Google Scholar 

  20. Crowder, H., Johnson, E.L., Padberg, M.W.: Solving large scale zero-one linear programming problems. Oper. Res. 31, 803–834 (1983)

    Article  MATH  Google Scholar 

  21. Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–90 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  22. Danzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393–410 (1954)

    Article  Google Scholar 

  23. Danzig, G.B., Fulkerson, D.R., Johnson, S.M.: On a linear-programming, combinatorial approach to the traveling-salesman problem. Oper. Res. 7, 58–66 (1959)

    Article  Google Scholar 

  24. Eastman, W.: Linear programming with pattern constraints. Ph.D. thesis, Department of Economics, Harvard University, Cambridge, MA, USA (1958)

    Google Scholar 

  25. Eckstein, J.: Parallel branch and bound algorithms for general mixed integer programming on the CM-5. SIAM J. Optim. 4(4), 794–814 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  26. Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  27. Fischetti, M., Lodi, A.: Heuristics in mixed integer programming. In: Cochran, J.J. (ed.) Wiley Encyclopedia of Operations Research and Management Science, vol. 8, pp. 738–747. Wiley, New York (2011)

    Google Scholar 

  28. Fischetti, M., Monaci, M.: Branching on nonchimerical fractionalities. Oper. Res. Lett. 40, 159–164 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  29. Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91–104 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  30. Fourer, R.: On the evolution of optimization modeling systems. In: Grötschel, M. (ed.) Optimization Stories, pp. 377–388. Deutsche Mathematiker-Vereinigung, Bielefeld (2012)

    Google Scholar 

  31. Gendron, B., Crainic, T.G.: Parallel branch-and-bound algorithms: survey and synthesis. Oper. Res. 42(6), 1042–1066 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  32. Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)

    Article  MathSciNet  MATH  Google Scholar 

  33. Grötschel, M. (ed.): The Sharpest Cut: The Impact of Manfred Padberg and His Work. MPS-SIAM Series on Optimization, vol. 4. SIAM, Philadelphia (2004)

    Google Scholar 

  34. Grötschel, M., Jünger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32, 1195–1220 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  35. Karamanov, M., Cornuéjols, G.: Branching on general disjunctions. Math. Program. 128, 403–436 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  36. Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3, 103–163 (2011)

    Article  MathSciNet  Google Scholar 

  37. Koster, A., Zymolka, A., Kutschka, M.: Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts. Algorithmica 55, 375–391 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  38. Land, A., Doig, A.: An automatic method of solving discrete programming problems. Econometrica 28, 497–520 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  39. Linderoth, J.T.: Topics in parallel integer optimization. Ph.D. thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA (1998)

    Google Scholar 

  40. Linderoth, J.T., Savelsbergh, M.W.P.: A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11, 173–187 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  41. Mahajan, A., Ralphs, T.: Experiments with branching using general disjunctions. In: Chinneck, J.W., Kristjansson, B., Saltzman, M.J. (eds.) Operations Research and Cyber-Infrastructure. Operations Research/Computer Science Interfaces Series, vol. 47, pp. 101–118. Springer, Berlin (2009)

    Chapter  Google Scholar 

  42. Margot, F.: Pruning by isomorphism in branch-and-cut. Math. Program. 94(1), 71–90 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  43. Markowitz, H.M., Manne, A.S.: On the solution of discrete programming problems. Econometrica 25, 84–110 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  44. Marques-Silva, J.P., Sakallah, K.A.: GRASP: a search algorithm for propositional satisfiability. IEEE Trans. Comput. 48, 506–521 (1999)

    Article  MathSciNet  Google Scholar 

  45. Matsliah, A., Sabharwal, A., Samulowitz, H.: Augmenting clause learning with implied literals. In: Cimatti, A., Sebastiani, R. (eds.) SAT. Lecture Notes in Computer Science, vol. 7317, pp. 500–501. Springer, Berlin (2012)

    Google Scholar 

  46. Olszewski, M., Ansel, J., Amarasinghe, S.: Kendo: efficient deterministic multithreading in software. ACM SIGPLAN Not. 44(3), 97–108 (2009)

    Article  Google Scholar 

  47. Ostrowski, J., Linderoth, J.T., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126, 147–178 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  48. Owen, J.H., Mehrotra, S.: Experimental results on using general disjunctions in branch-and-bound for general-integer linear programs. Comput. Optim. Appl. 20(2), 159–170 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  49. Padberg, M., Rinaldi, G.: Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6, 1–7 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  50. Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60–100 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  51. Patel, J., Chinneck, J.W.: Active-constraint variable ordering for faster feasibility of mixed integer linear programs. Math. Program. 110, 445–474 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  52. Puget, J.F.: Automatic detection of variable and value symmetries. In: van Beek, P. (ed.) CP 2005. Lecture Notes in Computer Science, vol. 3709, pp. 475–489. Springer, Berlin (2005)

    Google Scholar 

  53. Raidl, G.R., Puchinger, J.: Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In: Blum, C., Aguilera, M., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics. Studies in Computational Intelligence, vol. 114, pp. 31–62. Springer, Berlin (2008)

    Chapter  Google Scholar 

  54. Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19, 534–541 (2007)

    Article  MATH  Google Scholar 

  55. Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  56. SCIP: Solving constraint integer programs. scip.zib.de

  57. Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  58. van Roy, T.J., Wolsey, L.A.: Solving mixed integer programming problems with automatic reformulation. Oper. Res. 35(1), 45–57 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  59. Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. thesis, Technische Universität Berlin (1996)

    Google Scholar 

  60. Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: can a pure cutting plane algorithm work? Math. Program. 130(1), 153–176 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CPLEX Optimization, IBM, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, 14195, Berlin, Germany

    Tobias Achterberg

  2. CPLEX Optimization, IBM, Liebenauer Hauptstr. 2–6, 8041, Graz, Austria

    Roland Wunderling

Authors
  1. Tobias Achterberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roland Wunderling
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tobias Achterberg .

Editor information

Editors and Affiliations

  1. Dept. of Computer Science, University of Cologne, Pohligstr. 1, Cologne, 50969, Germany

    Michael Jünger

  2. Dept. of Computer Science, University of Heidelberg, Im Neuenheimer Feld 326, Heidelberg, 69120, Germany

    Gerhard Reinelt

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Achterberg, T., Wunderling, R. (2013). Mixed Integer Programming: Analyzing 12 Years of Progress. In: Jünger, M., Reinelt, G. (eds) Facets of Combinatorial Optimization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38189-8_18

Download citation

Publish with us

Policies and ethics

Search

Navigation