The Resolution of Duality Gaps in Discrete Optimization.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1973
- Accession Number
- AD0775462
Entities
People
- David E. Bell
Organizations
- Massachusetts Institute of Technology