This work addresses the Constrained Two-dimensional Guillotine Cutting Problem, with and without item rotation, and presents a primal-dual algorithm with the following original components: (1) An improvement of the primal method from [Velasco and Uchoa 2014], based on Reactive GRASP; (2) Algorithm X, based on integer programming, capable of obtaining the best possible upper bounds with the dynamic programming state space relaxation [Christofides and Hadjiconstantinou 1995]; (3) Algorithm X2, a generalization of X that uses two-dimensional weights to obtain even stronger upper bounds; (4) The X2H algorithm, an adaptation of X2 to transform it into a primal heuristic. A method with those elements was extensively tested and could consistently find high quality solutions, certificated to be optimal in many cases. Joint work with André Velasco