nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Structure-Based Primal Heuristics for Mixed Integer Programming

verfasst von : Gerald Gamrath, Timo Berthold, Stefan Heinz, Michael Winkler

Erschienen in: Optimization in the Real World

Verlag: Springer Japan

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.

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 ppOpen-HPC: Open Source Infrastructure for Development and Execution of Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning (AT)

Nächstes Kapitel Optimal Turbine Allocation for Offshore and Onshore Wind Farms

For a definition and discussion of the shifted geometric mean, see [1, Appendix A]. We use shifts of 10 and 100 for time and nodes, respectively.

We compute the average primal gap by means of the primal integral [7] as \(\frac{P(\text {t}_{\text {max}})}{\text {t}_{\text {max}}}\) with \(\text {t}_{\text {max}}= 3600\) s, \(P(x) = \int _{t = 0}^{x} \gamma (t)\,dt\) and \(\gamma (t)\) the primal gap at time t.

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

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

Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1–12 (2006). doi:10.1016/j.orl.2005.07.009 MathSciNetCrossRef

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

Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449–481. Springer (2013)

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

Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013)MATHMathSciNetCrossRef

Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014)

Berthold, T.: RENS—the optimal rounding. Math. Program. Comput. 6(1), 33–54 (2014)MATHMathSciNetCrossRef

10.

Berthold, T., Hendel, G.: Shift-and-propagate. J. Heuristics 21(1), 73–106 (2015)

11.

Bixby, R.E.: A brief history of linear and mixed-integer programming computation. Documenta Mathematica pp. 107–121 (2012)

12.

Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12–15 (1998)

13.

Borndörfer, R., Grötschel, M., Jäger, U.: Planning problems in public transit. In: Grötschel, M., Lucas, K., Mehrmann, V. (eds.) Production Factor Mathematics, pp. 95–121. Springer, Berlin (2010)CrossRef

14.

COR@L: MIP Instances (2014). http://coral.ie.lehigh.edu/data-sets/mixed-integer-instances/

15.

Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250–255 (1965)MATHMathSciNetCrossRef

16.

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

17.

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

18.

Fischetti, M., Lodi, A.: Heuristics in mixed integer programming. In: J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh, J.C. Smith (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley (2010)

19.

Ghosh, S.: DINS, a MIP improvement heuristic. In: Fischetti, M., Williamson, D.P. (eds.) 12th International IPCO Conference, Proceedings of the Integer Programming and Combinatorial Optimization, LNCS, vol. 4513, pp. 310–323. Springer, Berlin (2007)

20.

Heinz, S., Ku, W.Y., Beck, J.: Recent improvements using constraint integer programming for resource allocation and scheduling. In: Gomes, C., Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 7874, pp. 12–27. Springer, Berlin (2013)CrossRef

21.

Johnson, E.L., Padberg, M.W.: Degree-two inequalities, clique facets, and biperfect graphs. North-Holland Math. Stud. 66, 169–187 (1982)MathSciNetCrossRef

22.

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(2), 103–163 (2011)MathSciNetCrossRef

23.

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

24.

Lee, E., Lewis, D.: Integer programming for telecommunications. In: Resende, M., Pardalos, P. (eds.) Handbook of Optimization in Telecommunications, pp. 67–102. Springer, US (2006)CrossRef

25.

Lodi, A.: Mixed integer programming computation. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958–2008, pp. 619–645. Springer, Berlin (2010)

26.

Lodi, A.: The heuristic (dark) side of MIP solvers. In: Talbi, E.G. (ed.) Hybrid Metaheuristics, Studies in Computational Intelligence, vol. 434, pp. 273–284. Springer, Berlin (2013)CrossRef

27.

Marchand, H., Wolsey, L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49(3), 363–371 (2001). doi:10.1287/opre.49.3.363.11211 MATHMathSciNetCrossRef

28.

Pochet, Y., Wolsey, L.A.: Production Planning by Mixed Integer Programming. Springer Science and Business Media, Heidelberg (2006)

29.

Pryor, J., Chinneck, J.W.: Faster integer-feasibility in mixed-integer linear programs by branching to force change. Comput. Oper. Res. 38(8), 1143–1152 (2011)MATHMathSciNetCrossRef

30.

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

31.

Salvagnin, D.: Detecting and exploiting permutation structures in MIPs. In: Simonis, H. (ed.) Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science, vol. 8451, pp. 29–44. Springer, Berlin (2014)CrossRef

32.

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

33.

Winkler, M.: Presolving for pseudo-Boolean optimization problems. Diploma thesis, Tech-nische Universität Berlin (2014)

34.

Wunderling, R.: Paralleler und objektorientierter Simplex-algorithmus. Ph.D. thesis, Tech-nische Universität Berlin (1996)

Titel: Structure-Based Primal Heuristics for Mixed Integer Programming
verfasst von: Gerald Gamrath
Timo Berthold
Stefan Heinz
Michael Winkler
Verlag: Springer Japan
Buch: Optimization in the Real World
Print ISBN: 978-4-431-55419-6

Electronic ISBN: 978-4-431-55420-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-4-431-55420-2_3

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner

Marktübersichten