Nondeterministic Control for Hybrid Search |
| |
Authors: | Pascal Van Hentenryck Laurent Michel |
| |
Affiliation: | (1) Brown University, Box 1910, Providence, RI 02912, USA;(2) University of Connecticut, Storrs, CT 06269-2155, USA |
| |
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. |
| |
Keywords: | constraint language local search hybrid search non determinism continuation closure solution checkpoint search procedure |
本文献已被 SpringerLink 等数据库收录! |
|