Tomáš Dlask presents Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

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.