# Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

arXiv: https://arxiv.org/abs/2201.02018 · HTML: https://mlsanity.com/paper/2201.02018/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 78 references that are in the map.
- First posted on arXiv 6 Jan 2022.

## Builds on (most cited first, 6 of 6)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [Discrete graphical models -- an optimization perspective](https://mlsanity.com/paper/2001.09017/) (2020)
- [Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization](https://mlsanity.com/paper/2004.07715/) (2020)

## Abstract (arXiv)

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.