一句话：提出一种利用 alldifferent 约束信息来强化有限域线性约束过滤与变量界的改进算法。
约束满足问题中，线性约束的过滤算法通常未利用变量同时受 alldifferent 约束这一信息，因而边界传播可能偏弱。本文研究如何在这种情况下改进广泛使用的线性约束过滤算法：当线性约束中的变量还被 alldifferent 约束限制时，利用该结构计算更紧的变量边界，从而获得更强的约束传播。作者给出改进算法的详细描述并证明其正确性。实验在五类同时包含线性约束与 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 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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{Bankovic16,
title = {Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$},
author = {Milan Banković},
journal = {Logical Methods in Computer Science},
volume = {Volume 12, Issue 3},
year = {2017},
doi = {10.2168/lmcs-12(3:5)2016}
}