Domain Reduction for Valued Constraints by Generalising Methods from CSP. / Cohen, David; Cooper, Martin; Jguirim1, Wafa.

2018. 64-80 Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France.

Research output: Contribution to conferencePaper

E-pub ahead of print

Standard

Domain Reduction for Valued Constraints by Generalising Methods from CSP. / Cohen, David; Cooper, Martin; Jguirim1, Wafa.

2018. 64-80 Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France.

Research output: Contribution to conferencePaper

Harvard

Cohen, D, Cooper, M & Jguirim1, W 2018, 'Domain Reduction for Valued Constraints by Generalising Methods from CSP', Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France, 27/08/18 - 31/08/18 pp. 64-80. https://doi.org/10.1007/978-3-319-98334-9_5

APA

Cohen, D., Cooper, M., & Jguirim1, W. (2018). Domain Reduction for Valued Constraints by Generalising Methods from CSP. 64-80. Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France. https://doi.org/10.1007/978-3-319-98334-9_5

Vancouver

Cohen D, Cooper M, Jguirim1 W. Domain Reduction for Valued Constraints by Generalising Methods from CSP. 2018. Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France. https://doi.org/10.1007/978-3-319-98334-9_5

Author

Cohen, David ; Cooper, Martin ; Jguirim1, Wafa. / Domain Reduction for Valued Constraints by Generalising Methods from CSP. Paper presented at CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France.17 p.

BibTeX

@conference{4e046b35f2e04a7e9929777a49130506,
title = "Domain Reduction for Valued Constraints by Generalising Methods from CSP",
abstract = "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.",
author = "David Cohen and Martin Cooper and Wafa Jguirim1",
year = "2018",
month = aug,
day = "23",
doi = "10.1007/978-3-319-98334-9_5",
language = "English",
pages = "64--80",
note = "CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming, CP 2018 ; Conference date: 27-08-2018 Through 31-08-2018",
url = "http://cp2018.a4cp.org/",

}

RIS

TY - CONF

T1 - Domain Reduction for Valued Constraints by Generalising Methods from CSP

AU - Cohen, David

AU - Cooper, Martin

AU - Jguirim1, Wafa

PY - 2018/8/23

Y1 - 2018/8/23

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-98334-9_5

DO - 10.1007/978-3-319-98334-9_5

M3 - Paper

SP - 64

EP - 80

T2 - CP 2018: the 24th International Conference on Principles and Practice of Constraint Programming

Y2 - 27 August 2018 through 31 August 2018

ER -