Decomposition Algorithm for Optimization Placement Problems
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 tech...
Saved in:
| Published in: | Математичне та комп'ютерне моделювання. Серія: Технічні науки |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168582 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-168582 |
|---|---|
| record_format |
dspace |
| spelling |
Pankratov, A. Romanova, T. 2020-05-04T17:14:49Z 2020-05-04T17:14:49Z 2019 Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ. 2308-5916 DOI: 10.32626/2308-5916.2019-19.126-131 https://nasplib.isofts.kiev.ua/handle/123456789/168582 519.859 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-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів. uk Інститут кібернетики ім. В.М. Глушкова НАН України Математичне та комп'ютерне моделювання. Серія: Технічні науки Decomposition Algorithm for Optimization Placement Problems Алгоритм декомпозиції для розв’язання оптимізаційних задач розміщення Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Decomposition Algorithm for Optimization Placement Problems |
| spellingShingle |
Decomposition Algorithm for Optimization Placement Problems Pankratov, A. Romanova, T. |
| title_short |
Decomposition Algorithm for Optimization Placement Problems |
| title_full |
Decomposition Algorithm for Optimization Placement Problems |
| title_fullStr |
Decomposition Algorithm for Optimization Placement Problems |
| title_full_unstemmed |
Decomposition Algorithm for Optimization Placement Problems |
| title_sort |
decomposition algorithm for optimization placement problems |
| author |
Pankratov, A. Romanova, T. |
| author_facet |
Pankratov, A. Romanova, T. |
| publishDate |
2019 |
| language |
Ukrainian |
| container_title |
Математичне та комп'ютерне моделювання. Серія: Технічні науки |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Алгоритм декомпозиції для розв’язання оптимізаційних задач розміщення |
| description |
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-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментів.
|
| issn |
2308-5916 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/168582 |
| citation_txt |
Decomposition Algorithm for Optimization Placement Problems / A. Pankratov, T. Romanova // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 126-131. — Бібліогр.: 6 назв. — англ. |
| work_keys_str_mv |
AT pankratova decompositionalgorithmforoptimizationplacementproblems AT romanovat decompositionalgorithmforoptimizationplacementproblems AT pankratova algoritmdekompozicíídlârozvâzannâoptimízacíinihzadačrozmíŝennâ AT romanovat algoritmdekompozicíídlârozvâzannâoptimízacíinihzadačrozmíŝennâ |
| first_indexed |
2025-11-25T22:57:35Z |
| last_indexed |
2025-11-25T22:57:35Z |
| _version_ |
1850576543846236160 |
| fulltext |
Математичне та комп’ютерне моделювання
126
UDC 519.859
DOI: 10.32626/2308-5916.2019-19.126-131
A. Pankratov, Dr. Sci.,
T. Romanova, Dr. Sci.
Institute for Mechanical Engineering Problems
National Academy of Sciences of Ukraine, Kharkiv
DECOMPOSITION ALGORITHM FOR OPTIMIZATION
PLACEMENT PROBLEMS
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 trans-
lated and rotated. A nonlinear programming model of the problem is
derived using the phi-function technique. We develop an efficient de-
composition 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 di-
mension and a smaller number of nonlinear inequalities. The benefit of
this approach is borne out by the computational results.
Key words: placement problem, mathematical model, nonline-
ar optimization, decomposition algorithm.
Introduction. Optimal placement problem is a part of operational re-
search and computational geometry. It is also known as Packing and Cutting
problem [1, p. 1109–1130, 2, p. 397–415]. It has multiple applications in mod-
ern biology, mineralogy, medicine, materials science, nanotechnology, robot-
ics, coding, pattern recognition systems, control systems, space apparatus con-
trol systems, as well as in the chemical industry, power engineering, mechani-
cal engineering, shipbuilding, aircraft construction, civil engineering, etc. The
problems are NP-hard [3, p. 139–183] and, as a result, solution methodologies
generally employ heuristics. Some researchers develop approaches based on
mathematical modeling and general optimization procedures.
Our approach is based on mathematical modeling of relations be-
tween geometric objects, using the phi-function technique (see e. g. [4,
p. 539–544, 5, p. 283–294]) and thus reducing the Packing and Cutting
problem to a nonlinear programming problem. It contains all globally op-
timal solutions. It is possible, at least in theory, to use a global solver for
the nonlinear programming problem and obtain a solution, which is an
optimal packing. However in practice, the model contains a large number
of variables and a huge number of inequalities. Specifically, the model
involves O(n2) nonlinear inequalities and O(n2) variables due to additional
variables in quasi-phi-functions, where n is the number of convex objects.
© A. Pankratov, T. Romanova, 2019
Серія: Технічні науки. Випуск 19
127
As a result, even finding a locally optimal solution becomes an unrealistic
task for the available state of the art NLP-solvers. In order to search for a
«good» locally optimal object placement within a reasonable computation-
al time we propose here a decomposition algorithm.
Problem formulation. We consider here a placement problem in the
following setting. Let denote a rectangular domain of length l and
width w. Both of these dimensions may be variable, or one may be fixed
and the other variable. Suppose a set of convex objects iE ,
{1,2,..., } ni n I , is given to be placed in Ω without overlaps. The posi-
tion of object iE in the fixed coordinates is specified by the coordinates
( , )i ix y of its center and the rotation angle i . We call ( , , )i i ix y the vec-
tor of placement parameters of iE . Minimum allowable distances between
objects iE and jE , nj i I , as well as, between each object iE , ni I ,
and the frontier (border) of Ω may be given.
Object placement optimization problem. Place the set of objects iE ,
ni I , within a domain
2
{( , ) : 0 , 0 }x y R x l y w of mini-
mum area taking into account distance constraints. If one of the two di-
mensions ( l or w ) is fixed, we need to minimize the other one. If both are
variable, it is natural to minimize the area F l w of the container.
Mathematical model. The vector u R
of all our variables can be
described as follows: 1 2( , , , ,..., , )nu l w u u u , ( , , )i i i iu x y is the vec-
tor of placement parameters for the object iE , ni I , denotes the vec-
tor of additional variables, that includes two auxiliary variables 1 2
( , )ij ij
for each quasi phi-functions of objects iE and jE , R
denotes the -di-
mensional Euclidean space, where 2
2 2n n .
A mathematical model of the object placement optimization problem
may now be stated in the form:
min ( )
u W R
F u
, (1)
'
{ : 0, 0, 1, 2,..., , 1, 2,..., , }ij iW u R i n j n j i
, (2)
where ( )F u l w , '
ij is an adjusted quasi phi-function [5, p. 283–294]
defined for the pair of objects iE and jE , i is an adjusted phi-function [4,
p. 539–544] defined for the object iE and the object
*
(to hold the con-
tainment constraint), taking into account minimum allowable distance .
Математичне та комп’ютерне моделювання
128
Our constrained optimization problem (1), (2) is a continuous nonlin-
ear programming problem. The frontier of W is usually made of nonlinear
surfaces containing valleys, ravines. A matrix of the inequality system
which specifies W is strongly sparse and has a block structure.
Problem (1), (2) is an exact formulation for the object placement op-
timization problem. Our objective function is a quadratic; each quasi-phi-
function inequality in (2) is described by a system of inequalities with dif-
ferentiable functions.
A solution strategy. Our solution strategy consists of three major stages.
First we generate a number of starting points from the feasible set of the prob-
lem (1), (2). Then starting from each point obtained at Stage 1 we search for a
local minimum of the objective function F(u) of problem (1), (2). Lastly, we
choose the best local minimum from those found at Stage 2. This is our best
approximation to the global solution of the problem (1), (2).
An essential part of our local optimization scheme (Stage 2) is the de-
composition algorithm that reduces the dimension of the problem and compu-
tational time. It is due to this reduction that our strategy can process large sets
of non-identical convex objects (100 and more). The reduction scheme used
by our algorithm is described below. The actual search for a local minimum is
performed by IPOPT [6, p. 25–57], which is available at an open access non-
commercial software depository (https://projects.coin-or.org/Ipopt).
Description of the Decomposition Algorithm. Let (0)
u W be one
of the starting points found by the previous method. The main idea of the
algorithm is as follows.
First we circumscribe a circle iC of radius ia around each object iE ,
1,2,...,i n . Then for each circle iC we construct an «individual» rectangu-
lar container i i iC E with equal half-sides of length ia ,
1,2,...,i n , so that iC , iE and i have the same center
0 0
( , )i ix y subject to
the sides of i being parallel to those of , ia is a diameter of iE . We take
the fixed value of of the procedure as
1
/
n
i
i
a n
. Further we fix the po-
sition of each individual container i and let the local optimization algorithm
move the corresponding object iE only within the container i . It is clear
that if two individual containers i and j do not have common interior
points for 0 , i. e. 0i j
, (or dist( i , j ) for 0 , i. e.
0i j
), then we do not need to check the non-overlapping (or distance)
constraint for the corresponding pair of objects iE and jE .
https://projects.coin-or.org/Ipopt
Серія: Технічні науки. Випуск 19
129
The above key idea allows us to extract subsets of our feasible set W of
the problem (1), (2) at each step of our optimization algorithm as follows.
We create an inequality system of additional constraints on the trans-
lation vector iv of each object iE in the form: 1 0i i
C
, ni I , where
1 0 0 0 0
min{ , , , }i i
C
i i i i i i i ix x y y x x y y
, is the phi-
function for the circle iC and object
* 2
1 1\ inti iR .
The inequality 0i i
C
is equivalent to the system of four linear ine-
qualities 0
0i ix x , 0
0i iy y ,
0
0i ix x ,
0
0i iy y .
Then we form a new subregion defined by
11
1 1
'
{ : 0, ( , ) , 0, 0, }i i
C
ij i nW u R i j i I
,
where 1 1
1 {( , ) : 0, 1, 2,..., }i ji j i j n
.
In other words, we delete from the system, which describes feasible
region W , quasi phi-function inequalities for all pairs of objects whose
individual containers do not overlap and we add additional inequalities
1 0i i
C
, which describe the containment of the circles iC in their indi-
vidual containers 1i , 1, 2,..., .i n Eo ipso we reduce the number of addi-
tional variables by 1 . Then our algorithm searches for a point of local
minimum
1
*
wu
of the subproblem
1
1
11
min ( )
w
w
u W R
F u
.
When the point
1
*
w
u is found, it is used to construct a starting point
(1)
u
for the second iteration of our optimization procedure.
At that iteration we again identify all the pairs of objects with non-
overlapping individual containers, form the corresponding subregion 2W
(analogously to 1W ) and let our algorithm search for a local minimum
2
*
2wu W . The resulting local minimum
2
*
wu is used to construct a starting
point (2)
u for the third iteration, etc.
Then we solve the k-th subproblem with starting point ( 1)k
u
on a
subregion kW :
min ( )
kk
w kk
w
u W R
F u
, (3)
Математичне та комп’ютерне моделювання
130
'
{ : 0, ( , ) , 0, 0, },k i ki
C
k ij k i nW u R i j i I
(4)
where {( , ) : 0, 1, 2,..., }ki kj
k i j i j n
.
If the point *
k
w
u of local minimum of the k-th subproblem belongs to
the frontier of an «artificial» subset
( 1) ( 1)
{ : 0, 0,k
k k
k i i i iu R x x y y
( 1)
0,
k
i ix x
( 1)
0,
k
i iy y
1,..., }i n ,
(i. e. *
k
w
u kfr
), we take the point * ( )
k
k
w
u u as a center point for a
new subset 1k
and continue our optimization procedure, otherwise (i. e.
*
int
k
k
w
u ) we stop our iterative procedure.
We note that dist( *
k
w
u ,
1
*
k
w
u
) , if
1
*
k
k
w
u fr
, and the value of
is considerably greater than the accuracy of IPOPT ( 8
10
). Thus, we
may conclude that the stopping condition of the decomposition algorithm
is always reached in a finite number of iterations.
We claim that the point * ( )* * *
( , )
k
k
kw
u u u R
is a point of local
minimum of the problem (1), (2), where * k
k
w
u R
is the last point of our
iterative procedure and
*
k is a vector of redefined values of the previously
deleted additional variables k
k R
. The assertion comes from the fact that
any arrangement of each pair of objects Ei and Ej subject to ( , ) \ ki j
guarantees that there always exists a vector k of additional variables such
that '
0, ( , ) \ij ki j at the point ( )*k
u . Here {( , ),i j
1,2,..., }i j n . Therefore the values of additional variables of the vector
k have no effect on the value of our objective function, i. e
* ( )*
( ) ( )
k
k
wF u F u . That is why, indeed, we do not need to redefine the delet-
ed additional variables of the vector k at the last step of our algorithm.
So, while there are O( 2
n ) pairs of objects in the container, our algo-
rithm may in most cases only actively controls O(n) pairs of objects (this
depends on the sizes of objects and the value of ), because for each ob-
ject only its « -neighbors» have to be monitored.
Серія: Технічні науки. Випуск 19
131
The parameter provides a balance between the number of inequali-
ties in each nonlinear programming subproblem and the number of the
subproblems which we need to generate and solve in order to get a local
optimal solution of problem (1), (2).
Concluding remarks. The proposed decomposition algorithm allows
us to reduce the problem (1), (2) with O( 2
n ) inequalities and a O( 2
n )-
dimensional feasible set W to a sequence of subproblems (3), (4), each
with O( n ) inequalities and a O( n )-dimensional solution subset kW . This
reduction is of a paramount importance, since we deal with nonlinear op-
timization problems. We are going to apply our algorithm to optimization
placement problems for composed 2D and 3D objects in the near future.
Reference:
1. Wascher G., Hauner H. and Schumann H. An improved typology of cutting
and packing problems. European Journal of Operational Research. 2007.
Vol. 183 (3), № 16. P. 1109–1130.
2. Bennell J., Oliveira J. The geometry of nesting problems. A tutorial. European
J. Operational Research. 2008. Vol. 184. P. 397–415.
3. Chazelle B., Edelsbrunner H., Guibas L. The complexity of cutting complexes.
Discrete & Computational Geometry. 1989. Vol. 4 (2). P. 139–181.
4. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algo-
rithms for object packing problem. Computational Geometry: Theory and Ap-
plications. 2010. Vol. 43 (5). P. 535–553.
5. Stoyan Yu., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing
of ellipses. Journal of Global Optimzation. 2016. Vol. 65 (2). P. 283–307.
6. Wachter A., Biegler L. T. On the implementation of an interior-point filter
line-search algorithm for large-scale nonlinear programming. Mathematical
Programming. 2006. Vol. 106 (1). P. 25–57.
АЛГОРИТМ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗАННЯ
ОПТИМІЗАЦІЙНИХ ЗАДАЧ РОЗМІЩЕННЯ
У статті розглядається задача розміщення двовимірних опуклих
об'єктів у прямокутній області мінімальної площі, яка відноситься до
класу задач упаковки і розкрою. Об'єкти, що розміщуються, можуть
неперервно транслюватися і обертатися. Будується математична мо-
дель задачі розміщення у вигляді задачі нелінійного програмування з
використанням методу phi-функцій. Для пошуку локально-оптималь-
них розв’язків пропонується ефективний алгоритм декомпозиції, який
зводить вихідну задачу до послідовності підзадач нелінійного про-
грамування значно меншою розмірності з меншим числом нелінійних
нерівностей. Перевага цього підходу підтверджується результатами
численних експериментів.
Ключові слова: задача розміщення, математична модель, нелі-
нійна оптимізація, алгоритм декомпозиції.
Date received 31.01.2019
|