The Resolution of Duality Gaps in Discrete Optimization.
MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER
Pagination or Media Count:
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
- Operations Research