Set packing relaxations of some integer programs

被引：24

作者：

Borndörfer, R

Weismantel, R

机构：

[1] Konrad Zuse Zentrum Berlin, D-14195 Berlin, Germany

[2] Otto Von Guericke Univ, D-39106 Magdeburg, Germany

来源：

MATHEMATICAL PROGRAMMING | 2000年 / 88卷 / 03期

关键词：

set packing; polyhedral combinatorics; cutting planes; integer programming;

D O I：

10.1007/PL00011381

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper is bout set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.

引用

收藏

页码：425 / 450

页数：26

相关论文

共 30 条

[1] THE PERFECTLY MATCHABLE SUBGRAPH POLYTOPE OF AN ARBITRARY GRAPH [J].

BALAS, E ;

PULLEYBLANK, WR .

COMBINATORICA, 1989, 9 (04) :321-337

[2] ON THE CUT POLYTOPE [J].

BARAHONA, F ;

MAHJOUB, AR .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :157-173

[3] COMPOSITIONS OF GRAPHS AND POLYHEDRA .2. STABLE SETS [J].

BARAHONA, F ;

MAHJOUB, AR .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (03) :359-371

[4] {0,1/2}-Chvatal-Gomory cuts [J].

Caprara, A ;

Fischetti, M .

MATHEMATICAL PROGRAMMING, 1996, 74 (03) :221-235

[5] Wheel inequalities for stable set polytopes [J].

Cheng, E ;

Cunningham, WH .

MATHEMATICAL PROGRAMMING, 1997, 77 (03) :389-421

[6] THE STEINER TREE PROBLEM .2. PROPERTIES AND CLASSES OF FACETS [J].

CHOPRA, S ;

RAO, MR .

MATHEMATICAL PROGRAMMING, 1994, 64 (02) :231-246

[7] THE STEINER TREE PROBLEM .1. FORMULATIONS, COMPOSITIONS AND EXTENSION OF FACETS [J].

CHOPRA, S ;

RAO, MR .

MATHEMATICAL PROGRAMMING, 1994, 64 (02) :209-229

[8] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :138-154

[9]

Deza MM, 1997, Math. Methods Oper. Res., V15, DOI 10.1007/978-3-642-04295-9

[10] GENERALIZATIONS OF CLIQUES, ODD CYCLES AND ANTICYCLES AND THEIR RELATION TO INDEPENDENCE SYSTEM POLYHEDRA [J].

EULER, R ;

JUNGER, M ;

REINELT, G .

MATHEMATICS OF OPERATIONS RESEARCH, 1987, 12 (03) :451-462