×

Ideal representations of lexicographic orderings and base-2 expansions of integer variables. (English) Zbl 1266.90131

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

MSC:

90C10 Integer programming
Full Text: DOI