zbMATH — the first resource for mathematics

An empirical evaluation of portfolios approaches for solving CSPs. (English) Zbl 1382.68219
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 316-324 (2013).
Summary: Recent research in areas such as SAT solving and integer linear programming has shown that the performances of a single arbitrarily efficient solver can be significantly outperformed by a portfolio of possibly slower on-average solvers. We report an empirical evaluation and comparison of portfolio approaches applied to constraint satisfaction problems (CSPs). We compared models developed on top of off-the-shelf machine learning algorithms with respect to approaches used in the SAT field and adapted for CSPs, considering different portfolio sizes and using as evaluation metrics the number of solved problems and the time taken to solve them. Results indicate that the best SAT approaches have top performances also in the CSP field and are slightly more competitive than simple models built on top of classification algorithms.
For the entire collection see [Zbl 1263.68017].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C11 Mixed integer programming
Full Text: DOI