Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Martin Grötschel—The Early Years in Bonn and Augsburg Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Mixed Integer Programming: Analyzing 12 Years of Progress

Authors : Tobias Achterberg, Roland Wunderling

Published in: Facets of Combinatorial Optimization

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Scheduling and Routing of Fly-in Safari Planes Using a Flow-over-Flow Model
next chapter Progress in Academic Computational Integer Programming
Literature
1.
2.
Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007)
3.
4.
Achterberg, T.: LP basis selection and cutting planes. In: Mixed Integer Programming Workshop (MIP 2010) (2010)
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) CrossRef
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) MathSciNetMATHCrossRef
7.
8.
Achterberg, T., Junglas, D., Wunderling, R.: Deterministic parallelization through atomic task computation. US Patent US20120311604 A1 (2011)
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) CrossRef
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)
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)
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)
13.
Berthold, T.: Primal heuristics for mixed integer programs. Master’s thesis, Technische Universität Berlin (2006)
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)
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) MathSciNetMATHCrossRef
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)
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) CrossRef
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) MathSciNetMATHCrossRef
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)
20.
Crowder, H., Johnson, E.L., Padberg, M.W.: Solving large scale zero-one linear programming problems. Oper. Res. 31, 803–834 (1983) MATHCrossRef
21.
Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–90 (2005) MathSciNetMATHCrossRef
22.
Danzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393–410 (1954) CrossRef
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) CrossRef
24.
Eastman, W.: Linear programming with pattern constraints. Ph.D. thesis, Department of Economics, Harvard University, Cambridge, MA, USA (1958)
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) MathSciNetMATHCrossRef
26.
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)
28.
29.
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)
31.
32.
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)
34.
Grötschel, M., Jünger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32, 1195–1220 (1984) MathSciNetMATHCrossRef
35.
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) MathSciNetCrossRef
37.
Koster, A., Zymolka, A., Kutschka, M.: Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts. Algorithmica 55, 375–391 (2009) MathSciNetMATHCrossRef
38.
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)
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) MathSciNetMATHCrossRef
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) CrossRef
42.
43.
44.
Marques-Silva, J.P., Sakallah, K.A.: GRASP: a search algorithm for propositional satisfiability. IEEE Trans. Comput. 48, 506–521 (1999) MathSciNetCrossRef
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)
46.
Olszewski, M., Ansel, J., Amarasinghe, S.: Kendo: efficient deterministic multithreading in software. ACM SIGPLAN Not. 44(3), 97–108 (2009) CrossRef
47.
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) MathSciNetMATHCrossRef
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) MathSciNetMATHCrossRef
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) MathSciNetMATHCrossRef
51.
Patel, J., Chinneck, J.W.: Active-constraint variable ordering for faster feasibility of mixed integer linear programs. Math. Program. 110, 445–474 (2007) MathSciNetMATHCrossRef
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)
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) CrossRef
54.
Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19, 534–541 (2007) MATHCrossRef
55.
Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994) MathSciNetMATHCrossRef
56.
57.
58.
van Roy, T.J., Wolsey, L.A.: Solving mixed integer programming problems with automatic reformulation. Oper. Res. 35(1), 45–57 (1987) MathSciNetMATHCrossRef
59.
Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. thesis, Technische Universität Berlin (1996)
60.
Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: can a pure cutting plane algorithm work? Math. Program. 130(1), 153–176 (2011) MathSciNetMATHCrossRef
Metadata
Title
Mixed Integer Programming: Analyzing 12 Years of Progress
Authors
Tobias Achterberg
Roland Wunderling
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Facets of Combinatorial Optimization

Print ISBN: 978-3-642-38188-1

Electronic ISBN: 978-3-642-38189-8

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-38189-8_18