Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$
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 b...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2017-04-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2016/pdf |
| _version_ | 1827322866571411456 |
|---|---|
| author | Milan Banković |
| author_facet | Milan Banković |
| author_sort | Milan Banković |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:35:42Z |
| format | Article |
| id | doaj.art-8a9ac60778bd461193329ce2836d1b1b |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:42Z |
| publishDate | 2017-04-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-8a9ac60778bd461193329ce2836d1b1b2024-03-08T09:44:45ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742017-04-01Volume 12, Issue 310.2168/LMCS-12(3:5)20162016Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$Milan Bankovićhttps://orcid.org/0000-0002-0517-6334In 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.https://lmcs.episciences.org/2016/pdfcomputer science - logic in computer sciencecomputer science - artificial intelligence68t27, 68t15f.4.1 |
| spellingShingle | Milan Banković Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ Logical Methods in Computer Science computer science - logic in computer science computer science - artificial intelligence 68t27, 68t15 f.4.1 |
| title | Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ |
| title_full | Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ |
| title_fullStr | Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ |
| title_full_unstemmed | Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ |
| title_short | Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$ |
| title_sort | solving finite domain linear constraints in presence of the texttt alldifferent |
| topic | computer science - logic in computer science computer science - artificial intelligence 68t27, 68t15 f.4.1 |
| url | https://lmcs.episciences.org/2016/pdf |
| work_keys_str_mv | AT milanbankovic solvingfinitedomainlinearconstraintsinpresenceofthetextttalldifferent |