The Generalized Lattice-Point Problem

The generalized lattice-point problem, posed by Charnes and studied by M. J. L. Kirby, H. Love, and others, is a linear program whose solutions are constrained to be extreme points of a specified polytope. We show how to exploit this and more general problems by convexity (or intersection) cut strategies without resorting to standard problem-augmenting techniques such as introducing 0-1 variables. In addition, we show how to circumvent “degeneracy” difficulties inherent in this problem without relying on perturbation (which provides uselessly shallow cuts) by identifying nondegenerate subregions relative to which cuts may be defined effectively. Finally, we give results that make it possible to obtain strengthening cuts for problems with special structures.