Optimization Online


Convex hulls of superincreasing knapsacks and lexicographic orderings

Akshay Gupte (agupte***at***clemson.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 n-dimensional 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
Entry Accepted: 12/04/2012
Entry Last Modified: 01/25/2016

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