Improved Convexity Cuts for Lattice Point Problems
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
The generalized lattice point GLP problem provides a formulation that accommodates a variety of discrete alternative problems. In the paper the authors show how to substantially strengthen the convexity cuts for the GLP problem. The new cuts are based on the identification of synthesized lattice point conditions to replace those that ordinarily define the cut. The synthesized conditions give an alternative set of hyperplanes that enlarge the convex set, thus allowing the cut to be shifted deeper into the solution space. A convenient feature of the strengthened cuts is the existence of linking relationships by which they may be constructively generated from the original cuts. Geometric examples are given in the last section to show how the new cuts improve upon those previously proposed for the GLP problem.
- Operations Research