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