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. Newly, 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.

本文研究重新参数化和超级重新参数化与加权约束优化问题的关系，提出一种使用超级重新参数化和约束传播计算加权约束满足问题上界的方法，并在公共基准上比较了不同算法的实验结果。

加权 CSP 问题的超重参数化：特点和优化视角

Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

We describe Dr.Fill, a program that solves American-style crossword puzzles.
From a technical perspective, Dr.Fill works by converting crosswords to
weighted CSPs, and then using a variety of novel techniques to find a solution.
These techniques include generally applicable heuristics for variable and value
selection, a variant of limited discrepancy search, and postprocessing and
partitioning ideas. Branch and bound is not used, as it was incompatible with
postprocessing and was determined experimentally to be of little practical
value. Dr.Fillls performance on crosswords from the American Crossword Puzzle
Tournament suggests that it ranks among the top fifty or so crossword solvers
in the world.

Dr.Fill 是一个解决美式纵横填字游戏的程序，它将这些游戏转换为加权 CSPs，然后使用各种创新技术来找到解决方案，该程序在美国纵横填字游戏大赛上的表现表明，它在世界范围内排名前五十的纵横字谜解决者之间。