The discrete optimization technique called local search yields impressive results on many important combinatorial optimization problems. Its tendency to return solutions that are sub-optimal, however, remains a serious limitation of the approach. In this dissertation we propose and investigate a general technique that seeks to overcome this difficulty while maintaining the speed that makes local search an attractive approach. We focus on constrained problems which have an induced non-uniform neighborhood structure, and we examine three such problems experimentally. Our example set is: (1) a variant of Stock Cutting; (2) a precedence constrained routing problem; and (3) a weighted version of the latter. Using our techniques we have been able to improve significantly the quality of solutions found in each of these domains over that found by the traditional local search algorithm, with only modest increases in running time. Our technique is independent of problem domain and, therefore, is applicable to a wide variety of problems.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-8075 |
| Date | 01 January 1991 |
| Creators | Healy, Patrick |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0993 seconds