Packing small boxes into a big box

Abstract.

The three-dimensional orthogonal packing problem consists of filling a big rectangular box with as many small rectangular boxes as possible. In a recent paper G. Fasano (Alenia Aerospazio, Turin) has given a mixed-integer programming formulation of this problem. Here we extend Fasano's formulation and subject it to polyhedral analysis. The result is a more general formulation whose linear programming relaxation is a tighter approximation of the convex hull of the mixed-integer solutions to the problem than the original model.