The Generalized Lattice Point Problem
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
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.
- Operations Research