Powerful consistency techniques, such as AC~* and FDAC~*, have been developed for Weighted Constraint Satisfaction Problems (WCSPs) to reduce the space in solution search, but are restricted to only unary and binary constraints. On the other hand, van Hoeve el al. developed efficient graph-based algorithms for handling soft constraints as classical constraint optimization problems. We prove that naively incorporating van Hoeve's method into the WCSP framework can enforce a strong form of Φ-Inverse Consistency, which can prune infeasible values and deduce good lower bound estimates. We further show how Van Hoeve's method can be modified so as to handle cost projection and extension to maintain the stronger AC~* and FDAC~* generalized for non-binary constraints. Using the soft allDif ferent constraint as a testbed, preliminary results demonstrate that our proposal gives improvements up to an order of magnitude both in terms of time and pruning.
展开▼
机译：已经开发了强大的一致性技术，例如AC〜*和FDAC〜*，用于加权约束满意度问题（WCSP），以减少解决方案搜索中的空间，但仅限于只有一元和二进制约束。另一方面，van Hoeve El Al。开发了高效的基于图形的算法，用于处理软限制作为经典约束优化问题。我们证明，天鹅地将van Hoeve的方法进入WCSP框架可以强制强制形式的φ-逆一致性，这可以修剪不可行的值，并推测良好的下限估计。我们进一步展示了van Hoeve的方法如何修改，以处理成本投影和扩展，以维持更强的AC〜*和FDAC〜*广义非二进制约束。使用软的Alldif意义的约束作为测试平台，初步结果表明我们的提案在时间和修剪方面使高达数量级的改善。
展开▼
