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.
Citation
Clemson University, Clemson SC, September 2015.
Article
View Convex Hull Characterizations of Lexicographic Orderings