Projection with a minimal system of inequalities

被引：10

作者：

Balas, E ^{[1
]}

机构：

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

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 1998年 / 10卷 / 02期

基金：

美国国家科学基金会;

关键词：

projection of polyhedra; combinatorial optimization; facets of polyhedra;

D O I：

10.1023/A:1018368920203

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation that produces a cone whose extreme rays induce facets of the projection.

引用

收藏

页码：189 / 193

页数：5

相关论文

共 10 条

[1] THE PERFECTLY MATCHABLE SUBGRAPH POLYTOPE OF A BIPARTITE GRAPH [J].

BALAS, E ;

PULLEYBLANK, W .

NETWORKS, 1983, 13 (04) :495-516

[2] A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].

BALAS, E ;

CERIA, S ;

CORNUEJOLS, G .

MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324

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

BALAS, E ;

PULLEYBLANK, WR .

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

[4]

BALL MO, 1987, 87466OR I OK OP RES

[5]

GOEMANS MX, 1992, INTEGER PROGRAMMING, P1

[6] CONES OF MATRICES AND SET-FUNCTIONS AND 0-1 OPTIMIZATION [J].

Lovasz, L. ;

Schrijver, A. .

SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (02) :166-190

[7]

Nemhauser GL, 1988, INTEGER COMBINATORIA

[8] SINGLE-MACHINE SCHEDULING POLYHEDRA WITH PRECEDENCE CONSTRAINTS [J].

QUEYRANNE, M ;

WANG, YG .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (01) :1-20

[9] VALID INEQUALITIES AND PROJECTING THE MULTICOMMODITY EXTENDED FORMULATION FOR INCAPACITATED FIXED CHARGE NETWORK FLOW PROBLEMS [J].

RARDIN, RL ;

WOLSEY, LA .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 71 (01) :95-109

[10] A HIERARCHY OF RELAXATIONS BETWEEN THE CONTINUOUS AND CONVEX-HULL REPRESENTATIONS FOR ZERO-ONE PROGRAMMING-PROBLEMS [J].

SHERALI, HD ;

ADAMS, WP .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (03) :411-430