Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Variable elimination in binary CSPs

Martin C. Cooper 1 Achref El Mouelhi Cyril Terrioux 2
1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
IRIT - Institut de recherche en informatique de Toulouse
2 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We study variable-elimination rules based on the language of forbidden patterns enriched with counting and quantification over variables and values. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each define a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Cyril Terrioux <>
Submitted on : Tuesday, May 28, 2019 - 6:48:08 PM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM

Links full text


  • HAL Id : hal-02142769, version 1
  • ARXIV : 1905.04209


Martin C. Cooper, Achref El Mouelhi, Cyril Terrioux. Variable elimination in binary CSPs. 2019. ⟨hal-02142769⟩



Record views