An integer linear program solver using a Lagrange decomposition into binary decision diagrams. Lagrange multipliers are updated through min-marginal averaging (a form of dual block coordinate ascent). Sequential and parallel CPU solvers are provided as well as a massively parallel GPU implementation.
git clone https://github.com/LPMP/BDD
git submodule update --remote --recursive --init
Then continue with creating a build folder and use cmake:
mkdir build && cd build && cmake ..
If CUDA-solvers are to be built, set WITH_CUDA=ON in cmake and ensure CUDA is available (tested on CUDA 11.2, later versions should also work).
Given an input file ${input} in LP format, one can solve the problem via
bdd_solver_cl -i ${input} -s ${solver}
where ${solver} is one of
mmafor sequential min-marginal averaging.parallel_mmafor parallel CPU deferred min-marginal averaging.mma_cudafor parallel deferred min-marginal averaging on GPU (available if built withWITH_CUDA=ON).hybrid_parallel_mmafor parallel deferred min-marginal averaging on CPU and GPU simultaneously (available if built withWITH_CUDA=ON). This solver might be faster when a few long constraints are present that would constitute a sequential bottleneck for the pure GPU solver.
In order to compute a primal solution from the dual one obtained through a min-marginal averaging scheme, we provide a perturbation based rounding heuristic
--incremental_primal: Perturb costs iteratively to drive variables towards integrality. Parameters for this scheme are--incremental_initial_perturbation ${p}: The initial perturbation magnitude.--incremental_perturbation_growth_rate ${x}: The growth rate for increasing the perturbation after each round.
For terminating dual optimization we provide three stopping criteria:
--max_iter ${max_iter}: For terminating after a pre-specified number of iterations.--improvement_slope ${p}$: For terminating if improvement between iterations is less than ${p} of the improvement after the first iteration.--tolerance ${p}$: For terminating if improvement between iterations is less than ${p} of the initial lower bound.
For computing BDDs for representing constraints and for sequentially visiting variables in the mma solver the variable order can be specified.
-o input: Use the variable ordering as given in the input file.-o bfs: Use a breadth-first search through the variable-constraint adjacency matrix to determine a variable ordering starting from the most eccentric node.-o cuthill: Use the Cuthill McKee algorithm on the variable-constraint adjacency matrix to determina a variable ordering.
If you use this work please cite
and
for the parallel solvers.