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:
Advanced Computing and Optimization Infrastructure for Extremely Large-Scale Graphs on Post Peta-Scale Supercomputers Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Structure-Based Primal Heuristics for Mixed Integer Programming

Authors : Gerald Gamrath, Timo Berthold, Stefan Heinz, Michael Winkler

Published in: Optimization in the Real World

Publisher: Springer Japan

Log in

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

search-config
loading …

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.

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 ppOpen-HPC: Open Source Infrastructure for Development and Execution of Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning (AT)
next chapter Optimal Turbine Allocation for Offshore and Onshore Wind Farms
Footnotes
1
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.
 
2
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.
 
Literature
1.
Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007)
2.
3.
4.
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
5.
Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449–481. Springer (2013)
6.
Berthold, T.: Primal heuristics for mixed integer programs. Diploma thesis, Technische Universität Berlin (2006)
7.
8.
Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014)
9.
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.
15.
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.
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.
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.
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)
Metadata
Title
Structure-Based Primal Heuristics for Mixed Integer Programming
Authors
Gerald Gamrath
Timo Berthold
Stefan Heinz
Michael Winkler
Copyright Year
2016
Publisher
Springer Japan
Book
Optimization in the Real World

Print ISBN: 978-4-431-55419-6

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

Copyright Year: 2016

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

Premium Partners

    Image Credits