nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

5. Split and Gomory Inequalities

verfasst von : Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli

Erschienen in: Integer Programming

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Chapter 4 dealt with perfect formulations. What can one do when one is handed a formulation that is not perfect? A possible option is to strengthen the formulation in an attempt to make it closer to being perfect. One of the most successful strengthening techniques in practice is the addition of Gomory’s mixed integer cuts. These inequalities have a geometric interpretation, in the context of Balas’ disjunctive programming. They are known as split inequalities in this context, and they are the topic of interest in this chapter. They are also related to the so-called mixed integer rounding inequalities. We show that the convex set defined by intersecting all split inequalities is a polyhedron. For pure integer problems and mixed 0,1 problems, iterating this process a finite number of times produces a perfect formulation. We study Chvátal inequalities and lift-and-project inequalities, which are important special cases of split inequalities. Finally, we discuss cutting planes algorithms based on Gomory inequalities and lift-and-project inequalities, and provide convergence results.

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 Perfect Formulations

Nächstes Kapitel Intersection Cuts and Corner Polyhedra

[11]

K. Andersen, G. Cornuéjols, Y. Li, Split closure and intersection cuts. Math. Program. A 102, 457–493 (2005)CrossRefMATH

[24]

E. Balas, Disjunctive programming: properties of the convex hull of feasible points, GSIA Management Science Research Report MSRR 348, Carnegie Mellon University (1974); Published as invited paper in Discrete Appl. Math. 89, 1–44 (1998)

[27]

E. Balas, A modified lift-and-project procedure. Math. Program. 79, 19–31 (1997)MATHMathSciNet

[28]

E. Balas, P. Bonami, Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Program. Comput. 1, 165–199 (2009)CrossRefMATHMathSciNet

[29]

E. Balas, S. Ceria, G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)CrossRefMATH

[30]

E. Balas, S. Ceria, G. Cornuéjols, R.N. Natraj, Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996)CrossRefMATHMathSciNet

[31]

E. Balas, R. Jeroslow, Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)CrossRefMATHMathSciNet

[32]

E. Balas, M. Perregaard, A precise correspondence between lift-and-project cuts, simple disjunctive cuts and mixed integer Gomory cuts for 0–1 programming. Math. Program. B 94, 221–245 (2003)CrossRefMATHMathSciNet

[34]

E. Balas, A. Saxena, Optimizing over the split closure. Math. Program. 113, 219–240 (2008)CrossRefMATHMathSciNet

[56]

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

[57]

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

[58]

P. Bonami, On optimizing over lift-and-project closures. Math. Program. Comput. 4, 151–179 (2012)CrossRefMATHMathSciNet

[59]

P. Bonami, M. Conforti, G. Cornuéjols, M. Molinaro, G. Zambelli, Cutting planes from two-term disjunctions. Oper. Res. Lett. 41, 442–444 (2013)CrossRefMATHMathSciNet

[60]

P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, A. Lodi, Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Program. 113, 241–257 (2008)CrossRefMATHMathSciNet

[61]

P. Bonami, F. Margot, Cut generation through binarization, IPCO 2014, eds. by J. Lee, J. Vygen. LNCS, vol 8494 (2014) pp. 174–185

[67]

A. Caprara, M. Fischetti, \(\{0, \frac{1} {2}\}\) Chvátal–Gomory cuts. Math. Program. 74, 221–235 (1996)

[68]

A. Caprara, A.N. Letchford, On the separation of split cuts and related inequalities. Math. Program. B 94, 279–294 (2003)CrossRefMATHMathSciNet

[73]

V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial optimization. Discrete Math. 4, 305–337 (1973)CrossRefMATHMathSciNet

[75]

V. Chvátal, W. Cook, M. Hartmann, On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114/115, 455–499 (1989)

[83]

M. Conforti, L.A. Wolsey, G. Zambelli, Split, MIR and Gomory inequalities (2012 submitted)

[88]

W.J. Cook, S. Dash, R. Fukasawa, M. Goycoolea, Numerically accurate Gomory mixed-integer cuts. INFORMS J. Comput. 21, 641–649 (2009)CrossRefMATHMathSciNet

[90]

