Heuristic analysis, linear programming and branch and bound
(1980) Mathematical Programming Studies — Vol. 13, p. 121-134 (1980)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We consider two questions arising in the analysis of heuristic algorithms. (1)Is there a general procedure involved when analysing a particular problem heuristic? (2)How can heuristic procedures be incorporated into optimising algorithms such as branch and bound? In answer to (1) we present one possible procedure, and discuss the cutting stock and travelling salesman problems from this point of view. Noting that the analysis of a heuristic is often based on a linear programming relaxation, we then show how certain heuristics can be integrated into enumeration schemes to produce branch and bound algorithms whose worst case behaviour steadily improves as the enumeration develops. We take the multidimensional knapsack problem, the uncapacitated K-location problem, and the travelling salesman problem as examples.
- Affiliations
Citations
Wolsey, L. (1980). Heuristic analysis, linear programming and branch and bound. Mathematical Programming Studies, 13, 121-134. https://doi.org/10.1007/BFb0120913 (Original work published 1980)