A distributed global optimization method for packing problems

Abstract

Packing optimization problems aim to seek the best way of placing a given set of rectangular cartons within a minimum volume rectangular container. Currently, packing optimization methods either have difficulty in finding a globally optimal solution or are computationally inefficient, because models involve too many 0–1 variables and because use of just a single computer. This study proposes a distributed computation method for solving a packing problem by a set of personal computers via the Internet. First, the traditional packing optimization model is converted into an equivalent model containing many fewer 0–1 variables. Then the model is decomposed into several sub-problems by dividing the objective value into many intervals. Each of these sub-problems is a linearized logarithmic program expressed as a linear mixed 0–1 problem. The whole problem is solvable and reaches a globally optimal solution. The numerical examples demonstrate that the proposed method can obtain the global optimum of a packing problem effectively.

Keywords:

• cutting stock problem
• distributed computation
• layout
• optimization