Combining the scalability of local search with the pruning techniques of systematic search

Combining the scalability of local search with the pruning techniques of systematic search

0.00 Avg rating0 Votes
Article ID: iaor20031591
Country: Netherlands
Volume: 115
Issue: 1
Start Page Number: 51
End Page Number: 72
Publication Date: Sep 2002
Journal: Annals of Operations Research
Authors:
Keywords: constraint programming, local search
Abstract:

Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It is complete and can be combined with powerful search pruning techniques such as branch-and-bound, constraint propagation and dynamic variable ordering. However, it often scales poorly to large problems. Local search is incomplete, and has the additional drawback that it cannot exploit pruning techniques, making it uncompetitive on some problems. Nevertheless its scalability makes it superior for many large applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, a very flexible form of backtracking that sacrifices completeness to achieve the scalability of local search. It is combined with forward checking and dynamic variable ordering, and evaluated on three combinatorial problems: on the n-queens problem it out-performs the best local search algorithms; it finds large optimal Golomb rulers much more quickly than a constraint-based backtracker, and better rulers than a genetic algorithm; and on benchmark graphs it finds larger cliques than almost all other tested algorithms. We argue that this form of backtracking is actually local search in a space of consistent partial assignments, offering a generic way of combining standard pruning techniques with local search.

Reviews

Required fields are marked *. Your email address will not be published.