Application of Surrogate Duality to Discrete Optimization Problems.
Abstract
Size reduction (logical elimination of variables or constraints or elimination of redundant constraints) and constraint aggregation may all be viewed as preprocessing techniques for solving discrete optimization problems. It can be shown analytically that in the absence of constraint aggregation, size reduction leads to a poor linear programming relaxation value. A novel method was proposed to convert an equality knapsack problem into an equivalent inequality knapsack problem. The use of least-lower-bound based candidate problem selection in solving equality knapsacks was established. (author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 15, 1986
- Accession Number
- ADA173078
Entities
People
- Balasubramanian Ram
- Sanjiv Sarin