Improved Convexity Cuts for Lattice Point Problems
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1973
- Accession Number
- AD0763385
Entities
People
- Darwin Dee Klingman
- Fred W. Glover
Organizations
- University of Texas at Austin