Skip to main content

2014 | OriginalPaper | Buchkapitel

6. Intersection Cuts and Corner Polyhedra

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

Erschienen in: Integer Programming

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

In this chapter, we present two classical points of view for approximating a mixed integer linear set: Gomory’s corner polyhedron and Balas’ intersection cuts. It turns out that they are equivalent: the nontrivial valid inequalities for the corner polyhedron are exactly the intersection cuts. Within this framework, we stress two ideas: the best possible intersection cuts are generated from maximal lattice-free convex sets, and formulas for these cuts can be interpreted using the so-called infinite relaxation.

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!

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!

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!

Literatur
[12]
Zurück zum Zitat K. Andersen, Q. Louveaux, R. Weismantel, L.A. Wolsey, Inequalities from two rows of a simplex tableau, in Proceedings of IPCO XII, Ithaca, NY. Lecture Notes in Computer Science, vol. 4513 (2007), pp. 1–15CrossRefMathSciNet K. Andersen, Q. Louveaux, R. Weismantel, L.A. Wolsey, Inequalities from two rows of a simplex tableau, in Proceedings of IPCO XII, Ithaca, NY. Lecture Notes in Computer Science, vol. 4513 (2007), pp. 1–15CrossRefMathSciNet
[18]
Zurück zum Zitat G. Averkov, On maximal S-free sets and the Helly number for the family of S-convex sets. SIAM J. Discrete Math. 27(3), 1610–1624 (2013)CrossRefMATHMathSciNet G. Averkov, On maximal S-free sets and the Helly number for the family of S-convex sets. SIAM J. Discrete Math. 27(3), 1610–1624 (2013)CrossRefMATHMathSciNet
[19]
Zurück zum Zitat G. Averkov, A. Basu, On the unique lifting property, IPCO 2014, Bonn, Germany, Lecture Notes in Computer Science, 8494, 76–87 (2014)CrossRef G. Averkov, A. Basu, On the unique lifting property, IPCO 2014, Bonn, Germany, Lecture Notes in Computer Science, 8494, 76–87 (2014)CrossRef
[22]
[23]
[39]
Zurück zum Zitat A. Barvinok, A Course in Convexity. Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, 2002) A. Barvinok, A Course in Convexity. Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, 2002)
[40]
Zurück zum Zitat A. Basu, M. Campelo, M. Conforti, G. Cornuéjols, G. Zambelli, On lifting integer variables in minimal inequalities. Math. Program. A 141, 561–576 (2013)CrossRefMATH A. Basu, M. Campelo, M. Conforti, G. Cornuéjols, G. Zambelli, On lifting integer variables in minimal inequalities. Math. Program. A 141, 561–576 (2013)CrossRefMATH
[41]
Zurück zum Zitat A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35, 704–720 (2010)CrossRefMATHMathSciNet A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35, 704–720 (2010)CrossRefMATHMathSciNet
[42]
Zurück zum Zitat A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24, 158–168 (2010)CrossRefMATHMathSciNet A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24, 158–168 (2010)CrossRefMATHMathSciNet
[43]
Zurück zum Zitat A. Basu, R. Hildebrand, M. Köppe, M. Molinaro, A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation. SIAM J. Optim. 23(2), 1021–1040 (2013)CrossRefMATHMathSciNet A. Basu, R. Hildebrand, M. Köppe, M. Molinaro, A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation. SIAM J. Optim. 23(2), 1021–1040 (2013)CrossRefMATHMathSciNet
[44]
Zurück zum Zitat A. Basu, R. Hildebrand, M. Köppe, Equivariant perturbation in Gomory and Johnson infinite group problem III. Foundations for the k-dimensional case with applications to the case k = 2. www.optimization-online.org (2014) A. Basu, R. Hildebrand, M. Köppe, Equivariant perturbation in Gomory and Johnson infinite group problem III. Foundations for the k-dimensional case with applications to the case k = 2. www.​optimization-online.​org (2014)
[45]
Zurück zum Zitat D.E. Bell, A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187–188 (1977)MATH D.E. Bell, A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187–188 (1977)MATH
[63]
[78]
Zurück zum Zitat M. Conforti, G. Cornuéjols, G. Zambelli, Equivalence between intersection cuts and the corner polyhedron. Oper. Res. Lett. 38, 153–155 (2010)CrossRefMATHMathSciNet M. Conforti, G. Cornuéjols, G. Zambelli, Equivalence between intersection cuts and the corner polyhedron. Oper. Res. Lett. 38, 153–155 (2010)CrossRefMATHMathSciNet
[80]
Zurück zum Zitat M. Conforti, G. Cornuéjols, G. Zambelli, Corner polyhedron and intersection cuts. Surv. Oper. Res. Manag. Sci. 16, 105–120 (2011) M. Conforti, G. Cornuéjols, G. Zambelli, Corner polyhedron and intersection cuts. Surv. Oper. Res. Manag. Sci. 16, 105–120 (2011)
[106]
Zurück zum Zitat S. Dash, S.S. Dey, O. Günlük, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math. Program. 135, 221–254 (2012)CrossRefMATHMathSciNet S. Dash, S.S. Dey, O. Günlük, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math. Program. 135, 221–254 (2012)CrossRefMATHMathSciNet
[112]
Zurück zum Zitat A. Del Pia, R. Weismantel, Relaxations of mixed integer sets from lattice-free polyhedra. 4OR 10, 221–244 (2012) A. Del Pia, R. Weismantel, Relaxations of mixed integer sets from lattice-free polyhedra. 4OR 10, 221–244 (2012)
[115]
[117]
Zurück zum Zitat S.S. Dey, J.-P.P. Richard, Y. Li, L.A. Miller, On the extreme inequalities of infinite group problems. Math. Program. A 121, 145–170 (2010)CrossRefMATHMathSciNet S.S. Dey, J.-P.P. Richard, Y. Li, L.A. Miller, On the extreme inequalities of infinite group problems. Math. Program. A 121, 145–170 (2010)CrossRefMATHMathSciNet
[118]
Zurück zum Zitat S.S. Dey, L.A. Wolsey, Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles, IPCO 2008, Bertinoro, Italy. Lecture Notes in Computer Science, Springer, vol. 5035 (2008), pp. 463–475CrossRefMathSciNet S.S. Dey, L.A. Wolsey, Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles, IPCO 2008, Bertinoro, Italy. Lecture Notes in Computer Science, Springer, vol. 5035 (2008), pp. 463–475CrossRefMathSciNet
[119]
[179]
[201]
Zurück zum Zitat J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of Convex Analysis (Springer, New York, 2001)CrossRefMATH J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of Convex Analysis (Springer, New York, 2001)CrossRefMATH
[215]
Zurück zum Zitat E.L. Johnson, On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)CrossRef E.L. Johnson, On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)CrossRef
[216]
Zurück zum Zitat E.L. Johnson, Characterization of facets for multiple right-hand choice linear programs. Math. Program. Study 14, 112–142 (1981)CrossRefMATH E.L. Johnson, Characterization of facets for multiple right-hand choice linear programs. Math. Program. Study 14, 112–142 (1981)CrossRefMATH
[261]
Zurück zum Zitat L. Lovász, Geometry of numbers and integer programming, in Mathematical Programming: Recent Developments and Applications, ed. by M. Iri, K. Tanabe (Kluwer, Dordrecht, 1989), pp. 177–201 L. Lovász, Geometry of numbers and integer programming, in Mathematical Programming: Recent Developments and Applications, ed. by M. Iri, K. Tanabe (Kluwer, Dordrecht, 1989), pp. 177–201
[315]
Zurück zum Zitat J.-P.P. Richard, S.S. Dey (2010). The group-theoretic approach in mixed integer programming, in 50 Years of Integer Programming 1958–2008, ed. by M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, L. Wolsey (Springer, New York, 2010), pp. 727–801 J.-P.P. Richard, S.S. Dey (2010). The group-theoretic approach in mixed integer programming, in 50 Years of Integer Programming 1958–2008, ed. by M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, L. Wolsey (Springer, New York, 2010), pp. 727–801
[316]
Zurück zum Zitat R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, 1969) R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, 1969)
[322]
Zurück zum Zitat H.E. Scarf, An observation on the structure of production sets with indivisibilities. Proc. Natl. Acad. Sci. USA 74, 3637–3641 (1977)CrossRefMATHMathSciNet H.E. Scarf, An observation on the structure of production sets with indivisibilities. Proc. Natl. Acad. Sci. USA 74, 3637–3641 (1977)CrossRefMATHMathSciNet
Metadaten
Titel
Intersection Cuts and Corner Polyhedra
verfasst von
Michele Conforti
Gérard Cornuéjols
Giacomo Zambelli
Copyright-Jahr
2014
DOI
https://doi.org/10.1007/978-3-319-11008-0_6