Milan Banković - Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$

lmcs:2016 - Logical Methods in Computer Science, April 27, 2017, Volume 12, Issue 3 - https://doi.org/10.2168/LMCS-12(3:5)2016
Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$Article

Authors: Milan Banković ORCID

    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.


    Volume: Volume 12, Issue 3
    Published on: April 27, 2017
    Accepted on: September 5, 2016
    Submitted on: July 31, 2015
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Artificial Intelligence,68T27, 68T15,F.4.1
    Funding:
      Source : OpenAIRE Graph
    • Automated Reasoning and Data Mining; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 174021

    Consultation statistics

    This page has been seen 1110 times.
    This article's PDF has been downloaded 443 times.