  The paper introduces k-bounded MAP inference, a parameterization of MAP
inference in Markov logic networks. k-Bounded MAP states are MAP states with at
most k active ground atoms of hidden (non-evidence) predicates. We present a
novel delayed column generation algorithm and provide empirical evidence that
the algorithm efficiently computes k-bounded MAP states for meaningful
real-world graph matching problems. The underlying idea is that, instead of
solving one large optimization problem, it is often more efficient to tackle
several small ones.
