Disjunctive programming and relaxations of polyhedra

被引：2

作者：

Conforti, Michele ^{[1
]}

Del Pia, Alberto ^{[2
]}

机构：

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

[2] Swiss Fed Inst Technol, Dept Math, IFOR, CH-8092 Zurich, Switzerland

来源：

MATHEMATICAL PROGRAMMING | 2014年 / 144卷 / 1-2期

关键词：

Mixed integer programming; Disjunctive programming; Polyhedral relaxations; INTERSECTION CUTS; RANK;

D O I：

10.1007/s10107-013-0634-3

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a polyhedron with facets, whose interior contains no integral points, and a polyhedron , recent work in integer programming has focused on characterizing the convex hull of minus the interior of . We show that to obtain such a characterization it suffices to consider all relaxations of defined by at most among the inequalities defining . This extends a result by Andersen, Cornu,jols, and Li.

引用

页码：307 / 314

页数：8

共 14 条

[1] Split closure and intersection cuts [J].

Andersen, K ;

Cornuéjols, G ;

Li, YJ .

MATHEMATICAL PROGRAMMING, 2005, 102 (03) :457-493

[2] An Analysis of Mixed Integer Linear Sets Based on Lattice Point Free Convex Sets [J].

Andersen, Kent ;

Louveaux, Quentin ;

Weismantel, Robert .

MATHEMATICS OF OPERATIONS RESEARCH, 2010, 35 (01) :233-256

[3] Disjunctive programming: Properties of the convex hull of feasible points [J].

Balas, E .

DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) :3-44

[4] A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming [J].

Balas, E ;

Perregaard, M .

MATHEMATICAL PROGRAMMING, 2003, 94 (2-3) :221-245

[5] Generalized intersection cuts and a new cut generating paradigm [J].

Balas, Egon ;

Margot, Francois .

MATHEMATICAL PROGRAMMING, 2013, 137 (1-2) :19-35

[6] Intersection Cuts with Infinite Split Rank [J].

Basu, Amitabh ;

Cornuejols, Gerard ;

Margot, Francois .

MATHEMATICS OF OPERATIONS RESEARCH, 2012, 37 (01) :21-40

[7]

Conforti M., 2012, INTEGER PROGRA UNPUB

[8] Equivalence between intersection cuts and the corner polyhedron [J].

Conforti, Michele ;

Cornuejols, Gerard ;

Zambelli, Giacomo .

OPERATIONS RESEARCH LETTERS, 2010, 38 (03) :153-155

[9] A note on the MIR closure and basic relaxations of polyhedra [J].

Dash, Sanjeeb ;

Guenluek, Oktay ;

Raack, Christian .

OPERATIONS RESEARCH LETTERS, 2011, 39 (03) :198-199

[10] On convergence in mixed integer programming [J].

Del Pia, Alberto ;

Weismantel, Robert .

MATHEMATICAL PROGRAMMING, 2012, 135 (1-2) :397-412

← 1 2 →