Accession Number : AD0775462

Title :   The Resolution of Duality Gaps in Discrete Optimization.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Bell,David E.

Report Date : AUG 1973

Pagination or Media Count : 128

Abstract : Methods by which the unconstrained group problem may be applied to generalized programming problems in which the activities are not known explicitly, are presented together with a worked example of the cutting stock problem. A special analysis is made of a generalized programming approach to the Traveling Salesman problem in which a different type of cut is presented. Two algorithms are given which resolve any duality gap for the general integer programming resulting from the unconstrained group problem. Both rely on an existing primal-dual ascent method of Fisher and Shapiro. Finally some theoretical considerations of the integer lattice are examined, particularly in connection with the intersection of corner polyhedra. (Author)

Descriptors :   *Mathematical programming, *Optimization, Convex sets, Network flows, Algorithms

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE