  


Convex Hull Characterizations of Lexicographic Orderings
Warren Adams(wadamsclemson.edu) Abstract: Given a pdimensional 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 componentwise upperbounded 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 basen expansions, and the solving of n ary knapsack problems having weakly superdecreasing 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. Download: [PDF] Entry Submitted: 12/14/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  