Relaxations of mixed integer sets from lattice-free polyhedra

被引:0
作者
Alberto Del Pia
Robert Weismantel
机构
[1] IFOR,Department of Mathematics
[2] ETH Zürich,undefined
来源
4OR | 2012年 / 10卷
关键词
Mixed integer programming; Cutting planes; Disjunctive programming; Lattice-free polyhedra; Primary 90C11; Secondary 90C10;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:221 / 244
页数:23
相关论文
共 91 条
  • [1] Andersen K(2005)Split closure and intersection cuts Math Program A 102 457-493
  • [2] Cornuéjols G(2010)An analysis of mixed integer linear sets based on lattice point free convex sets Math Oper Res 35 233-256
  • [3] Li Y(2011)Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three Math Oper Res 36 721-742
  • [4] Andersen K(1971)Intersection cuts—a new type of cutting planes for integer programming Oper Res 19 19-39
  • [5] Louveaux Q(1979)Disjunctive programming Ann Discret Math 5 3-51
  • [6] Weismantel R(1985)Disjunctive programming and a hierarchy of relaxations for discrete optimization problems SIAM J Algebraic Discret Methods 6 466-486
  • [7] Averkov G(1993)A lift-and-project cutting plane algorithm for mixed 0-1 programs Math Program 58 295-324
  • [8] Wagner C(2008)Optimizing over the split closure Math Program A 113 219-240
  • [9] Weismantel R(2010)Maximal lattice-free convex sets in linear subspaces Math Oper Res 35 704-720
  • [10] Balas E(2010)Minimal inequalities for an infinite relaxation of integer programs SIAM J Discret Optim 24 158-168