Home Books eBooks Journals References & Proceedings Authors, Editors, Reviewers A-Z Product Index Awards
Flexible Automation and Intelligent Manufacturing,  1997:<br>Proceedings of the Seventh International FAIM Conference

ISBN:
978-1-56700-089-4 (Print)
978-1-56700-442-7 (Online)

PLUG AND PLAY FRAMEWORK FOR COMBINATORAL PROBLEM HEURISTICS

Andrew Wooster
Panasonic Technologies Kyushu Matsushita Electric Research Lab Research Triangle Park, NC, USA

Abstract

Combinatorial problems such as the traveling salesperson, assignment and set-covering problems often rear their heads in process optimization. Because these problems are NP-hard, it remains unlikely that they will yield global optima at reasonable computational cost. Therefore, we must rely on heuristic techniques which seek good, albeit sub-optimal, solutions at an acceptable cost. To this end, meta-heuristic search strategies are interesting because they require very little problem specific knowledge. What little they do need to know about a problem can be encapsulated in a neighborhood operator which provides a mechanism for seeking local optima. Unfortunately, these operators can be very difficult to implement and in this paper we define a practical interface for enumerating neighbors. Once a neighborhood operator has been defined, dynamic strategy selection becomes possible. This means that meta-heuristic strategies, such as simulated annealing and tabu search, can be plugged into problem contexts at run-time.