ALOP Colloquium with Paul Swoboda

On Monday, June 13, 2022, at 16.00 c.t. Dr. Paul Swoboda, Max-Planck-Institut für Informatik, Saarland Informatics Campus will present his recent work titled

Solving 0-1 ILPs with Binary Decision Diagrams

Abstract:

We present a Lagrange decomposition method for solving 0–1 integer linear programs occurring in structured prediction. We propose a sequential and a massively min-marginal averaging schemes for solving the Lagrangean dual and a perturbation technique for decoding primal solutions. For representing subproblems we use binary decision diagrams (BDDs), which support efficient computation of subproblem solutions and update steps. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment and cell tracking for developmental biology. Our highly parallel GPU implementation improves comes close to or outperform some state-of-the-art specialized heuristics while being problem agnostic. We additionally showcase improvement that can be obtained by integrating machine learning into our solver.

The presentation will take place in HS 9.  Please join us for coffee in E 10 at 15:45.