-

 

 

 




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: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Integer Programming

Category 3: Combinatorial Optimization (Polyhedra )

Citation:

Download: [PDF]

Entry Submitted: 09/09/2013
Entry Accepted: 09/09/2013
Entry Last Modified: 09/10/2013

Modify/Update this entry


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

 

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