Decomposition Algorithm for Optimization Placement Problems

Abstract

The paper considers a placement problem of 2D convex objects in a rectangular domain of minimum area, that related to the field of Packing and Cutting problems. Our objects may be continuously translated and rotated. A nonlinear programming model of the problem is derived using the phi-function technique. We develop an efficient decomposition algorithm to search for local optimal solutions for the placement problem. The algorithm reduces our problem to a sequence of nonlinear programming subproblems of considerably smaller dimension and a smaller number of nonlinear inequalities. The benefit of this approach is borne out by the computational results.

У статті розглядається задача розміщення двовимірних опуклих об'єктів у прямокутній області мінімальної площі, яка відноситься до класу задач упаковки і розкрою. Об'єкти, що розміщуються, можуть неперервно транслюватися і обертатися. Будується математична модель задачі розміщення у вигляді задачі нелінійного програмування з використанням методу phi-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів.