论文标题
弧度抗性和线性编程二重性：分析基于成本的过滤
Arc-consistency and linear programming duality: an analysis of reduced cost based filtering
论文作者
论文摘要
在约束编程（CP）中，以成本成本来实现全局约束的弧线矛盾（AC），包括从变量的域中删除所有不属于任何不属于固定界限的解决方案的值。我们分析了如何使用线性双重性和降低成本来找到所有此类不一致的值。特别是，当约束具有理想的线性编程（LP）公式时，我们表明n对溶液始终足以实现AC（其中n是变量的数量）。该分析导致了一种简单的算法，该算法对LP求解器进行了n个调用，与基于每个域的每个值的呼叫呼叫的幼稚方法相反。它扩展了[German等，2017]中为满意度问题和[Claus等，2020]中介绍的工作。我们对以下问题提出了一些答案：是否总是存在双重解决方案，可以证明价值一致/不一致？给定双重解决方案，我们如何知道哪些值被证明是一致/不一致的？我们可以确定双重解决方案家庭的简单条件，以确保弧线一致吗？
In Constraint Programming (CP), achieving arc-consistency (AC) of a global constraint with costs consists in removing from the domains of the variables all the values that do not belong to any solution whose cost is below a fixed bound. We analyse how linear duality and reduced costs can be used to find all such inconsistent values. In particular, when the constraint has an ideal Linear Programming (LP) formulation, we show that n dual solutions are always enough to achieve AC (where n is the number of variables). This analysis leads to a simple algorithm with n calls to an LP solver to achieve AC, as opposed to the naive approach based on one call for each value of each domain. It extends the work presented in [German et al., 2017] for satisfaction problems and in [Claus et al., 2020] for the specific case of the minimum weighted alldifferent constraint. We propose some answers to the following questions: does there always exists a dual solution that can prove a value consistent/inconsistent ? given a dual solution, how do we know which values are proved consistent/inconsistent ? can we identify simple conditions for a family of dual solutions to ensure arc-consistency ?
