zbMATH — the first resource for mathematics

Minimal and redundant SAT encodings for the all-interval-series problem. (English) Zbl 1028.68627
Escrig, M. Teresa (ed.) et al., Topics in artificial intelligence. 5th Catalonian conference on AI, CCIA 2002, Castellón, Spain, October 24-25, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2504, 139-144 (2002).
Summary: The SAT encodings defined so far for the all-interval-series (ais) problem are very hard for local search but rather easy for systematic algorithms. We define different SAT encodings for the ais problem and provide experimental evidence that this problem can be efficiently solved with local search methods if one chooses a suitable SAT encoding.
For the entire collection see [Zbl 1001.00045].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: Link