On Irrelevant Literals in Pseudo-Boolean Constraint Learning
Autor: | Daniel Le Berre, Pierre Marquis, Romain Wallon, Stefan Mengel |
---|---|
Přispěvatelé: | Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université d'Artois (UA), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.) |
Jazyk: | angličtina |
Rok vydání: | 2019 |
Předmět: |
FOS: Computer and information sciences
Current (mathematics) Theoretical computer science Computer Science - Artificial Intelligence Computer science Inference 02 engineering and technology Solver 16. Peace & justice Boolean constraint 020202 computer hardware & architecture [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Constraint (information theory) Artificial Intelligence (cs.AI) Truth value 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing |
Zdroj: | 29th International Joint Conference on Artificial Intelligence (IJCAI'20) 29th International Joint Conference on Artificial Intelligence (IJCAI'20), Jan 2021, Yokohama (en ligne), Japan. pp.1148-1154, ⟨10.24963/ijcai.2020/160⟩ HAL |
DOI: | 10.24963/ijcai.2020/160⟩ |
Popis: | Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cutting planes based inference is not as well understood as clause learning in conflict-driven clause learning solvers. In this paper, we show that PB constraints derived using cutting planes may contain \emph{irrelevant literals}, i.e., literals whose assigned values (whatever they are) never change the truth value of the constraint. Such literals may lead to infer constraints that are weaker than they should be, impacting the size of the proof built by the solver, and thus also affecting its performance. This suggests that current implementations of PB solvers based on cutting planes should be reconsidered to prevent the generation of irrelevant literals. Indeed, detecting and removing irrelevant literals is too expensive in practice to be considered as an option (the associated problem is NP-hard. Comment: published at IJCAI 2020 |
Databáze: | OpenAIRE |
Externí odkaz: |