W.J. Cook, R. Kannan, A. Schrijver, Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)CrossRefMATHMathSciNet

[94]

G. Cornuéjols, Y. Li, On the rank of mixed 0,1 polyhedra. Math. Program. A 91, 391–397 (2002)CrossRefMATH

[95]

G. Cornuéjols, Y. Li, A connection between cutting plane theory and the geometry of numbers. Math. Program. A 93, 123–127 (2002)CrossRefMATH

[107]

S. Dash, O. Günlük, A. Lodi, in On the MIR Closure of Polyhedra, IPCO 2007, ed. by M. Fischetti, D.P. Williamson. LNCS, Springer vol. 4513 (2007), pp. 337–351

[113]

A. Del Pia, R. Weismantel, On convergence in mixed integer programming. Math. Program. 135, 397–412 (2012)

[130]

F. Eisenbrand, On the membership problem for the elementary closure of a polyhedron. Combinatorica 19, 297–300 (1999)CrossRefMATHMathSciNet

[132]

F. Eisenbrand, A.S. Schulz, Bounds on the Chvátal rank of polytopes in the 0/1 cube. Combinatorica 23, 245–261 (2003)CrossRefMATHMathSciNet

[141]

M. Fischetti, A. Lodi, Optimizing over the first Chvátal closure. Math. Program. 110, 3–20 (2007)CrossRefMATHMathSciNet

[142]

M. Fischetti, A. Lodi, A. Tramontani, On the separation of disjunctive cuts. Math. Program. A 128, 205–230 (2011)CrossRefMATHMathSciNet

[159]

R.S. Garfinkel, G. Nemhauser, Integer Programming (Wiley, New York, 1972)MATH

[175]

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

[176]

R.E. Gomory, An algorithm for the mixed integer problem. Tech. Report RM-2597 (The Rand Corporation, 1960)

[177]

R.E. Gomory, An algorithm for integer solutions to linear programs, in Recent Advances in Mathematical Programming, ed. by R.L. Graves, P. Wolfe (McGraw-Hill, New York, 1963), pp. 269–302

[241]

M. Köppe, Q. Louveaux, R. Weismantel, Intermediate integer programming representations using value disjunctions. Discrete Optim. 5, 293–313 (2008)CrossRefMATHMathSciNet

[266]

H. Marchand, L.A. Wolsey, Aggregation and mmixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)CrossRefMATHMathSciNet

[286]

G.L. Nemhauser, L.A. Wolsey, A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Program. 46, 379–390 (1990)CrossRefMATHMathSciNet

[294]

J.H. Owen, S. Mehrotra, A disjunctive cutting plane procedure for general mixed-integer linear programs. Math. Program. A 89, 437–448 (2001)CrossRefMATHMathSciNet

[295]

J.H. Owen, S. Mehrotra, On the value of binary expansions for general mixed-integer linear programs. Oper. Res. 50, 810–819 (2002)CrossRefMATHMathSciNet

[319]

T. Rothvoß, L. Sanitá, 0 − 1 polytopes with quadratic Chvátal rank, in Proceedings of the 16th IPCO Conference. Lecture Notes in Computer Science, vol. 7801 (Springer, New York, 2013)

[320]

J.-S. Roy, Reformulation of bounded integer variables into binary variables to generate cuts. Algorithmic Oper. Res. 2, 810–819 (2007)

[323]

A. Schrijver, On cutting planes. Ann. Discrete Math. 9, 291–296 (1980)CrossRefMATHMathSciNet

[325]

A. Schrijver, Theory of Linear and Integer Programming (Wiley, New York, 1986)MATH

[331]

H. Sherali, W. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Chap. 4 (Kluwer Academic Publishers, Norwell, 1999)

[346]

J.P. Vielma, A constructive characterization of the split closure of a mixed integer linear program. Oper. Res. Lett. 35, 29–35 (2007)CrossRefMATHMathSciNet

Titel: Split and Gomory Inequalities
verfasst von: Michele Conforti
Gérard Cornuéjols
Giacomo Zambelli
Verlag: Springer International Publishing
Buch: Integer Programming
Print ISBN: 978-3-319-11007-3

Electronic ISBN: 978-3-319-11008-0

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-3-319-11008-0_5

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"