Optimization Online


Convex Hull Characterizations of Lexicographic Orderings

Warren Adams(wadams***at***clemson.edu)
Pietro Belotti(pietrobelotti***at***fico.com)
Ruobing Shen(rshen***at***g.clemson.edu)

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.

Download: [PDF]

Entry Submitted: 12/14/2015
Entry Accepted: 12/14/2015
Entry Last Modified: 12/14/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society