Forbidding extreme points from the 0-1 hypercube
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.
Entry Submitted: 05/10/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|