Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Angulo G., Ahmed S., Dey S.S. and Kaibel V. (2015)

Forbidden vertices

Revista : Mathematics of Operations Research
Volumen : 40
Número : 2
Páginas : 350-360
Tipo de publicación : ISI Ir a publicación

Abstract

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.