We present a general and efficient optimisation methodology for for max-margin sructured classification tasks. The efficiency of the method relies on the interplay of several techiques: marginalization of the dual of the structured SVM, or max-margin Markov problem; partial decomposition via a gradient formulation; and finally tight coupling of a max-likelihood inference algorithm into the optimization algorithm, as opposed to using inference as a working set maintenance mechanism only.