lpmp / bdd Goto Github PK

An integer linear program solver using a Lagrange decomposition into binary decision diagrams. Lagrange multipliers are updated through dual block coordinate ascent.

License: GNU General Public License v3.0

CMake 1.23% C++ 65.69% Python 13.91% C 0.01% Cuda 18.99% Shell 0.17%

gpu ilp-solver optimization

bdd's Introduction

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

Discrete graphical models,
Multicut, [3]
Max-cut,
Graph matching, [4]
Multi-graph matching, [5]
Discrete graphical models with bottleneck terms, [6]
Lifted disjoint paths.

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

Optimization techniques

Optimization techniques include

Messsage passing [1],
Subgradient ascent with a proximal bundle method based on the Frank-Wolfe algorithm [2], Vladimir Kolmogorov's original implementation.
An interface to external solvers is provided by DD_ILP.

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/LPMP/LPMP.git

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

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

In order to install only the all variants of multicut solvers (multicut, asymmetric multiway cut [9], multiway cut [9]), type

PACKAGES="mc" python3 -m pip install git+https://github.com/LPMP/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/lpmp/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:

Clang 5.0 or GCC 8.0 upwards for C++17 compatibility (see here for installation instructions).
HDF5 (install with apt install libhdf5-serial-dev)
cmake (install with apt install cmake)

Documentation

A tutorial on writing a new solver from scratch can be found here. The documentation for using all the existing solvers is in the directory doc.

References

bdd's People

Contributors

Stargazers

Watchers

Forkers

aabbas90 daghty kepengxu asb24repo amuwa wenyuzhi gwangho-lee xiaogaogaoxiaoseu

bdd's Issues

Issue building

Hi! I am very interested in using your solver!

I am running into the following error:
fatal error: cub/detail/device_synchronize.cuh: No such file or directory 36 | #include <cub/detail/device_synchronize.cuh>

I am using CUDA 11.4

It looks like I don't have any cub/detail/ directory:

ls -l /usr/local/cuda-11.4/include/cub/
total 212
drwxr-xr-x 2 root root  4096 Jul  1 20:12 agent
drwxr-xr-x 3 root root  4096 Jul  1 20:12 block
drwxr-xr-x 2 root root  4096 Jul  1 20:12 cmake
-rw-r--r-- 1 root root  2000 Jul  1 20:12 config.cuh
-rw-r--r-- 1 root root  3750 Jul  1 20:12 cub.cuh
drwxr-xr-x 3 root root  4096 Jul  1 20:12 device
drwxr-xr-x 2 root root  4096 Jul  1 20:12 grid
drwxr-xr-x 2 root root  4096 Jul  1 20:12 host
drwxr-xr-x 2 root root  4096 Jul  1 20:12 iterator
drwxr-xr-x 2 root root  4096 Jul  1 20:12 thread
-rw-r--r-- 1 root root 29129 Jul  1 20:12 util_allocator.cuh
-rw-r--r-- 1 root root  6955 Jul  1 20:12 util_arch.cuh
-rw-r--r-- 1 root root  3652 Jul  1 20:12 util_compiler.cuh
-rw-r--r-- 1 root root  6333 Jul  1 20:12 util_cpp_dialect.cuh
-rw-r--r-- 1 root root  5763 Jul  1 20:12 util_debug.cuh
-rw-r--r-- 1 root root  2176 Jul  1 20:12 util_deprecated.cuh
-rw-r--r-- 1 root root 23022 Jul  1 20:12 util_device.cuh
-rw-r--r-- 1 root root  3710 Jul  1 20:12 util_macro.cuh
-rw-r--r-- 1 root root  2872 Jul  1 20:12 util_math.cuh
-rw-r--r-- 1 root root  2368 Jul  1 20:12 util_namespace.cuh
-rw-r--r-- 1 root root 22197 Jul  1 20:12 util_ptx.cuh
-rw-r--r-- 1 root root 40332 Jul  1 20:12 util_type.cuh
-rw-r--r-- 1 root root  3114 Jul  1 20:12 version.cuh
drwxr-xr-x 3 root root  4096 Jul  1 20:12 warp

Do you have any advice on how to proceed? I am unable to install different CUDA versions on this machine. Thanks!

git clone https://github.com/LPMP/BDD
cd BDD
git submodule update --remote --recursive --init
python setup.py install # where python command refers to python 3 installation

and encountered several issues. As a reference (and maybe for future fixes) i post them here so not everyone has to go on the journey to solve them :)

My compiler(s) are complaining about multiple things:

size_t not found. Fix: add #include <stddef.h> to this line of two_dimensional_variable_array.hxx
"narrowing conversion" in incremental_mm_agreement_rounding_cuda.cu. (Definitely just a temporary) fix: replace the linked line with thrust::transform(first, last, delta_it_begin, mm_types_transform<typename SOLVER::value_type>{(float)cur_delta, (float)max_incon_mm_diff, 2.0, false}); (basically casting cur_delta and max_incon_mm_diff ALWAYS to float which might cause precision loss when using double-solvers)
file <cub/detail/detect_cuda_runtime.cuh not found. fix: 1) navigate with console to <bdd_root>/external/thrust/dependencies/cub/ and git checkout main && git pull (in fact, before building the bdd project i did perform git submodule update --init --recursive --remote which should actually solve it but it didnt...)
file <cuda_runtime.h> not found. Fix: i added after this line include_directories("${CMAKE_CUDA_TOOLKIT_INCLUDE_DIRECTORIES}")