Linear programming models for bin packing and cutting stock problems

We review several linear programming (LP) formulations for the one-dimensional cutting stock and bin packing problems, namely, the models of Kantorovich, Gilmore–Gomory, onecut models, as in the Dyckhoff–Stadtler approach, position-indexed models, and a model derived from the vehicle routing literature. We analyse some relations between the corresponding LP relaxations, and their relative strengths, and refer how to derive branching schemes that can be used in the exact solution of these problems, using branch-and-price.