A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems

Paul Swoboda, Jan Kuske, Bogdan Savchynskyy; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 1596-1606

Abstract


We propose a general dual ascent (message passing) framework for Lagrangean (dual) decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficiency of our method on the graph matching and the multicut problems, where it outperforms state-of-the-art solvers including those based on the subgradient optimization and off-the-shelf linear programming solvers.

Related Material


[pdf] [supp] [arXiv]
[bibtex]
@InProceedings{Swoboda_2017_CVPR,
author = {Swoboda, Paul and Kuske, Jan and Savchynskyy, Bogdan},
title = {A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {July},
year = {2017}
}