In this paper  we propose combining augmented Lagrangian optimization with the dual decomposition method to obtain a fast algorithm for approximate MAP (maximum a posteriori) inference on factor graphs We also show how the proposed algorithm can efficiently handle problems with (possibly global) structural constraints