Optimization Online


Forbidding extreme points from the 0-1 hypercube

Gustavo Angulo(gangulo***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Santanu S. Dey(santanu.dey***at***isye.gatech.edu)

Abstract: Let B be the set of n-dimensional binary vectors and let V be a subset of m of its elements. We give an extended formulation of the convex hull of B\V which is polynomial in n and m. In developing this result, we give a two-sided extension of a result in Laurent and Sassano (1992) for knapsack sets with superincreasing coefficients.

Keywords: Binary hypercube; Binary Knapsack; Superincreasing Coefficients

Category 1: Integer Programming

Category 2: Integer Programming (0-1 Programming )

Citation: Technical Report, ISyE, Georgia Tech, 2012.

Download: [PDF]

Entry Submitted: 05/10/2012
Entry Accepted: 05/10/2012
Entry Last Modified: 05/10/2012

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