Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Martin Grötschel—The Early Years in Bonn and Augsburg Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Mixed Integer Programming: Analyzing 12 Years of Progress

verfasst von : Tobias Achterberg, Roland Wunderling

Erschienen in: Facets of Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Scheduling and Routing of Fly-in Safari Planes Using a Flow-over-Flow Model
Nächstes Kapitel Progress in Academic Computational Integer Programming
Literatur
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.
Gendron, B., Crainic, T.G.: Parallel branch-and-bound algorithms: survey and synthesis. Oper. Res. 42(6), 1042–1066 (1994) MathSciNetMATHCrossRef
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
Metadaten
Titel
Mixed Integer Programming: Analyzing 12 Years of Progress
verfasst von
Tobias Achterberg
Roland Wunderling
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Facets of Combinatorial Optimization

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

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

Copyright-Jahr: 2013

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

Premium Partner

    Bildnachweise