  


Convex hulls of superincreasing knapsacks and lexicographic orderings
Akshay Gupte (agupteclemson.edu) Abstract: We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this ndimensional set with O(n) facets. We also establish a distributive property by proving that the convex hull of $\le$ and $\ge$type superincreasing knapsacks can be obtained by intersecting the convex hulls of $\le$ and $\ge$sets taken individually. Our proofs generalize existing results for the 0\1 case. Keywords: superincreasing sequence, lexicographic ordering, greedy solution knapsack, convex hull, linear time complexity Category 1: Integer Programming Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Discrete Applied Mathematics (2015), DOI:10.1016/j.dam.2015.08.010 Download: [PDF] Entry Submitted: 12/04/2012 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  