论文标题
加权CSP的超级重新置换：属性和优化透视图
Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective
论文作者
论文摘要
加权CSP（WCSP）（也称为WCSP的等效性变换）的重新构度的概念是众所周知的，并且发现其在许多算法中的使用以近似或结合最佳WCSP值。相比之下，已经提出了超级反映化的概念（这是保留或增加WCSP目标的权重的变化），但从未详细研究过。为了填补这一空白，我们介绍了超级反映的许多理论特性，并将其与重新构度的理论特性进行了比较。此外，我们提出了一个框架，用于使用超级反映化的WCSP（最大化版本的最大化版本）计算上限。我们表明，原则上可以采用任意（在某些技术条件）约束传播规则来改善界限。特别是对于ARC的一致性，该方法还原为已知的虚拟AC（VAC）算法。我们实施了单粒弧一致性（SAC）的方法，并将其与公共基准中WCSP中其他强大的局部一致性进行了比较。结果表明，从SAC获得的界限对于许多实例组都是优越的。
The notion of reparametrizations of Weighted CSPs (WCSPs) (also known as equivalence-preserving transformations of WCSPs) is well-known and finds its use in many algorithms to approximate or bound the optimal WCSP value. In contrast, the concept of super-reparametrizations (which are changes of the weights that keep or increase the WCSP objective for every assignment) was already proposed but never studied in detail. To fill this gap, we present a number of theoretical properties of super-reparametrizations and compare them to those of reparametrizations. Furthermore, we propose a framework for computing upper bounds on the optimal value of the (maximization version of) WCSP using super-reparametrizations. We show that it is in principle possible to employ arbitrary (under some technical conditions) constraint propagation rules to improve the bound. For arc consistency in particular, the method reduces to the known Virtual AC (VAC) algorithm. We implemented the method for singleton arc consistency (SAC) and compared it to other strong local consistencies in WCSPs on a public benchmark. The results show that the bounds obtained from SAC are superior for many instance groups.
