The Generalized Lattice Point Problem

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1970
Accession Number
AD0726175

Entities

People

  • Darwin Dee Klingman
  • Fred W. Glover

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Boundaries
  • Coefficients
  • Computer Programming
  • Convex Programming
  • Convex Sets
  • Equations
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Optimization
  • Perturbations
  • Simplex Method
  • Theorems
  • United States
  • United States Government

Readers

  • Educational Psychology
  • Operations Research