Georgia Institute of Technology College of Sciences

In this talk, 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 how both P and X are described, that is, on the encoding of the input data. For example, we analyze the case where the complete linear formulation of P is provided, as opposed to the case where P is given by an implicit description (to be defined in the talk). When P has binary vertices only, we provide additional tractability results and linear formulations of polynomial size. Some applications and extensions to integral polytopes will be discussed. Joint work with Shabbir Ahmed, Santanu S. Dey, and Volker Kaibel.