Exact methods based on Lagrangian relaxations and surrogate for the problem of loading pallets of the producer

In this paper we present exact methods, based on Lagrangean and surrogate relaxations, with good performance to solve the manufacturer's pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) or (l,w) into a larger rectangle (L,W) without overlapping. The proposed methods involve a branch and bound based tree search procedure for which the bounds, in each node of the tree, are derived from Lagrangean and/or surrogate relaxations of a 0–1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and surrogate heuristics are also applied to obtain good feasible solutions in the subgradient optimization. Computational experiments were performed with instances of the literature and actual instances of a carrier. The results show that one of the proposed methods is competitive with methods found in the literature, including the software GAMS/CPLEX.