Convex hull characterizations of lexicographic orderings

Given a p-dimensional nonnegative, integral vector $$\varvec{\alpha },$$ α , this paper characterizes the convex hull of the set S of nonnegative, integral vectors $$\varvec{x}$$ x that is lexicographically less than or equal to $$\varvec{\alpha }.$$ α . To obtain a finite number of elements in S, the vectors $$\varvec{x}$$ x are restricted to be component-wise upper-bounded by an integral vector $$\varvec{u}.$$ 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 $$\varvec{u}$$ u takes the same value $$(n-1)$$ ( n - 1 ) for some integer $$n \ge 2,$$ 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$$ n = 2 binary case. They allow for advances relative to both the modeling of integer variables using base-n expansions, and the solving of knapsack problems having weakly super-decreasing coefficients. Insight is gained by alternately constructing the convex hull representation in a higher-variable space using disjunctive programming arguments.