Convex hull characterizations of lexicographic orderings

Warren Adams (), Pietro Belotti and Ruobing Shen
Additional contact information
Warren Adams: Clemson University
Pietro Belotti: FICO
Ruobing Shen: Universität Heidelberg

Journal of Global Optimization, 2016, vol. 66, issue 2, No 8, 329 pages

Abstract: Abstract 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.

Keywords: Convex hull; Facets; Knapsack problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0435-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:66:y:2016:i:2:d:10.1007_s10898-016-0435-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0435-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().