Open AccessSymmetry breaking in a new stable model search method
Author(s) -
Tarek Khaled,
Belaïd Benhamou
Publication year - 2018
Publication title -
kalpa publications in computing
Language(s) - English
Resource type - Conference proceedings
ISSN - 2515-1762
DOI - 10.29007/1l5r
Subject(s) - symmetry breaking , computer science , symmetry (geometry) , constraint programming , constraint satisfaction problem , homogeneous space , theoretical computer science , answer set programming , representation (politics) , set (abstract data type) , mathematics , logic programming , programming language , artificial intelligence , mathematical optimization , physics , geometry , particle physics , politics , probabilistic logic , stochastic programming , political science , law
In this work, we investigate the inclusion of symmetry breaking in the answer set programming (ASP) framework. The notion of symmetry is widely studied in various domains. Particularly, in the field of constraint programming, where symmetry breaking made a significant improvement in the performances of many constraint solvers. Usually, combinatorial problems contain a lot of symmetries that could render their resolution difficult for the solvers that do not consider them. Indeed, these symmetries guide the solvers in the useless exploration of symmetric and redundant branches of the search tree. The ASP framework is well-known in knowledge representation and reasoning. How- ever, only few works on symmetry in ASP exist. We propose in this paper a new ASP solver based on a novel semantics that we enhance by symmetry breaking. This method with symmetry elimination is implemented and used for the resolution of a large variety of combinatorial problems. The obtained results are very promising and showcase an advantage when using our method in comparison to other known ASP methods.