Forbidden Vertices

被引：19

作者：

Angulo, Gustavo ^{[1
,2
]}

Ahmed, Shabbir ^{[1
]}

Dey, Santanu S. ^{[1
]}

Kaibel, Volker ^{[3
]}

机构：

[1] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[2] Pontificia Univ Catolica Chile, Dept Ingn Ind & Sistemas, Santiago 13101, Chile

[3] Univ Magdeburg, Inst Math Optimierung, D-39106 Magdeburg, Germany

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2015年 / 40卷 / 02期

关键词：

forbidden vertices; vertex enumeration; extended formulation; k-best solutions; all-different polytopes; OPTIMIZATION PROBLEMS; COLORING FORMULATION; PROGRAMS;

D O I：

10.1287/moor.2014.0673

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations when P has binary vertices only. Some applications and extensions to integral polytopes are discussed.

引用

页码：350 / 360

页数：11

共 19 条

[1] How good are convex hull algorithms? [J].

Avis, D ;

Bremner, D ;

Seidel, R .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 7 (5-6) :265-301

[2] The negative cycles polyhedron and hardness of checking some polyhedral properties [J].

Boros, Endre ;

Elbassioni, Khaled ;

Gurvich, Vladimir ;

Tiwary, Hans Raj .

ANNALS OF OPERATIONS RESEARCH, 2011, 188 (01) :63-76

[3] Extended formulations in combinatorial optimization [J].

Conforti, Michele ;

Cornuejols, Gerard ;

Zambelli, Giacomo .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (01) :1-48

[4]

Fiorini S, 2013, PREPRINT

[5]

Fiorini S, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P95

[6]

Gupte A, 2013, PREPRINT

[7] Generating all vertices of a polyhedron is hard [J].

Khachiyan, Leonid ;

Boros, Endre ;

Borys, Konrad ;

Elbassioni, Khaled ;

Gurvich, Vladimir .

DISCRETE & COMPUTATIONAL GEOMETRY, 2008, 39 (1-3) :174-190

[8] THE INTEGER L-SHAPED METHOD FOR STOCHASTIC INTEGER PROGRAMS WITH COMPLETE RECOURSE [J].

LAPORTE, G ;

LOUVEAUX, FV .

OPERATIONS RESEARCH LETTERS, 1993, 13 (03) :133-142

[9] PROCEDURE FOR COMPUTING K BEST SOLUTIONS TO DISCRETE OPTIMIZATION PROBLEMS AND ITS APPLICATION TO SHORTEST PATH PROBLEM [J].

LAWLER, EL .

MANAGEMENT SCIENCE SERIES A-THEORY, 1972, 18 (07) :401-405

[10] Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation [J].

Lee, J ;

Leung, J ;

De Vries, S .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (01) :59-67

← 1 2 →