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: | Prestwich Steven |
Keywords: | constraint programming, local search |
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