×

zbMATH — the first resource for mathematics

Yet another local search method for constraint solving. (English) Zbl 1054.68646
Steinhöfel, Kathleen (ed.), Stochastic algorithms: Foundations and applications. International symposium, SAGA 2001, Berlin, Germany, December 13–14, 2001. Proceedings. Berlin: Springer (ISBN 3-540-43025-3). Lect. Notes Comput. Sci. 2264, 73-89 (2001).
Summary: We propose a generic, domain-independent local search method called adaptive search for solving Constraint Satisfaction Problems (CSP). We design a new heuristics that takes advantage of the structure of the problem in terms of constraints and variables and can guide the search more precisely than a global cost function to optimize (such as for instance the number of violated constraints). We also use an adaptive memory in the spirit of Tabu Search in order to prevent stagnation in local minima and loops. This method is generic, can apply to a large class of constraints (e.g. linear and non-linear arithmetic constraints, symbolic constraints, etc) and naturally copes with over-constrained problems. Preliminary results on some classical CSP problems show very encouraging performances.
For the entire collection see [Zbl 0977.00039].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
WSAT(OIP)
PDF BibTeX XML Cite
Full Text: Link