ML Anthology

Variable Elimination in Binary CSPs (Extended Abstract)

Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux
IJCAI 2020 pp. 5035-5039
doi:10.24963/IJCAI.2020/702 /ijcai/2020/cooper2020ijcai-variable/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Cooper et al. "Variable Elimination in Binary CSPs (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/702

Markdown

[Cooper et al. "Variable Elimination in Binary CSPs (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/cooper2020ijcai-variable/) doi:10.24963/IJCAI.2020/702

BibTeX

@inproceedings{cooper2020ijcai-variable,
  title     = {{Variable Elimination in Binary CSPs (Extended Abstract)}},
  author    = {Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {5035-5039},
  doi       = {10.24963/IJCAI.2020/702},
  url       = {https://mlanthology.org/ijcai/2020/cooper2020ijcai-variable/}
}