Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams
Jan-Hendrik Lange, Paul Swoboda
Abstract
We present a message passing method for 0{–}1 integer linear programs. Our algorithm is based on a decomposition of the original problem into subproblems that are represented as binary deci- sion diagrams. The resulting Lagrangean dual is solved iteratively by a series of efficient block coordinate ascent steps. Our method has linear iteration complexity in the size of the decomposi- tion and can be effectively parallelized. The char- acteristics of our approach are desirable towards solving ever larger problems arising in structured prediction. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment, discrete tomography and cell tracking for develop- mental biology and show promising performance.
BibTeX
@InProceedings{pmlr-v139-lange21a,
title = {Efficient Message Passing for 0{–}1 ILPs with Binary Decision Diagrams},
author = {Lange, Jan-Hendrik and Swoboda, Paul},
booktitle = {Proceedings of the 38th International Conference on Machine Learning},
pages = {6000--6010},
year = {2021},
editor = {Meila, Marina and Zhang, Tong},
volume = {139},
series = {Proceedings of Machine Learning Research},
month = {18--24 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v139/lange21a/lange21a.pdf},
url = {https://proceedings.mlr.press/v139/lange21a.html},
abstract = {We present a message passing method for 0{–}1 integer linear programs. Our algorithm is based on a decomposition of the original problem into subproblems that are represented as binary deci- sion diagrams. The resulting Lagrangean dual is solved iteratively by a series of efficient block coordinate ascent steps. Our method has linear iteration complexity in the size of the decomposi- tion and can be effectively parallelized. The char- acteristics of our approach are desirable towards solving ever larger problems arising in structured prediction. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment, discrete tomography and cell tracking for develop- mental biology and show promising performance.}
}