MINIMAL INEQUALITIES FOR AN INFINITE RELAXATION OF INTEGER PROGRAMS

被引：37

作者：

Basu, Amitabh ^{[1
]}

Conforti, Michele ^{[2
]}

Cornuejols, Gerard ^{[3
,4
]}

Zambelli, Giacomo ^{[2
]}

机构：

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

[2] Univ Padua, Dipartimento Matemat Pura & Applicata, I-35121 Padua, Italy

[3] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA

[4] Univ Aix Marseille, Fac Sci Luminy, F-13288 Marseille, France

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2010年 / 24卷 / 01期

关键词：

integer programming; cutting planes; maximal lattice-free convex sets;

D O I：

10.1137/090756375

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that maximal S-free convex sets are polyhedra when S is the set of integral points in some rational polyhedron of R-n. This result extends a theorem of Lovasz characterizing maximal lattice-free convex sets. Our theorem has implications in integer programming. In particular, we show that maximal S-free convex sets are in one-to-one correspondence with minimal inequalities.

引用

页码：158 / 168

页数：11

共 11 条

[1]

Andersen K, 2007, LECT NOTES COMPUT SC, V4513, P1

[2] INTERSECTION CUTS - NEW TYPE OF CUTTING PLANES FOR INTEGER PROGRAMMING [J].

BALAS, E .

OPERATIONS RESEARCH, 1971, 19 (01) :19-+

[3]

Barvinok A, 2002, Graduate Studies in Mathematics, V54

[4]

BASU A, 2009, MAXIMAL LATTIC UNPUB

[5]

BASU A, 2009, CONVEX SETS MI UNPUB

[6] Minimal Valid Inequalities for Integer Constraints [J].

Borozan, Valentin ;

Cornuejols, Gerard .

MATHEMATICS OF OPERATIONS RESEARCH, 2009, 34 (03) :538-546

[7]

DEY SS, 2009, CONSTRAINED IN UNPUB

[8]

JOHNSON EL, 1981, MATH PROGRAM STUD, V14, P112, DOI 10.1007/BFb0120925

[9]

LOVASZ L, 1989, MATH PROGRAMMING REC, P177

[10]

Schrijver Alexander, 1986, Theory of Linear and Integer Programming

← 1 2 →