A global optimization method for packing problems

Abstract

The objective of packing problems is to determine an optimal way of placing a given set of three-dimensional (3D) rectangular cartons within a minimum volume 3D rectangular container. Current packing optimization methods either use too many extra 0-1 variables or find it difficult to obtain a globally optimal solution. This study proposes an efficient method for finding the global optimum of packing problems. First the traditional packing optimization problem is converted into an equivalent program containing many fewer 0-1 variables than contained in current methods. Then the global optimum of the converted program is found by utilizing piecewise linearization techniques. The numerical examples demonstrate that the proposed method is capable of finding the global optimum of a packing problem.