Accession Number:

AD0726175

Title:

The Generalized Lattice Point Problem

Descriptive Note:

Research rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s):

Report Date:

1970-08-01

Pagination or Media Count:

39.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE