LPMP is a C++ framework for developing scalable dual (Lagrangean) decomposition based solvers for a wide range of LP-relaxations to discrete optimization problems. For a theoretical introduction to the techniques used and the class of problems that can be optimized see [1,2].
We provide a range of solvers for various discrete optimization problems, including
Benchmark problems for various solvers above can be found in Multi-graph matching.
Optimization techniques include
- Messsage passing ,
- Subgradient ascent with a proximal bundle method based on the Frank-Wolfe algorithm , Vladimir Kolmogorov's original implementation.
- An interface to external solvers is provided by DD_ILP.
git clone https://github.com/LPMP/LPMP.git for downloading, then
cd LPMP and
git submodule update --init --remote --recursive for downloading dependencies and finally
cmake . for building.
- Clang 5.0 or GCC 8.0 upwards for C++17 compatibility.
A tutorial on writing a new solver from scratch can be found here.
P. Swoboda, J. Kuske and B. Savchynskyy. A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems. In CVPR 2017.
P. Swoboda and V. Kolmogorov. MAP inference via Block-Coordinate Frank-Wolfe Algorithm. In CVPR 2019
P. Swoboda and B. Andres. A Message Passing Algorithm for the Minimum Cost Multicut Problem. In CVPR 2017.
P. Swoboda, C. Rother, H. A. Alhaija, D. Kainmuller, B. Savchynskyy. A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching. In CVPR 2017.
P. Swoboda, D. Kainmueller, A. Mokarian, C. Theobalt and F. Bernard. A convex approach to multi-graph matching. In CVPR 2019.