Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions
We consider the problem of solving LP relaxations of MAP-MRF inference problems, and in particular the method proposed recently in (Swoboda, Kolmogorov 2019; Kolmogorov, Pock 2021). As a key computational subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex function over a combinatorial polytope. We propose an efficient implementation of this subproutine based on in-face Frank-Wolfe directions, introduced in (Freund et al. 2017) in a different context. More generally, we define an abstract data structure for a combinatorial subproblem that enables in-face FW directions, and describe its specialization for tree-structured MAP-MRF inference subproblems. Experimental results indicate that the resulting method is the current state-of-art LP solver for some classes of problems. Our code is available at https://pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we…
Graph Neural NetworkConvex mixed-integer optimization with Frank-Wolfe methods
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound a…
Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity
We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underl…
RetrievalExploring the Power of Graph Neural Networks in Solving Linear Optimization Problems
Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization probl…
Combinatorial OptimizationConvex Relaxations for Pose Graph Optimization with Outliers
Pose Graph Optimization involves the estimation of a set of poses from pairwise measurements and provides a formalization for many problems arising in mobile robotics and geometric computer vision. In this paper, we cons…