The Generalized Lattice Point Problem
- 1 August 1970
- report
- Published by Defense Technical Information Center (DTIC)
Abstract
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. The authors 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, the authors 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 effectively defined. Finally, results are given that make it possible to obtain strengthened cuts for problems with special structures.Keywords
This publication has 0 references indexed in Scilit: