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 条
123