Accession Number:

AD0763385

Title:

Improved Convexity Cuts for Lattice Point Problems

Descriptive Note:

Research rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s):

Report Date:

1973-04-01

Pagination or Media Count:

16.0

Abstract:

The generalized lattice point GLP problem provides a formulation that accommodates a variety of discrete alternative problems. In the paper the authors show how to substantially strengthen the convexity cuts for the GLP problem. The new cuts are based on the identification of synthesized lattice point conditions to replace those that ordinarily define the cut. The synthesized conditions give an alternative set of hyperplanes that enlarge the convex set, thus allowing the cut to be shifted deeper into the solution space. A convenient feature of the strengthened cuts is the existence of linking relationships by which they may be constructively generated from the original cuts. Geometric examples are given in the last section to show how the new cuts improve upon those previously proposed for the GLP problem.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE