Minimal Valid Inequalities for Integer Constraints

被引：55

作者：

Borozan, Valentin ^{[1
]}

Cornuejols, Gerard ^{[1
,2
]}

机构：

[1] Univ Marseille, Fac Sci Luminy, LIF, F-13288 Marseille, France

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

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2009年 / 34卷 / 03期

关键词：

integer programming; lattice-free convex set; corner polyhedron;

D O I：

10.1287/moor.1080.0370

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative, piecewise linear, positively homogeneous, convex functions.

引用

页码：538 / 546

页数：9

共 20 条

[1]

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

[2]

[Anonymous], 1963, Recent Advances in Mathematical Programming

[3]

[Anonymous], 1972, Mathematical Programming, DOI DOI 10.1007/BF01585008

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

BALAS, E .

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

[5]

BASU A, 2009, MATH OPER R IN PRESS

[6]

BASU A, 2008, E38 CARN MELL U TEPP

[7]

BELL DE, 1977, STUD APPL MATH, V56, P187

[8] CHVATAL CLOSURES FOR MIXED INTEGER PROGRAMMING-PROBLEMS [J].

COOK, W ;

KANNAN, R ;

SCHRIJVER, A .

MATHEMATICAL PROGRAMMING, 1990, 47 (02) :155-174

[9]

CORNUEJOLS G, 2008, MATH PROGRAMMING

[10]

Dey SS, 2008, LECT NOTES COMPUT SC, V5035, P463, DOI 10.1007/978-3-540-68891-4_32

← 1 2 →