OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On Broken Triangles

Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril and Zanuttini, Bruno On Broken Triangles. (2014) In: International Conference on Principles and Practice of Constraint Programming - CP 2014, 8 September 2014 - 12 September 2014 (Lyon, France).

[img] (Document in English)

PDF (Author's version) - Depositor and staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
359kB

Abstract

A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in arbitrary instances of binary CSP, thus providing a novel polynomial-time reduction operation. Extensive experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity and we investigate the theoretical relationship with resolution in SAT. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. The definitive version is available at http://www.springer.com/gp/book/9783319104270
Audience (conference):National conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Ecole Nationale Supérieure d'Ingénieurs de Caen - ENSICAEN (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Caen Basse-Normandie (FRANCE)
Laboratory name:
Funders:
ANR-10-BLAN-0210
Statistics:download
Deposited By: IRIT IRIT
Deposited On:30 Mar 2015 12:53

Repository Staff Only: item control page