[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Relaxations of mixed integer sets from lattice-free polyhedra

  • Invited Survey
  • Published:
4OR Aims and scope Submit manuscript

Abstract

This paper gives an introduction to a recently established link between the geometry of numbers and mixed integer optimization. The main focus is to provide a review of families of lattice-free polyhedra and their use in a disjunctive programming approach. The use of lattice-free polyhedra in the context of deriving and explaining cutting planes for mixed integer programs is not only mathematically interesting, but it leads to some fundamental new discoveries, such as an understanding under which conditions cutting planes algorithms converge finitely.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

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

    Article  Google Scholar 

  • Andersen K, Louveaux Q, Weismantel R (2010) An analysis of mixed integer linear sets based on lattice point free convex sets. Math Oper Res 35: 233–256

    Article  Google Scholar 

  • Andersen K, Louveaux Q, Weismantel R, Wolsey LA (2007) Cutting planes from two rows of a simplex tableau. In: Proceedings of IPCO, lecture notes in computer science , vol 4513, pp 1–15

  • Averkov G (2011) On finite generation and infinite convergence of generalized closures from the theory of cutting planes (manuscript)

  • Averkov G, Wagner C, Weismantel R (2011) Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three. Math Oper Res 36: 721–742

    Article  Google Scholar 

  • Balas E (1971) Intersection cuts—a new type of cutting planes for integer programming. Oper Res 19: 19–39

    Article  Google Scholar 

  • Balas E (1979) Disjunctive programming. Ann Discret Math 5: 3–51

    Article  Google Scholar 

  • Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J Algebraic Discret Methods 6: 466–486

    Article  Google Scholar 

  • Balas E (1998) 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 Applied Mathematics 89:3–44

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

    Article  Google Scholar 

  • Balas E, Margot F (2011) Generalized intersection cuts and a new cut generating paradigm. Math Program A (to appear)

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

    Article  Google Scholar 

  • Basu A, Campelo M, Conforti M, Cornuéjols G, Zambelli G (2010a) On lifting integer variables in minimal inequalities. In: Proceedings of IPCO, lecture notes in computer science, vol 6080, pp 85–95

  • Basu A, Conforti M, Cornuéjols G, Zambelli G (2010b) Maximal lattice-free convex sets in linear subspaces. Math Oper Res 35: 704–720

    Article  Google Scholar 

  • Basu A, Conforti M, Cornuéjols G, Zambelli G (2010c) Minimal inequalities for an infinite relaxation of integer programs. SIAM J Discret Optim 24: 158–168

    Article  Google Scholar 

  • Basu A, Cornuéjols G, Molinaro M (2010d) A probabilistic analysis of the strength of the split and triangle closures. Technical report

  • Basu A, Bonami P, Cornuéjols G, Margot F (2011a) On the relative strength of split, triangle and quadrilateral cuts. Math Program A 126: 281–314

    Article  Google Scholar 

  • Basu A, Campelo M, Conforti M, Cornuéjols G, Zambelli G (2011b) Unique lifting of integer variables in minimal inequalities (manuscript)

  • Basu A, Cornuéjols G, Köppe M (2011c) Unique minimal liftings for simplicial polytopes (manuscript)

  • Basu A, Cornuéjols G, Margot F (2011d) Intersection cuts with infinite split rank. Math Oper Res (to appear)

  • Basu A, Cornuéjols G, Zambelli G (2011e) Convex sets and minimal sublinear functions. J Convex Anal 18(2): 427–432

    Google Scholar 

  • Basu A, Hildebrand R, Köppe M (2011f) Algorithmic and complexity results for cutting planes derived from maximal lattice-free convex sets (manuscript)

  • Bell DE (1977) A theorem concerning the integer lattice. Stud Appl Math 56: 187–188

    Google Scholar 

  • Benoy F, King A, Mesnard F (2005) Computing convex hulls with a linear solver. Theory Pract Logic Program 5(1&2): 259–271

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discret Math 4: 305–337

    Article  Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2010a) Eqivalence between intersection cuts and the corner polyhedron. Oper Res Lett 38: 153–155

    Article  Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2010b) Polyhedral approaches to mixed integer linear programming. In: Juenger M, Liebling T, Naddef D, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L (eds) 50 years of integer programming 1958–2008: from the early years to the state-of-the-art. Springer, Berlin, pp 334–384

    Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2011a) Corner polyhedron and intersection cuts. Surv Oper Res Manag Sci 16: 105–120

    Article  Google Scholar 

  • Conforti M, Cornuéjols G, Zambelli G (2011b) A geometric perspective on lifting. Oper Res 59: 569–577

    Article  Google Scholar 

  • Conforti M, Del Pia A (2011) Disjunctive programming and relaxations of polyhedra. (manuscript)

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Dash S (2010) On the complexity of cutting-plane proofs using split cuts. Ope Res Lett 38: 109–114

    Article  Google Scholar 

  • Dash S, Günlük O, Lodi A (2007) On the MIR closure of polyhedra. In: Proceedings of IPCO, lecture notes in computer science, vol 4513, pp 337–351

  • Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math Program A 121: 33–60

    Article  Google Scholar 

  • Dash S, Dey SS, Günlük O (2011a) On mixed-integer sets with two integer variables. Oper Res Lett 39: 305–309

    Article  Google Scholar 

  • Dash S, Dey SS, Günlük O (2011b) Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math Program A (to appear)

  • Dash S, Dobbs N, Günlük O, Nowicki T, Swirszcz G (2011c) Lattice-free sets, branching disjunctions, and mixed-integer programming (manuscript)

  • Dash S, Günlük O, Raack C (2011d) A note on the MIR closure and basic relaxations of polyhedra. Oper Res Lett 39: 198–199

    Article  Google Scholar 

  • Dash S, Günlük O, Vielma JP (2011e) Computational experiments with cross and crooked cross cuts (manuscript)

  • Del Pia A (2011) On the rank of disjunctive cuts. Math Oper Res (to appear)

  • Del Pia A, Wagner C, Weismantel R (2011) A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts. Oper Res Lett 39: 234–240

    Article  Google Scholar 

  • Del Pia A, Weismantel R (2011) On convergence in mixed integer programming. Math Program A (to appear)

  • Dey SS (2011) A note on the split rank of intersection cuts. Math Program A 130: 107–124

    Article  Google Scholar 

  • Dey SS, Louveaux Q (2011) Split rank of triangle and quadrilateral inequalities. Math Oper Res 36: 432–461

    Article  Google Scholar 

  • Dey SS, Wolsey LA (2008) Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. In: Proceedings of IPCO, lecture notes in computer science, vol 5035, pp 463–475

  • Dey SS, Wolsey LA (2010) Two row mixed-integer cuts via lifting. Math Program B 124: 143–174

    Article  Google Scholar 

  • Fukasawa R, Günlük O (2011) Strengthening lattice-free cuts using non-negativity. Discret Optim 8: 229–245

    Article  Google Scholar 

  • Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math Program 69: 335–349

    Google Scholar 

  • Gomory RE (1963) An algorithm for integer solutions to linear programs. In: Graves RL, Wolfe P (eds) Recent advances in mathematical programming. McGraw-Hill, New York, pp 269–302

    Google Scholar 

  • Gomory RE (1965) On the relation between integer and non-integer solutions to linear programs. In: Proceedings of the National Academy of Sciences, vol 53, pp 260–265

  • Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Algebra Appl 2: 451–558

    Article  Google Scholar 

  • Jörg M (2008) k-disjunctive cuts and cutting plane algorithms for general mixed integer linear programs. Ph.D. thesis, Technische Universität München, München

  • Khachiyan LG (1979) A polynomial algorithm in linear programming (in russian). Doklady Akademii Nauk SSSR 244:1093–1096 (English translation: Soviet Mathematics Doklady 20:191–194)

  • Khachiyan LG (1980) Polynomial algorithms in linear programming (in russian). Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 20:51–68. (English translation: U.S.S.R. Computational Mathematics and Mathematical Physics 20:53–72)

  • Lovász L (1989) Geometry of numbers and integer programming. In: Iri M, Tanabe K (eds) Mathematical programming: recent developments and applications. Kluwer, Dordrecht, pp 177–201

    Google Scholar 

  • Marchand H, Wolsey LA (2001) Aggregation and mixed integer rounding to solve MIPs. Oper Res 49: 363–371

    Article  Google Scholar 

  • Meyer RR (1974) On the existence of optimal solutions to integer and mixed-integer programming problems. Math Program 7: 223–235

    Article  Google Scholar 

  • Morán R, Dey SS (2011) On maximal S-free convex sets. SIAM J Discret Math 25: 379–393

    Article  Google Scholar 

  • Nemhauser GL, Wolsey LA (1990) A recursive procedure to generate all cuts for 0-1 mixed integer programs. Math Program 46: 379–390

    Article  Google Scholar 

  • Nill B, Ziegler GM (2011) Projecting lattice polytopes without interior lattice points. Math Oper Res 36: 462–467

    Article  Google Scholar 

  • Owen JH, Mehrotra S. (2001) A disjunctive cutting plane procedure for general mixed integer linear programs. Math Program A 89: 437–448

    Article  Google Scholar 

  • Rockafellar RT (1970) Convex analysis. Princeton University Press, Princeton

    Google Scholar 

  • Salinetti G, Wets RJ-B (1979) On the convergence of sequences of convex sets in finite dimensions. Soc Ind Appl Math 21: 18–33

    Google Scholar 

  • Scarf HE (1977) An observation on the structure of production sets with indivisiblities. Proc Natl Acad Sci USA 74: 3637–3641

    Article  Google Scholar 

  • Schrijver A (1980) On cutting planes. Ann Discret Math 9: 291–296

    Article  Google Scholar 

  • Schrijver A (1986) Theory of Linear and Integer Programming. Wiley, Chichester

    Google Scholar 

  • Vielma JP (2007) A constructive characterization of the split closure of a mixed integer linear program. Oper Res Lett 35: 29–35

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, IFOR, ETH Zürich, Rämistrasse 101, 8092, Zurich, Switzerland

    Alberto Del Pia & Robert Weismantel

Authors
  1. Alberto Del Pia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Weismantel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Del Pia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Del Pia, A., Weismantel, R. Relaxations of mixed integer sets from lattice-free polyhedra. 4OR-Q J Oper Res 10, 221–244 (2012). https://doi.org/10.1007/s10288-012-0198-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-012-0198-8

Keywords

MSC classification (2000)

Search

Navigation