Maximal Lattice-Free Convex Sets in Linear Subspaces

被引：60

作者：

Basu, Amitabh ^{[1
]}

Conforti, Michele ^{[2
]}

Cornuejols, Gerard ^{[1
]}

Zambelli, Giacomo ^{[2
]}

机构：

[1] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA

[2] Univ Padua, Dept Pure & Appl Math, I-35121 Padua, Italy

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2010年 / 35卷 / 03期

基金：

美国安德鲁·梅隆基金会;

关键词：

geometry of numbers; integer programming; maximal lattice-free convex sets; minimal valid inequalities; SIMPLEX TABLEAU; CUTTING PLANES; INTEGER; INEQUALITIES; VARIABLES; ROWS; CUTS;

D O I：

10.1287/moor.1100.0461

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a model that arises in integer programming and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that these sets are polyhedra. The latter result extends a theorem of Lovasz characterizing maximal lattice-free convex sets in R-n.

引用

页码：704 / 720

页数：17

共 23 条

[1] ON MAXIMAL S-FREE CONVEX SETS
Moran R, Diego A.
Dey, Santanu S.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (01) : 379 - 393
[2] Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three
Averkov, Gennadiy
Wagner, Christian
Weismantel, Robert
MATHEMATICS OF OPERATIONS RESEARCH, 2011, 36 (04) : 721 - 742
[3] Relaxations of mixed integer sets from lattice-free polyhedra
Del Pia, Alberto
Weismantel, Robert
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2012, 10 (03): : 221 - 244
[4] Lifting properties of maximal lattice-free polyhedra
Averkov, Gennadiy
Basu, Amitabh
MATHEMATICAL PROGRAMMING, 2015, 154 (1-2) : 81 - 111
[5] Relaxations of mixed integer sets from lattice-free polyhedra
Del Pia, Alberto
Weismantel, Robert
ANNALS OF OPERATIONS RESEARCH, 2016, 240 (01) : 95 - 117
[6] Relaxations of mixed integer sets from lattice-free polyhedra
Alberto Del Pia
Robert Weismantel
4OR, 2012, 10 : 221 - 244
[7] Relaxations of mixed integer sets from lattice-free polyhedra
Alberto Del Pia
Robert Weismantel
Annals of Operations Research, 2016, 240 : 95 - 117
[8] Constructing Lattice-Free Gradient Polyhedra in Dimension Two
Paat, Joseph
Schloter, Miriam
Speakman, Emily
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2020, 2020, 12125 : 364 - 377
[9] Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
Dash, Sanjeeb
Dobbs, Neil B.
Guenluek, Oktay
Nowicki, Tomasz J.
Swirszcz, Grzegorz M.
MATHEMATICAL PROGRAMMING, 2014, 145 (1-2) : 483 - 508
[10] Lattice-Free Simplices with Lattice Width 2d - o(d)
Mayrhofer, Lukas
Schade, Jamico
Weltge, Stefan
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2022, 2022, 13265 : 375 - 386

← 1 2 3 →