Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
For practitioners solving discrete optimization problems, this provides a more effective tightening method for MAP-MRF inference.
The paper addresses MAP-MRF inference by tightening LP relaxations. The proposed technique, based on Singleton Arc Consistency, outperforms the previous frustrated-cycle approach in experiments.
We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling this NP-hard problem in practice is to solve its natural LP relaxation and then iteratively tighten the relaxation by adding clusters. Based on some theoretical observations, we propose a new technique for identifying such clusters. It works by running the Singleton Arc Consistency algorithm in a certain CSP instance. Experimental results indicate that the new tightening technique outperforms the previous approach by [Sontag et al. UAI 2012] that searches for frustrated cycles. Our code will be made available at https://github.com/vnk-ist/MAP-MRF/.