Convex hull characterizations of lexicographic orderings

Given a p‐dimensional nonnegative, integral vector $‐{\alpha },$ this paper characterizes the convex hull of the set S of nonnegative, integral vectors $‐{x}$ that is lexicographically less than or equal to $‐{\alpha }.$ 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\ge 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 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.