Lagrangian Relaxation in the literature In the literature, in applications of the Lagrangian relaxation technique (such as (Rush and Collins, 2011;Chang and Collins, 2011;Reichart and Barzilay, 2012) and others), the relaxed problems are solved using specialized algorithms.
in both the relaxations considered in this paper, even the relaxed problems cannot be solved without an ILP solver, and yet we can see improvements from decomposition in Table 1.