Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$
| Autor: | Banković, Milan |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science Mathematical optimization Correctness General Computer Science Computer Science - Artificial Intelligence Computer science 020207 software engineering 02 engineering and technology 16. Peace & justice Logic in Computer Science (cs.LO) Theoretical Computer Science Domain (software engineering) Constraint (information theory) Artificial Intelligence (cs.AI) 0202 electrical engineering electronic engineering information engineering Local consistency F.4.1 020201 artificial intelligence & image processing 68T27 68T15 Constraint satisfaction problem |
| Zdroj: | Logical Methods in Computer Science. 12 |
| ISSN: | 1860-5974 |
| DOI: | 10.2168/lmcs-12(3:5)2016 |
| Popis: | In this paper, we investigate the possibility of improvement of the widely-used filtering algorithm for the linear constraints in constraint satisfaction problems in the presence of the alldifferent constraints. In many cases, the fact that the variables in a linear constraint are also constrained by some alldifferent constraints may help us to calculate stronger bounds of the variables, leading to a stronger constraint propagation. We propose an improved filtering algorithm that targets such cases. We provide a detailed description of the proposed algorithm and prove its correctness. We evaluate the approach on five different problems that involve combinations of the linear and the alldifferent constraints. We also compare our algorithm to other relevant approaches. The experimental results show a great potential of the proposed improvement. 28 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|