Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams

Jan-Hendrik Lange, Paul Swoboda
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:6000-6010, 2021.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams %A Jan-Hendrik Lange %A Paul Swoboda %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-lange21a %I PMLR %P 6000--6010 %U https://proceedings.mlr.press/v139/lange21a.html %V 139 %X 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.
APA
Lange, J. & Swoboda, P.. (2021). Efficient Message Passing for 0–1 ILPs with Binary Decision Diagrams. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:6000-6010 Available from https://proceedings.mlr.press/v139/lange21a.html.

Related Material