We present a new proximal bundle method for Maximum-
A-Posteriori (MAP) inference in structured energy minimiza-
tion problems. The method optimizes a Lagrangean relax-
ation of the original energy minimization problem using a
multi plane block-coordinate Frank-Wolfe method that takes
advantage of the specific structure of the Lagrangean decom-
position. We show empirically that our method outperforms
state-of-the-art Lagrangean decomposition based algorithms
on some challenging Markov Random Field, multi-label dis-
crete tomography and graph matching problems.