A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems

Citations Over TimeTop 12% of 2017 papers

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 Papers

• → A merit function approach to the subgradient method with averaging(2007)14 cited
• → The optimization of nonlinear programming problem by subgradient-based Lagrangian relaxation(2013)2 cited
• Incremental Subgradient Method to Scheduling Algorithm Based on Lagrangian Relaxation(2007)
• Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem(2004)
• → A modified subgradient extragradient method for solving the variational inequality problem(2018)