Variable Elimination in Binary CSPs (Extended Abstract)
| Autor: | Achref El Mouelhi, Cyril Terrioux, Martin C. Cooper |
|---|---|
| Přispěvatelé: | Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), H & H: Research and Training, COntraintes, ALgorithmes et Applications (COALA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
CSP (Constraint Satisfaction Problem) Computer science Binary number 02 engineering and technology Constraints and SAT Constraint satisfaction Class (biology) Satisfiability [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Problèmes de satisfaction de contraintes CSP 020204 information systems 0202 electrical engineering electronic engineering information engineering Benchmark (computing) Preprocessor 020201 artificial intelligence & image processing Variable elimination Constraint satisfaction problem Constraint Satisfaction |
| Zdroj: | Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20} Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence, Jul 2020, Yokohama, France. pp.5035-5039, ⟨10.24963/ijcai.2020/702⟩ IJCAI Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}, Jul 2020, Yokohama, France. pp.5035-5039, ⟨10.24963/ijcai.2020/702⟩ |
| DOI: | 10.24963/ijcai.2020/702⟩ |
| Popis: | International audience; We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each defines a novel tractable class. Using our variable elimination rules in preprocessing allowed us to solve more benchmark problems than without. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|