Decomposition Algorithm for Optimization Placement Problems

• Published in: Математичне та комп'ютерне моделювання. Серія: Технічні науки
• Date: 2019
• Main Authors: Pankratov, A., Romanova, T.
• Format: Article
• Language: Ukrainian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/168582
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ.

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-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів.