Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams
Authors: Jan-Hendrik Lange, Paul Swoboda
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment, discrete tomography and cell tracking for developmental biology and show promising performance. |
| Researcher Affiliation | Academia | 1University of T ubingen, Germany 2Max Planck Institute for Informatics, Saarbr ucken, Germany. |
| Pseudocode | Yes | Algorithm 1: Min-marginal averaging |
| Open Source Code | Yes | The code and datasets are available on https://github.com/LPMP/BDD. |
| Open Datasets | Yes | Cell tracking Small and large cell tracking problems from the study (Haller et al., 2020). Graph matching (GM) Quadratic assignment problems (often called graph matching in the literature) for correspondence in computer vision (Torresani et al., 2008) (hotel, house) and developmental biology (Kainmueller et al., 2014) (worms). Markov Random Field (MRF) Several datasets from the Open GM (Kappes et al., 2015) benchmark... QAPLIB The widely used benchmark dataset for quadratic assignment problems used in the combinatorial optimization community (Burkard et al., 1997). Discrete tomography The synthetic discrete tomography dataset introduced in (Kuske et al., 2017)... |
| Dataset Splits | No | The paper discusses various datasets and problem instances, but does not specify training, validation, or test dataset splits (e.g., percentages, counts, or explicit standard splits) needed to reproduce data partitioning. |
| Hardware Specification | No | The paper does not provide specific details about the hardware (e.g., GPU/CPU models, memory) used to run the experiments. It only mentions general aspects like parallelization capabilities. |
| Software Dependencies | No | The paper mentions external solvers like Gurobi (Gurobi Optimization, LLC, 2020) and CPLEX (Cplex, IBM ILOG, 2019) that it compares against, but it does not specify software dependencies with version numbers for its own implementation (e.g., Python version, specific libraries). |
| Experiment Setup | Yes | BDD-MP We create one BDD per linear inequality. For celltracking-large and MRF we use variable reordering and parallelization with γ = 0.5. We run Algorithm 1 until a minimal relative objective improvement of 10 6 and afterwards search for a primal solution with the primal heuristic Algorithm 5 from the appendix. We use the non-smooth optimization except for discrete tomography, where we use smoothing parameter α = 0.01 (cf. Section A.5). |