SCSC2003 Abstract S11599
Empirical Analysis of Legacy Heuristics using Simulation-Based Methods
Empirical Analysis of Legacy Heuristics using Simulation-Based Methods
Submitting Author: Dr. Raymond Hill
Abstract:
Discrete optimization problems are sometimes difficult to solve using exact algorithmic approaches. Lack of continuity means branch-and-bound-type of methods are generally employed to find exact solutions. The primary problem with these methods are the excessively long run times possible on even fairly small problems. Heuristic solution methods are thus employed to obtain reasonable solutions in a fraction of the computing time. Prior to the popularity of modern heuristic approaches, such as genetic algorithms, tabu search, and ant colony algorithms, greedy algorithm approaches constituted the preferred heuristic approach. In this paper we re-address the viability of examining these legacy greedy approaches building upon a research hypothesis that these approaches offer insights into solution procedure performance as yet uncovered, insights that hold promise for improving the neighborhood structure exploited in the modern heuristic approaches. Employing a simulation-based em
pirical analysis methodology, this paper examines the performance of two sets of greedy heuristics: greedy construction heuristics and problem re-structuring approaches. This paper discusses the simulation-based methodology for developing a reasonable test problem set, summarizes the members of the heuristic sets examined, the results of the empirical testing, and insights gained from that testing. Potential implications for modern heuristic approaches are also offered.
Back to SCSC2003 Abstracts