A mathematical model and a solution method for the problem of placing various-sized circles into a strip

A mathematical model of the problem of placing different-radii circles into a strip is constructed. Several peculiarities of the mathematical model are considered. On the ground of these peculiarities, an original method of transition from one local minimum to another one to provide a decrease of the objective function value is suggested. The method is based on the idea of increasing the problem dimension and a reduced gradient method, as well as on the concept of active inequalities and the Newton method. An algorithm to solve the problem is described in detail. Numerical examples which demonstrate the possibilities of the method are also given. (C) 2003 Elsevier B.V. All rights reserved.