Forbidden Vertices

• 成果类型: Article
• 署名作者: Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S.; Kaibel, Volker
• 署名单位: University System of Georgia; Georgia Institute of Technology; Pontificia Universidad Catolica de Chile; Otto von Guericke University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0673
• 发表日期: 2015
• 页码: 350-360
• 关键词: optimization problems; coloring formulation; PROGRAMS

摘要

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.