Convex Hull Characterizations of Lexicographic Orderings
Abstract: Given a p-dimensional nonnegative, integral vector α, this paper characterizes the convex hull of the set S of nonnegative, integral vectors x that is lexicographically less than or equal to α. To obtain a finite number of elements in S, the vectors x are restricted to be component-wise upper-bounded by an integral vector u. We show that a linear number of facets is sufficient to describe the convex hull. For the special case in which every entry of u takes the same value (n − 1) for some integer n ≥ 2 , the convex hull of the set of n -ary vectors results. Our facets generalize the known family of cover inequalities for the n = 2 binary case. They allow for advances relative to both the modeling of integer variables using base-n expansions, and the solving of n -ary knapsack problems having weakly super-decreasing coefficients.
Keywords: convex hull, facets, knapsack problem
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Combinatorial Optimization (Polyhedra )
Citation: Clemson University, Clemson SC, September 2015.
Entry Submitted: 12/14/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|