1. Nondeterministic Control for Hybrid Search.
- Author
-
Barták, Roman, Milano, Michela, Hentenryck, Pascal, and Michel, Laurent
- Abstract
Hybrid algorithms combining local and systematic search often use nondeterminism in fundamentally different ways. They may differ in the strategy to explore the search tree and/or in how computation states are represented. This paper presents nondeterministic control structures to express a variety of hybrid search algorithms concisely and elegantly. These nondeterministic abstractions describe the search tree and are compiled in terms of first-class continuations. They are also parameterized by search controllers that are under user control and specify the state representation and the exploration strategy. The resulting search language is thus high-level, flexible, and directly extensible. The abstractions are illustrated on a jobshop scheduling algorithm that combines tabu search and a limited form of backtracking. Preliminary experimental results indicate that the control structures induce small, often negligible, overheads. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF