Optimization Online


Forbidden vertices

Gustavo Angulo (gangulo***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Volker Kaibel (kaibel***at***ovgu.de)

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.

Keywords: forbidden vertices; vertex enumeration; extended formulation; k-best solutions; all-different polytopes

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 09/11/2013
Entry Accepted: 09/11/2013
Entry Last Modified: 03/01/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society