Home

Awesome

LPMP

<!--- [![Build Status](https://travis-ci.org/LPMP/LPMP.svg?branch=master)](https://travis-ci.org/LPMP/LPMP) --->

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].

Solvers

We provide a range of solvers for various discrete optimization problems, including

Benchmark problems for various solvers above can be found in datasets.

Optimization techniques

Optimization techniques include

Differentiable wrappers

The solvers can be wrapped as differentiable PyTorch modules using the technique of [7]. Currently, wrappers are available for graph matching, multigraph matching and lifted disjoint paths solvers. For usage examples see an application to keypoint matching [8] (code) or the general repository of [7].

All these can be pip installed with

python3 -m pip install git+https://github.com/lpmp/LPMP.git

In order to install only graph matching and multigraph matching solvers, type

PACKAGES="gm" python3 -m pip install git+https://github.com/AndreaHor/LPMP.git

In order to install only the lifted disjoint paths solver, type

PACKAGES="ldp" python3 -m pip install git+https://github.com/AndreaHor/LPMP.git

In order to get the precise version of graph matching as used in [8], type

python3 -m pip install git+https://github.com/lpmp/LPMP.git@keypiont_submission

NOTE: If you already installed with one of the above options and would like to change the option or if you have an older version installed, you must add --upgrade argument to pip. So, you type for instance

PACKAGES="ldp" python3 -m pip install git+https://github.com/AndreaHor/LPMP.git --upgrade

Installation

Type 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.

Prerequisites:

Documentation

A tutorial on writing a new solver from scratch can be found here.

References