Ideal representations of lexicographic orderings and base-2 expansions of integer variables

作者：Muldoon Frank M; Adams Warren P^*; Sherali Hanif D

来源：Operations Research Letters, 2013, 41(1): 32-39.

DOI：10.1016/j.orl.2012.10.005

• Integer program
• Binary expansion
• Convex hull
• Minimal cover

We use minimal cover and set covering inequalities to define the convex hulls of special sets of binary vectors that are lexicographically lower and upper bounded by given vectors. These convex hulls are used to obtain ideal representations for base-2 expansions of bounded integer variables, and also to afford a new perspective on, and extend convex hull results for, binary knapsack polytopes having weakly super-decreasing coefficients. Computational experience for the base-2 expansions exhibits, on average, a 60% reduction in effort.