论文标题
使用二进制决策图的0-1 ILP的有效消息传递
Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams
论文作者
论文摘要
我们提出了一个针对0-1整数线性程序的消息传递方法。我们的算法基于将原始问题分解为以二进制决策图表示的子问题。由一系列有效的块坐标步骤迭代求解所得的Lagrangean双重二元。我们的方法具有分解大小的线性迭代复杂性，并且可以有效地平行。我们方法的特征是解决结构化预测中出现的越来越大问题的必需。我们介绍了马尔可夫随机场的MAP推断，二次分配，离散断层扫描和细胞跟踪的实验结果，以进行发育生物学，并显示出令人鼓舞的性能。
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 decision 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 decomposition and can be effectively parallelized. The characteristics 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 developmental biology and show promising performance.
