OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Domain Reduction for Valued Constraints by Generalising Methods from CSP

Cooper, Martin and Jguirim, Wafa and Cohen, David Domain Reduction for Valued Constraints by Generalising Methods from CSP. (2018) In: 24th International Conference on Principles and Practice of Constraint Programming (CP 2018), 27 August 2018 - 31 August 2018 (Lille, France).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1007/978-3-319-98334-9_5


For classical CSPs, the absence of broken triangles on a pair of values allows the merging of these values without changing the satisfiability of the instance, giving experimentally verified reduction in search time. We generalise the notion of broken triangles to VCSPs to obtain a tractable value-merging rule which preserves the cost of a solution. We then strengthen this value merging rule by using soft arc consistency to remove soft broken triangles and we show that the combined rule generalises known notions of domain value substitutability and interchangeability. Unfortunately the combined rules are no longer tractable to apply, but can still have applications as heuristics for reducing the search space. Finally we consider the generalisation of another value-elimination rule for CSPs to binary VCSPs. This new rule properly generalises neighbourhood substitutability and so we expect it will also have practical applications.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in volume 11008 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN: 978-3-319-98333-2 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-319-98334-9_5 within the French Agence Nationale de la Recherche program
HAL Id:hal-02283157
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > Université de la Manouba - UMA (TUNISIA)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Royal Holloway University of London - RHUL (UNITED KINGDOM)
Laboratory name:
ANR : Agence nationale de la recherche (France)
Deposited On:06 Sep 2019 14:56

Repository Staff Only: item control page