Optimized Object Packings Using Quasi-Phi-Functions

Abstract

In this chapter we further develop the main tool of our studies,phi-functions. We define new functions, called quasi-phi-functions, that we use for analytic description of relations of geometric objects placed in a container taking into account their continuous rotations, translations, and distance constraints. The new functions are substantially simpler than phi-functions for some types of objects. They also are simple enough for some types of objects for which phi-functions could not be constructed. In particular, we derive quasi-phi-functions for certain 2D&3D-objects. We formulate a basic optimal packing problem and introduce its exact mathematical model in the form of a nonlinear continuous programming problem, using our quasi-phi-functions. We propose a general solution strategy, involving: a construction of feasible starting points, a generation of nonlinear subproblems of a smaller dimension and decreased number of inequalities; a search for local extrema of our problem using subproblems. To show the advantages of our quasi-phi-functions we apply them to two packing problems, which have a wide spectrum of industrial applications: packing of a given collection of ellipses into a rectangular container of minimal area taking into account distance constraints; packing of a given collection of 3D-objects, including cuboids, spheres, spherocylinders and spherocones, into a cuboid container of minimal height. Our efficient optimization algorithms allow us to get local optimal object packings and reduce considerably computational cost. We applied our algorithms to several inspiring instances: our new benchmark instances and known test cases.

13.1 Introduction

Optimal packing problem is a part of operational research and computational geometry. It has multiple applications in modern biology, mineralogy, medicine, materials science, nanotechnology, robotics, coding, pattern recognition systems, control systems, space apparatus control systems, as well as in the chemical industry, power engineering, mechanical engineering, shipbuilding, aircraft construction, civil engineering, logistics, etc. At present, the interest in finding effective solutions for packing problems is growing rapidly. This is due to a large and growing number of applications and an extreme complexity of methods used to handle many of them. We refer the reader to [1] for typology of the class of problems.

These problems are NP-hard [2], and, as a result, solution methodologies generally employ heuristics, e.g. [3–16]. Some researchers develop approaches based on mathematical modeling and general optimization procedures; e.g. [17–25].

Our approach is based on mathematical modeling of relations between geometric objects and thus reducing the Optimal Packing Problem to a nonlinear programming problem. We use the phi-function technique [26, 27] for an analytic description of relations of objects to be packed in a container taking into account their continuous rotations, translations, and distance constraints. In [28] we review our phi-functions. One may also find there a clear definition of a phi-function. There we construct a mathematical model of a basic placement (cutting and packing) problem using phi-functions as a constrained optimization problem. We propose a solution strategy for placement problems. The paper also considers a layout problem encountered in space engineering and provides a number of computational results for 2D- and 3D-applications. The complete class of phi-functions for basic 2D-objects are derived in[29]. The functions allow us to cover a wide spectrum of irregular packing problems involving arbitrary shaped 2D-objects, bounded by circular arcs and line segments; see, e.g., [30]. Phi-functions for the simplest 3D-objects under continuous rotations, such as parallelepipeds, convex polytopes, and spheres, are considered in [31, 32]. But some of these phi-functions (especially for 3D-objects) happen to be rather complicated, analytically, and difficult in practical use. Our attempts to construct convenient phi-functions for more general types of objects have been futile.

In this chapter we further develop the concept of phi-functions, introducing a new class of functions, called quasi-phi-functions. The functions can be described by analytical formulas that are substantially simpler than those used for phi-functions, for pairs of some types of 2D- and 3D-objects (convex polygons, circles, circular segments, cuboids, spheres, cylinders, disks, and convex polytopes). They also are simple enough for some types of rotating objects for which phi-functions could not be constructed. In particular, we find convenient quasi-phi-functions for ellipses, and for certain 3D-objects including, so-called, spherocylinders, spherocones. The use of quasi-phi-functions allows us to handle new types of objects, but there is a price to pay: now the optimization has to be performed over a larger set of parameters, including the extra variables used by our new functions. To demonstrate high efficiency of our quasi-phi-functions we consider two practical problems of packing a collection of ellipses into a rectangular container of minimal area as well as packing a collection of given 3D-objects (cuboids, spheres, spherocylinders, spherocones) into a cuboid container of minimal height. We derive here quasi-phi-functions to describe non-overlapping and containment constraints for appropriate pairs of rotating objects and develop efficient optimization algorithms. In this chapter the reader will find theoretical results presented in our works [33, 34].

The chapter is organized as follows: in Sect. 13.2 we define our new quasi-phi-functions for an analytical description of non-overlapping, containment, and distance constraints; we also discuss their general properties. In Sect. 13.3 we define quasi-phi-functions for certain types of convex 2D- and 3D-objects needed in applications. In Sect. 13.4 we formulate a basic optimal packing problem, construct its mathematical model, using our quasi-phi-functions, in the form of a nonlinear programming problem with nonsmooth functions, and develop a general solution strategy. In Sect. 13.5 we formulate the optimal packing problem of ellipses taking into account continuous ellipse rotations and distance constraints as a continuous nonlinear programming problem with smooth functions; describe the algorithm to search for “good” local optimal solutions for the problem which involves a fast starting point and efficient local optimization procedures. In Sect. 13.6 we formulate the optimal packing problem of 3D-objects, including spherocylinders and spherocones, and based on characteristics of its mathematical model, describe an efficient solution algorithm, using local and global optimization methods. We provide some computational results of several instances for 2D- and 3D-optimal packing problems, illustrated with pictures, in Sect. 13.7, and finish with some concluding remarks in Sect. 13.8.

13.2 Quasi-Phi-Functions and Their Properties

Let $A\subset {R}^d$ and $B\subset {R}^d$ be closed phi-objects, $d=2,3$; one can find a precise definition of phi-objects, e.g., in [26, 27]. We assume that at least one of these objects is bounded. Position of the object A is defined by a vector of placement parameters (v _A , θ _A ), where v _A is a translation vector and θ _A is a vector of rotation parameters: for 2D object v _A ${=}\left({x}_A,{y}_A\right)$ and θ _A is a rotation angle; for 3D-object ${v}_A=\left({x}_A,{y}_A,{z}_A\right)$ and ${\theta}_A=\left({\theta}_z,{\theta}_x,{\theta}_y\right)$, where θ _z , θ _x , θ _y are rotation angles, respectively: from axis OX to OY, from axis OY to OZ and from axis OX to OZ. We denote the vector of variables for the object A by ${u}_A=\left({v}_A,{\theta}_A\right)$ and the vector of variables for the object B by ${u}_B=\left({v}_B,{\theta}_B\right)$. The object A, rotated by angles θ _z , θ _x , θ _y (in this order), translated by vector v _A , will be denoted by A(u _A ).

Definition 1

A continuous and everywhere defined function Φ′^AB(u _A , u _B , u ′) is called a quasi-phi-function for two phi-objects A(u _A ) and B(u _B ) if $\underset{u'\in U}{ \max }\break {\varPhi{'}}^{AB}\left({u}_A,{u}_B,u{'}\right)$ is a phi-function Φ ^AB(u _A , u _B ) for the objects. Here u′ is a vector of auxiliary variables, that takes values in some domain $U\subset {R}^n$ (which may depend on the shapes of objects A and B).

The concept of quasi-phi-functions and basic characteristics of quasi-phi-functions formulated in the form of theorems are introduced in [33].

We emphasize that according to the definition, a quasi-phi-function Φ′^AB for a pair of objects A and B can be constructed by many different formulas, and we can choose the most convenient ones for our optimization algorithms.

Next we discuss general properties of quasi-phi-functions. Let Φ′^AB(u _A , u _B , u ′) be a quasi-phi-function for two phi-objects A(u _A ) and B(u _B ).

Property 1

If ${\varPhi{'}}^{AB}\left({u}_A,{u}_B,u'\right)\ge 0$ for some u′, then $\operatorname{int}A\left({u}_A\right)\cap \operatorname{int}B\left({u}_B\right)=\varnothing$. Here int A denotes the topological interior of object A.

Property 2

Let $P\left({u}_P\right)=\left\{\left(x,y,z\right):{\psi}_P=\alpha \cdot x+\beta \cdot y+\gamma \cdot z+{\mu}_P\le 0\right\}$ be a half-space (for d = 2 it will be a half-plane; see below); here, ${u}_P=\left({\theta_x}_P,{\theta_y}_P,{\mu}_P\right)$, $\alpha = \sin {\theta}_{yP},$ $\beta = \sin {\theta}_{xP}\cdot \cos {\theta}_{yP},$ $\gamma = \cos {\theta}_{xP}\cdot \cos {\theta}_{yP}$ (note ${\alpha}^2+{\beta}^2+{\gamma}^2=1$). If $A,B\subset {R}^2$, then $P\left({u}_P\right)=\left\{\left(x,y\right):{\psi}_P=\alpha \cdot x+\beta \cdot y+{\mu}_P\le 0\right\}$, where ${u}_P=\left({\theta}_P,{\mu}_P\right)$ $\alpha = cos{\theta}_P$, $\beta = sin{\theta}_P$. Suppose Φ ^AP(u _A , u _P ) is a phi-function for A(u _A ) and P(u _P ) and ${\varPhi}^{B{P}^{\ast }}\left({u}_B,{u}_P\right)$ is a phi-function for B(u _B ) and ${P}^{*}\left({u}_P\right)={R}^d\backslash \operatorname{int}P\left({u}_P\right)$, $d=2,3$.

Then a function defined by

$$ {\varPhi{'}}^{AB}\left({u}_A,{u}_B,{u}_P\right)= \min \left\{{\varPhi}^{AP}\left({u}_A,{u}_P\right),{\varPhi}^{B{P}^{\ast }}\left({u}_B,{u}_P\right)\right\}, $$

(13.1)

is a quasi-phi-function for the pair of bounded objects A(u _A ) and B(u _B ). Here$u'={u}_P$.

Property 3

If Φ ′ ^AP(u _A , u _P , u ^'₁ ) is a quasi-phi-function for A(u _A ) and P(u _P ), $\varPhi {'}^{B{P}^{\ast }}({u}_B,{u}_P,{u}_2^{'})$ is a quasi-phi-function for B(u _B ) and P*(u _P ), then function

$$ {\varPhi{'}}^{AB}\left({u}_A,{u}_B,{u}^{'}\right)= \min \left\{{\varPhi{'}}^{AP}\left({u}_A,{u}_P,{u}_1^{'}\right),{\varPhi{'}}^{B{P}^{\ast }}\left({u}_B,{u}_P,{u}_2^{'}\right)\right\}, $$

(13.2)

is a quasi-phi-function for the pair of bounded objects A(u _A ) and B(u _B ). Here $u'=({u}_P,{u}_1^{'},{u}_2^{'})$.

We adapt the concept of quasi-phi-functions to model distance constraints. To this end we define normalized and adjusted quasi-phi-functions [33], based on similar terms for phi-functions [27].

Let $\mathrm{dist}\left(A,B\right)=\underset{a\in A,b\in B}{ \min }d\left(a,b\right)$, where d(a, b) stands for the Euclidean distance between points $a,b\in {R}^d$, $d=2,3$, and let ${\rho}^{-}>0$ denote minimal allowable distances between objects A(u _A ) and B(u _B ).

We remind the reader that by definition (see for instance [27]) a phi-function ${\tilde{\varPhi}}^{AB}\left({u}_A,{u}_B\right)$ for objects A(u _A ) and B(u _B ) is said to be a normalized phi-function if ${\tilde{\varPhi}}^{AB}\left({u}_A,{u}_B\right)=\mathrm{dist}\left(A\left({u}_A\right),B\left({u}_B\right)\right)$ whenever $\operatorname{int}A\left({u}_A\right)\cap \operatorname{int}B\left({u}_B\right)=\varnothing$.

Definition 2

A quasi-phi-function ${{\tilde{\varPhi}}{'}}^{AB}\left({u}_A,{u}_B,u'\right)$ is called a normalized quasi-phi-function for objects A(u _A ) and B(u _B ), if function $\underset{u'\in U}{ \max }{{\tilde{\varPhi}}{'}}^{AB}\left({u}_A,{u}_B,u'\right)$ is a normalized phi-function.

Thus, $\underset{u'\in U}{ \max }{{\tilde{\varPhi}}^{'}}{}^{AB}\ge {\rho}^{-}\iff \operatorname{dist}\left(A,B\right)\ge {\rho}^{-}$.

Definition 3

Function ${{\overset{\frown }{\varPhi}}^{'}}^{AB}\left({u}_A,{u}_B,u'\right)$ is called an adjusted quasi-phi-function for objects A(u _A ) and B(u _B ), if function $\underset{u'\in U}{ \max }{{\overset{\frown }{\varPhi}}^{'}}^{AB}\left({u}_A,{u}_B,u'\right)$ is an adjusted phi-function.

Thus, $\underset{u'\in U}{ \max }{{\overset{\frown }{\varPhi}}^{'}}^{AB}\ge 0\iff \operatorname{dist}\left(A,B\right)\ge {\rho}^{-}$.

Let ${\tilde{\varPhi}}^{AP}\left({u}_A,{u}_P\right),$ ${\tilde{\varPhi}}^{B{P}^{\ast }}\left({u}_B,{u}_P\right)$ be normalized phi-functions. Assume

$$ {\varPhi{'}}^{AB}\left({u}_A,{u}_B,{u}_P\right)= \min \left\{{\tilde{\varPhi}}^{AP}\left({u}_A,{u}_P\right),{\tilde{\varPhi}}^{B{P}^{\ast }}\left({u}_B,{u}_P\right)\right\}. $$

Then a quasi-phi-function

$$ \tilde{\varPhi}{'}^{AB}\left({u}_A,{u}_B,{u}_P\right)=2{\varPhi{'}}^{AB}\left({u}_A,{u}_B,{u}_P\right), $$

(13.3)

is a normalized quasi-phi-function, and a quasi-phi-function

$$ \overset{\frown }{\varPhi }{'}^{AB}\left({u}_A,{u}_B,{u}_P\right)={\varPhi{'}}^{AB}\left({u}_A,{u}_B,{u}_P\right)-0.5{\rho}^{-}, $$

(13.4)

is an adjusted quasi-phi-function.

13.3 Construction of Quasi-Phi-Functions

Here we derive quasi-phi-functions for certain 2D- and 3D-objects, based on our general formulas (13.1)–(13.3).

A quasi-phi-function for convex polygons. Let K ₁(u ₁) and K ₂(u ₂) be convex polygons, given by their vertices ${p}_i^1,i=1,....,{m}_1$, and ${p}_i^2,i=1,....,{m}_2$, respectively. Then ${\varPhi}^{K_1P}\left({u}_1,{u}_P\right)=\underset{1\le i\le {m}_1}{ \min }{\psi}_P\left({p}_i^1\right)$ and ${\varPhi}^{K_2P}\left({u}_2,{u}_P\right)=\underset{1\le i\le {m}_2}{ \min}\left(-{\psi}_P\left({p}_i^2\right)\right)$ are phi-functions for K ₁(K ₂) and P(P*), respectively.

Now the function

$$ {\varPhi{'}}^{K_1{K}_2}\left({u}_1,{u}_2,{u}_P\right)= \min \left\{{\varPhi}^{K_1P}\left({u}_1,{u}_P\right),{\varPhi}^{K_2{P}^{\ast }}\left({u}_2,{u}_P\right)\right\}, $$

(13.5)

is a quasi-phi-function for K ₁(u ₁) and K ₂(u ₂).

Note that function $2{\varPhi{'}}^{K_1{K}_2}\left({u}_1,{u}_2,{u}_P\right)$ is a normalized quasi-phi-function.

An adjusted quasi-phi-function for K ₁(u ₁) and K ₂(u ₂) is defined by

$$ {{\overset{\frown }{\varPhi}}}^{{'}^{K_1{K}_2}}\left({u}_1,{u}_2,{u}_P\right)= \min \left\{{\varPhi}^{K_1P}\left({u}_1,{u}_P\right),{\varPhi}^{K_2{P}^{\ast }}\left({u}_2,{u}_P\right)\right\}-0.5{\rho}^{-}. $$

(13.6)

A quasi-phi-function for a convex polygon K(u ₁) and a circle C(u ₂). Let K(u ₁) be a convex polygon given by its vertices ${p}_i,i=1,....,m$. Let p _C and r _C be the center and radius of circle C(u ₂). Then ${\varPhi}^{KP}\left({u}_1,{u}_P\right)=\underset{1\le i\le m}{ \min }{\psi}_P\left({p}_i\right)$ and ${\varPhi}^{C{P}^{*}}\left({u}_2,{u}_P\right)=-{\psi}_P\left({p}_C\right)-{r}_C$ are phi-functions.

Now a quasi-phi-function for K(u ₁) and C(u ₂) may be defined as:

$$ {\varPhi{'}}^{CK}\left({u}_1,{u}_2,{u}_P\right)= \min \left\{{\varPhi}^{KP}\left({u}_1,{u}_P\right),{\varPhi}^{C{P}^{\ast }}\left({u}_2,{u}_P\right)\right\}. $$

(13.7)

It should be noted that function 2Φ′^CK(u ₁, u ₂, u _P ) is a normalized quasi-phi-function.

Quasi-phi-functions defined by (13.5)–(13.7) can be applied to convex polytopes and spheres.

A quasi-phi-function for circular segments D ₁(u ₁) and D ₂(u ₂). Let ${D}_1\left({u}_1\right)={T}_1\left({u}_1\right)\cap {C}_1\left({u}_1\right)$, ${D}_2\left({u}_2\right)={T}_2\left({u}_2\right)\cap {C}_2\left({u}_2\right)$ be two circular segments, where T ₁(u ₁) (T ₂(u ₂)) denotes a triangle given by its vertices p ¹ _i (p ² _i ), $i=1,2,3$ (we note that two sides of T have to be tangents to C and one side is a chord of C) and ${p}_C^1=\left({x}_1,{y}_1\right)$ (${p}_C^2=\left({x}_2,{y}_2\right)$) and r ¹ _C (r ² _C ) denote the center and radius of C ₁(u ₁) (resp., C ₂(u ₂)). Then, following (13.1), a quasi-phi-function for D ₁(u ₁) and D ₂(u ₂) may be defined by

$$ \varPhi {'}^{D_1{D}_2}\left({u}_1,{u}_2,{u}_P\right)= \min \left\{{\varPhi}^{D_1P}\left({u}_1,{u}_P\right),{\varPhi}^{D_2{P}^{\ast }}\left({u}_2,{u}_P\right)\right\}, $$

(13.8)

where ${\varPhi}^{D_1P}\left({u}_1,{u}_P\right)= \max \left\{{\varPhi}^{T_1P},{\varPhi}^{C_1P}\right\},{\varPhi}^{D_2{P}^{*}}\left({u}_2,{u}_P\right)= \max \left\{{\varPhi}^{T_2{P}^{*}},{\varPhi}^{C_2{P}^{*}}\right\}$, are phi-functions, and ${\varPhi}^{T_1P}\left({u}_1,{u}_P\right)=\underset{i=1,2,3}{ \min }{\psi}_P\left({p}_i^1\right),$ ${\varPhi}^{C_1P}\left({u}_1,{u}_P\right)={\psi}_P\left({p}_C^1\right)-{r}_C^1$, ${\varPhi}^{T_2{P}^{*}}\left({u}_2,{u}_P\right)=\underset{i=1,2,3}{ \min}\left(-{\psi}_P\left({p}_i^2\right)\right)$, ${\varPhi}^{C_2{P}^{*}}\left({u}_2,{u}_P\right)=-{\psi}_P\left({p}_C^2\right)-{r}_C^2$.

We can define a quasi-phi-function for D ₁(u ₁) and D ₂(u ₂) using formula (13.2)

$$ \varPhi {'}^{D_1{D}_2}\left({u}_1,{u}_2,u'\right)= \min \left\{\varPhi {'}^{D_1P}\left({u}_1,{u}_P,{u}_1^{'}\right),\varPhi {'}^{D_2{P}^{\ast }}\left({u}_2,{u}_P,{u}_2^{'}\right)\right\}, $$

where $u'=\left({u}_P,{u}_1^{'},{u}_2^{'}\right)$, ${u}_1^{'}\in \left[0,1\right]\subset {R}^1$, ${u}_2^{'}\in \left[0,1\right]\subset {R}^1$.

To this end, first, we construct quasi-phi-functions $\varPhi {'}^{D_1P}\left({u}_1,{u}_P,{u}_1^{'}\right)$ and $\varPhi {'}^{D_2{P}^{\ast }}\left({u}_2,{u}_P,{u}_2^{'}\right)$. Let ${\varPhi}^{C_1P}\left({u}_1,{u}_P\right)$ be a phi-function for C ₁(u ₁) and P(u _p ). We introduce function

$$ \varPhi {'}^{D_1P}\left({u}_1,{u}_P,{u}_1^{'}\right)= \min \left\{{\psi}_P\left({p}_1^1\right),{\psi}_P\left({p}_2^1\right),{\chi}_1\left({u}_1,{u}_P,{u}_1^{'}\right)\right\}, $$

$$ {\chi}_1\left({u}_1,{u}_P,{u}_1^{'}\right)={\psi}_P\left({p}_3^1\right)-{u}_1^{'}{\psi}_P\left({p}_3^1\right)+{u}_1^{'}{\varPhi}^{C_1P}\left({u}_1,{u}_P\right), $$

where ${u}_1^{'}\in \left[0,1\right]\subset {R}^1$, p ¹ _i , $i=1,2$, are the endpoints of the chord of D ₁(u ₁).

By analogy we have

$$ \varPhi {'}^{D_2P}\left({u}_2,{u}_P,{u}_2^{'}\right)= \min \left\{-{\psi}_P\left({p}_1^2\right),-{\psi}_P\left({p}_2^2\right),{\chi}_2\left({u}_2,{u}_P,{u}_2^{'}\right)\right\}, $$

$$ {\chi}_2\left({u}_2,{u}_P,{u}_2^{'}\right)=-{\psi}_P\left({p}_3^2\right)-{u}_2^{'}\left(-{\psi}_P\left({p}_3^2\right)\right)+{u}_2^{'}{\varPhi}^{C_2{P}^{*}}\left({u}_2,{u}_P\right), $$

where ${u}_2^{'}\in \left[0,1\right]\subset {R}^1$, p ² _i , $i=1,2$, are the endpoints of the chord of D ₂(u ₂).

The a quasi-phi-function defined by (13.8) may be adapted to a pair of spherical segments defined as intersections of right circular cones with solid spheres.

A quasi-phi-function for ellipses. Let E ₁(u ₁) and E ₂(u ₂) be two ellipses with semi-axes a _i and b _i , ${a}_i>{b}_i$ $i=1,2$.

Then, a quasi-phi-function for E ₁(u ₁) and E ₂(u ₂) may be defined as follows:

$$ {\varPhi{'}}^{E_1{E}_2}\left({u}_1,{u}_2,u'\right)= \min \left\{\chi \left({\theta}_1,{\theta}_2,u'\right),{\chi}^{+}\left({u}_1,{u}_2,u'\right),{\chi}^{-}\left({u}_1,{u}_2,u'\right)\right\}, $$

(13.9)

where θ ₁ and θ ₂ are rotation angles and ${u}^{'}=\left({t}_1,{t}_2\right)$ is a vector of auxiliary parameters, $0\le {t}_i\le 2\pi$, $i=1,2$; functions $\chi, {\chi}^{+},{\chi}^{-}$ are defined below.

The parameter t _i specifies a point on ellipse E _i . In the local coordinate system of ellipse E _i that point is $\left({x}_i^t,{y}_i^t\right)=\left({a}_i \cos {t}_i,{b}_i \sin {t}_i\right)$, and after rotation and translation its coordinates are $\left({x}_i^{'},{y}_i^{'}\right)={v}_i+M\left({\theta}_i\right)\cdot \left({x}_i^t,{y}_i^t\right)$, where M(θ) denotes the standard rotation matrix, ${v}_i=\left({x}_i,{y}_i\right)$ is a translation vector of E _i .

Now we define the three functions mentioned in (13.9): $\chi =-\left\langle {N}_1^{'},{N}_2^{'}\right\rangle$, where ${N}_i^{'}=\left({\alpha}_i^{'},{\beta}_i^{'}\right)=M\left({\theta}_i\right)\left({\alpha}_i,{\beta}_i\right)$, ${\alpha}_i=\frac{ \cos {t}_i}{a_i},{\beta}_i=\frac{ \sin {t}_i}{b_i}$; ${\chi}^{\pm }={\psi}_1\left({x}_2^{\pm }-{x}_1,{y}_2^{\pm }-{y}_1\right)={\alpha}_1^{'}\left({x}_2^{\pm }-{x}_1\right)+{\beta}_1^{'}\left({y}_2^{\pm }-{y}_1\right)-1$, where $\left({x}_2^{\pm },{y}_2^{\pm}\right)$ are coordinates of two points ${q}_2^{\pm }$ on the second tangent line, $\left({x}_2^{\pm },{y}_2^{\pm}\right)=\left({x}_2^{'},{y}_2^{'}\right)\pm \eta \left(-{\beta}_2^{'},{\alpha}_2^{'}\right)$, $\eta ={\left({a}_2\right)}^2$, 〈N ^′₁ , N ^′₂ 〉 is a scalar product of vectors N ^′₁ and N ^′₂ .

Alternatively, a quasi-phi-function for E ₁(u ₁) and E ₂(u ₂) may be defined according to (13.2):

$$ \varPhi {'}^{E_1{E}_2}\left({u}_1,{u}_2,u'\right)= \min \left\{\varPhi {'}^{E_1P}\left({u}_1,{u}_P,{u}_1^{'}\right),\varPhi {'}^{E_2{P}^{\ast }}\left({u}_2,{u}_P,{u}_2^{'}\right)\right\}. $$

It remains to define a quasi-phi-function for an ellipse E(u _E ) and a half-plane P(u _P ). This can be done as follows:

$$ \varPhi {'}^{EP}\left({u}_E,{u}_P,t\right)= \min \left\{\chi \left({\theta}_E,{\theta}_P,t\right),{\psi}_P^{+}\left({u}_E,{u}_P,t\right),{\psi}_P^{-}\left({u}_E,{u}_P,t\right)\right\}, $$

(13.10)

where ${u}_P=\left({\theta}_P,{\mu}_P\right)$, $0\le t\le 2\pi$ is auxiliary parameter.

Here the half-plane is defined by ${\psi}_P\left(x,y\right)={\alpha}_Px+{\beta}_Py+{\mu}_P\le 0$, where $\alpha = cos{\theta}_P$, $\beta = sin{\theta}_P$.

Note that ${N}_P=\left({\alpha}_P,{\beta}_P\right)$ is the corresponding outer normal vector for the half-plane. For ellipse E(u _E ) we adopt our previous formulas introduced for E ₂(u ₂), i.e. ${N}_2^{'}=\left({\alpha}_2^{'},{\beta}_2^{'}\right)$ and $\left({x}_2^{\pm },{y}_2^{\pm}\right)$, we just replace the subscript 2 with E in those formulas. Thus ${\psi}_P^{\pm}\left({x}_E^{\pm },{y}_E^{\pm}\right)={\alpha}_P{x}_E^{\pm }+{\beta}_P{y}_E^{\pm }+{\mu}_P\le 0.$ Lastly we define $\chi =-\left\langle {N}_P,{N}_E^{'}\right\rangle$, which completes our construction of (13.10), here 〈N _P , N ^' _E 〉 is a scalar product of vectors N _P and N ^' _E .

Now let a minimal allowable distance between two ellipses E ₁ and E ₂ be given, we denote it by ${\rho}^{-}$. Assume that $\overset{\frown }{\varPhi }{'}^{E_1P}\left({u}_1,{u}_P\right),$ $\overset{\frown }{\varPhi }{'}^{E_2{P}^{\ast }}\left({u}_2,{u}_P\right)$ are adjusted quasi-phi-functions provided that $\underset{u_P\in U}{ \max}\overset{\frown }{\varPhi }{'}^{E_1P}\left({u}_1,{u}_P\right)\ge 0$ if $\operatorname{dist}\left({E}_1,P\right)\ge 0.5{\rho}^{-}$ and $\underset{u_P\in U}{ \max}\overset{\frown }{\varPhi }{'}^{E_2{P}^{*}}\left({u}_2,{u}_P\right)\ge 0$ if $\operatorname{dist}\left({E}_2,{P}^{*}\right)\ge 0.5{\rho}^{-}$. Then

$$ \overset{\frown }{\varPhi }{'}^{E_1{E}_2}\left({u}_1,{u}_2,{u}_P\right)= \min \left\{\overset{\frown }{\varPhi }{'}^{E_1P}\left({u}_1,{u}_P\right),\overset{\frown }{\varPhi }{'}^{E_2{P}^{\ast }}\left({u}_2,{u}_P\right)\right\}, $$

(13.11)

is an adjusted quasi-phi-function for distance constraint $\operatorname{dist}\left({E}_1,{E}_2\right)\ge {\rho}^{-}$.

A quasi-phi-function for ellipse E(u ₁) and the complement of the interior of Ω

Let E(u ₁) be an ellipse with variable parameters ${u}_1=\left({x}_1,{y}_1,{\theta}_1\right)$, and let Ω be a rectangular container with vertices ${p}_1=\left(0,0\right)$, ${p}_2=\left(l,0\right)$, ${p}_3=\left(l,w\right)$, ${p}_4=\left(0,w\right)$. We denote ${\varOmega}^{*}={R}^2\backslash \operatorname{int}\varOmega$.

Then a quasi-phi-function for E and Ω* may be defined as

$$\begin{array}{llll}{\varPhi^{\prime}}^{E{\varOmega}^{*}}\left({u}_1,{t}_1^{\prime},{t}_2^{\prime}\right)=& \min \left\{{\varphi}_{11}\left({p}_1\right),{\varphi}_{11}\left({p}_2\right),{\varphi}_{12}\left({p}_3\right),{\varphi}_{12}\left({p}_4\right),{\varphi}_{21}\left({p}_2\right),\right.\\ &\left.{\varphi}_{21}\left({p}_3\right),{\varphi}_{22}\left({p}_1\right),{\varphi}_{22}\left({p}_4\right)\right\},\end{array}$$

(13.12)

where ${t}_{{}_2}^{'}\ne {t}_{{}_1}^{'}\in \left[0,2\pi \right]$, ${\varphi}_{11}={A}_1x+{B}_1y+{C}_1-1$, ${\varphi}_{12}=-{A}_1x-{B}_1y-{C}_1-1$, ${A}_1={\alpha}_1\cdot \cos {\theta}_1+{\beta}_1\cdot \sin {\theta}_1$, ${B}_1=-{\alpha}_1\cdot \sin {\theta}_1+{\beta}_1\cdot \cos {\theta}_1$, ${\alpha}_1=\frac{ \cos {t}_1^{'}}{a},$ ${\beta}_1=\frac{ \sin {t}_1^{'}}{b}$, ${C}_1=-{A}_1{x}_1-{B}_1{y}_1$, ${\varphi}_{21}={A}_2x+{B}_2y+{C}_2-1$, ${\varphi}_{22}=-{A}_2x-{B}_2y-{C}_2-1$, ${A}_2={\alpha}_2\cdot \cos {\theta}_2+{\beta}_2\cdot \sin {\theta}_2$, ${B}_2=-{\alpha}_2\cdot \sin {\theta}_2+{\beta}_2\cdot \cos {\theta}_2$, ${C}_2=-{A}_2{x}_2-{B}_2{y}_2$, ${\alpha}_2=\frac{ \cos {t}_2^{'}}{a},$ ${\beta}_2=\frac{ \sin {t}_2^{'}}{b}$.

Let a minimal allowable distance ${\rho}^{-}$ between an ellipse E(u ₁) and the frontier of the rectangle Ω be given. Then function

$$ \begin{array}{l}{\overset{\frown }{\varPhi}}^{E{\varOmega}^{*}} (u_1, t_1^{^{'}}, t_2^{^{'}})= \min \Big\{{\varphi}_{11}\left({p}_{{}_1}^{-}\right),{\varphi}_{11}\left({p}_{{}_2}^{-}\right),{\varphi}_{12}\left({p}_{{}_3}^{-}\right),{\varphi}_{12}\left({p}_{{}_4}^{-}\right),\\ {} {\varphi}_{21}\left({p}_{{}_2}^{-}\right),{\varphi}_{21}\left({p}_{{}_3}^{-}\right),{\varphi}_{22}\left({p}_{{}_1}^{-}\right),{\varphi}_{22}\left({p}_{{}_4}^{-}\right)\Big\},\end{array} $$

(13.13)

is an adjusted quasi-phi-function enforcing the distance constraint $\operatorname{dist}\left({E}_1,{\varOmega}^{*}\right)\ge {\rho}^{-}$, where ${p}_{{}_i}^{-},i=1,2,3,4$ are vertices of region ${\varOmega}^{*}\oplus C\left({\rho}^{-}\right)$, $C\left({\rho}^{-}\right)$ is circle of radius ${\rho}^{-}$, i.e. ${p}_{{}_1}^{-}=\left({\rho}^{-},{\rho}^{-}\right)$, ${p}_{{}_2}^{-}=\left(l-{\rho}^{-},{\rho}^{-}\right)$, ${p}_{{}_3}^{-}=\left(l-{\rho}^{-},w-{\rho}^{-}\right)$, ${p}_{{}_4}^{-}=\left({\rho}^{-},w-{\rho}^{-}\right)$, $\oplus$ is a symbol of Minkovski sum [35].

A quasi-phi-function for two spherocones ${\overset{\frown }{\mathbb{T}}}_1$ and ${\overset{\frown }{\mathbb{T}}}_2$. Further a convex object $\overset{\frown }{\mathbb{T}}$ we call a spherocone, if $\overset{\frown }{\mathbb{T}}={\mathbb{D}}_1\cup \overline{\mathbb{T}}\cup {\mathbb{D}}_2$, where: $\overline{\mathbb{T}}$ is a truncated cone of height 2e, with radius r ₁ of the upper base and radius r ₂ of the lower base, ${r}_1\ge {r}_2$; ${\mathbb{D}}_k$ is a spherical segment of sphere ${\mathbb{S}}_k$ of radius ${R}_k=\frac{r_k^2+{\varpi}_k^2}{2{\varpi}_k},$ $k=1,2$, ${\mathbb{D}}_1$ is an upper spherical segment of height ϖ ₁ and the base radius r ₁; ${\mathbb{D}}_2$ is a lower spherical segment of height ϖ ₂ and the base radius r ₂.

A quasi-phi-function for spherocones ${\overset{\frown }{\mathbb{T}}}_1\left({u}_1\right)$ and ${\overset{\frown }{\mathbb{T}}}_2\left({u}_2\right)$ can be derived as

$$ {\varPhi}^{'\kern0.24em {\overset{\frown }{\mathbb{T}}}_1{\overset{\frown }{\mathbb{T}}}_2}\left({u}_1,{u}_2,{u}_p\right)= min\left\{{\varPhi}^{{\overset{\frown }{\mathbb{T}}}_1P}\left({u}_1,{u}_p\right),{\varPhi}^{{\overset{\frown }{\mathbb{T}}}_2P*}\left({u}_2,{u}_p\right)\right\}, $$

(13.14)

where ${\varPhi}^{{\overset{\frown }{\mathbb{T}}}_1P}$ and ${\varPhi}^{{\overset{\frown }{\mathbb{T}}}_2P*}$ are phi-functions for objects ${\overset{\frown }{\mathbb{T}}}_1$ and P, and objects ${\overset{\frown }{\mathbb{T}}}_2$ and P* respectively. Now we define

$$ {\varPhi}^{{\overset{\frown }{\mathbb{T}}}_1P}\left({u}_1,{u}_p\right)= min\left\{{\varPhi}^{{\mathbb{D}}_{11}P}\left({u}_1,{u}_p\right),{\varPhi}^{{\mathbb{D}}_{12}P}\left({u}_1,{u}_p\right)\right\}, $$

(13.15)

$$ {\varPhi}^{\;{\overset{\frown }{\mathbb{T}}}_2P*}\left({u}_2,{u}_p\right)= min\left\{{\varPhi}^{{\mathbb{D}}_{21}P*}\left({u}_2,{u}_p\right),{\varPhi}^{{\mathbb{D}}_{22}P*}\left({u}_2,{u}_p\right)\right\}, $$

(13.16)

where ${\varPhi}^{{\mathbb{D}}_{11}P}\left({u}_1,{u}_p\right),$ ${\varPhi}^{{\mathbb{D}}_{12}P}\left({u}_1,{u}_p\right)$, ${\varPhi}^{{\mathbb{D}}_{21}P*}\left({u}_2,{u}_p\right),$ ${\varPhi}^{{\mathbb{D}}_{22}P*}\left({u}_2,{u}_p\right)$ are phi-functions for ${\mathbb{D}}_{11}$ (or ${\mathbb{D}}_{12}$) and P, and for ${\mathbb{D}}_{21}$ (or ${\mathbb{D}}_{22}$) and P*, respectively.

It remains to define a phi-function for a spherical segment $\mathbb{D}\left({u}_1\right)$ and a half-space P(u _P ). This can be done as follows:

$$ {\varPhi}^{\mathbb{D}P}\left({u}_1,{u}_p\right)= max\left\{ min\left\{{\rho}_1\left({u}_1,{u}_p\right),{\rho}_3\left({u}_1,{u}_p\right)\right\},{\rho}_2\left({u}_1,{u}_p\right)\right\}, $$

(13.17)

where ${\rho}_1\left({u}_1,{u}_p\right)={\psi}_p+e{\zeta}_p-r\sqrt{1-{\zeta}_p^2},$ ${\rho}_2\left({u}_1,{u}_p\right)={\psi}_p-R+q{\zeta}_p,$ ${\zeta}_p=\alpha sin{\theta}_{y_p}-\beta sin{\theta}_{x_p} cos{\theta}_{y_p}+\gamma cos{\theta}_{x_p} \cos {\theta}_{y_p}$, $q=e+\varpi -R$, ${\rho}_3\left({u}_1,{u}_p\right)={\psi}_p+\left(e+\frac{r^2}{e-q}\right){\zeta}_p.$

By analogy, replacing ψ _p by $-{\psi}_p$, we can derive a phi-function for a spherical segment $\mathbb{D}\left({u}_2\right)$ and a half-space P*(u _P ).

Remark

By altering the values of the sizes of $\overset{\frown }{\mathbb{T}}$ we can obtain the following shapes of 3D-objects: spherocylinder $\overset{\frown }{\mathbb{C}}$ if ${r}_1={r}_2$; truncated cone $\mathbb{T}$ if ${\varpi}_1={\varpi}_2=0$; circular cylinder ℂ if ${r}_1={r}_2$ and ${\varpi}_{1i}^0={\varpi}_{2i}^0=0$; cone $\widehat{\mathbb{T}}$ if ${r}_1={\varpi}_1={\varpi}_2=0$; spherical segment $\mathbb{D}$ if ${r}_2={\varpi}_2=e=0$ or ${r}_1={\varpi}_1=e=0$; spherical disk $\mathbb{E}$ if $e=0$ and ${r}_1={r}_2$.

Based on the quasi-phi-function for spherocones defined by relations (13.14)–(13.17) we can derive the following quasi-phi-functions:

for spherical segments ${\mathbb{D}}_1$ and ${\mathbb{D}}_2$

$$ {\varPhi}^{' {\mathbb{D}}_1{\mathbb{D}}_2}\left({u}_1,{u}_2,{u}_p\right)= min\left\{{\varPhi}^{{\mathbb{D}}_1P}\left({u}_1,{u}_p\right),{\varPhi}^{{\mathbb{D}}_2P*}\left({u}_2,{u}_p\right)\right\}; $$

(13.18)

for truncated cones ${\overline{\mathbb{T}}}_1$ and ${\overline{\mathbb{T}}}_2$

$$\begin{array}{lll} {\varPhi}^{\prime {\overline{\mathbb{T}}}_1{\overline{\mathbb{T}}}_2}\left({u}_1,{u}_2,{u}_p\right) & = min\left({\rho}_{11}^1\left({u}_1,{u}_p\right),{\rho}_{21}^1\left({u}_1,{u}_p\right),\right.\nonumber\\ &\left.\quad{\rho}_{11}^2\left({u}_2,{u}_p\right),{\rho}_{21}^2\left({u}_2,{u}_p\right)\right), \end{array}$$

(13.19)

where ρ ⁱ_1j and ρ ⁱ_2j , $i,j=1,2$, are defined as ρ ₁ and ρ ₂ in (13.17);

for cones ${\mathbb{T}}_1$ and ${\mathbb{T}}_2$

$$ {\varPhi{'}}^{{\mathbb{T}}_1{\mathbb{T}}_2}\left({u}_1,{u}_2,{u}_p\right)= \min \left\{{\rho}_{11}^1\left({u}_1,{u}_p\right),{\psi}_p\left({\widehat{p}}_1\right),{\rho}_{11}^2\left({u}_2,{u}_p\right),{\psi}_p\left({\widehat{p}}_2\right)\right\}, $$

(13.20)

where ${\widehat{p}}_i=\left(-{e}_i \cos {\theta}_{xi} sin{\theta}_{yi},\kern0.24em {e}_i \sin {\theta}_{xi},{e}_i cos{\theta}_{xi} \cos {\theta}_{yi}\right)$, $i=1,2.$

A quasi phi-function ${\varPhi}^{'\kern0.24em {\mathbb{C}}_1{\mathbb{C}}_2}$ for cylinders ℂ ₁ and ℂ ₂ may be defined by formula (13.19).

Using (13.5) and (13.16), we define a quasi phi-function for cuboid ${\mathbb{K}}_1$ and spherocone ${\overset{\frown }{\mathbb{T}}}_2$ in the form

$$ {\varPhi}^{'\kern0.24em {\mathbb{K}}_1{\mathbb{T}}_2}\left({u}_1,{u}_2,{u}_p\right)= min\left\{{\varPhi}^{{\mathbb{K}}_1P}\left({u}_1,{u}_p\right),{\varPhi}^{{\mathbb{T}}_2P*}\left({u}_2,{u}_p\right)\right\}. $$

We refer the reader to papers [33] and [34] for details of construction of the quasi-phi-functions mentioned above.

13.4 A Mathematical Model and a General Solution Strategy

We consider here a packing problem in the following setting. Let a collection of objects ${O}_i\subset {R}^d$, $i\in \left\{1,2,\dots, n\right\}={I}_n,$ $d=2,3$, be given. And let Ω denote a rectangle of length l and width w in two-dimensional case, and a cuboid of length l, width w and height η in three-dimensional case. Each of the sizes of Ω may be variable. We denote an objective function by F.

We assemble a complete set of variables for our optimization problem. We denote: the vector of variable sizes of container Ω by u _Ω ; the vector of placement parameters of object O _i by u _i , $i\in {I}_n$; the vector of all additional variables, taken from quasi-phi-functions (13.5)–(13.20), by τ.

Thus, a vector of all our variables can be described as follows: $u=\left({u}_{\varOmega },{u}_1,{u}_2,\dots, {u}_n,\tau \right)\in {R}^{\sigma }$, where R ^σ denotes the σ-dimensional Euclidean space.

Optimal packing problem. Pack the set of objects O _i , $i\in {I}_n$, into a given container Ω taking into account distance constraints, such that objective function F will reach its minimal value.

A mathematical model of the optimal packing problem may now be stated in the form:

$$ \min F(u),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em u\in W\subset {R}^{\sigma } $$

(13.21)

$$ W=\left\{u\in {R}^{\sigma }:{\overset{\frown }{\varPhi}}_{ij}^{'}\ge 0,i<j\in {I}_n,{\overset{\frown }{\varPhi}}_i^{'}\ge 0,i\in {I}_n\right\}, $$

(13.22)

where ${\overset{\frown }{\varPhi}}_{ij}^{'}$ is an adjusted quasi-phi-function derived for the pair of objects O _i and O _j , taking into account minimal allowable distance ${\rho}_{ij}^{-}$, ${\overset{\frown }{\varPhi}}_i^{'}$ is an adjusted (or normalized) phi-function derived for objects O _i and ${\varOmega}^{*}={R}^d\backslash \operatorname{int}\varOmega$ (to hold the containment constraint), also taking into account minimal allowable distance ${\rho}_i^{-}$. If ${\rho}_{ij}^{-}=0,$ then we replace an adjusted quasi-phi-function ${\overset{\frown }{\varPhi}}_{ij}^{'}$ by a quasi-phi-function Φ ^' _ij for objects O _i and O _j ; as well as an adjusted quasi-phi-function ${\overset{\frown }{\varPhi}}_i^{'}$ – by a quasi-phi-function Φ ^' _i (or a phi-function Φ _i ) for objects O _i and Ω.

Our problem (13.21)–(13.22) is NP-hard, in general, nonlinear programming problem with nonsmooth functions. The feasible region W defined by (13.22) has a complicated structure: it is, in general, a disconnected set, each connected component of W is multiconnected, 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. The feasible region W is specified by a system of nonlinear inequalities with piecewise continuously differentiable functions (quasi-phi-functions or phi-functions), which involve operations of maximum and minimum of smooth functions. This means that the feasible region W can be represented as a finite union of subregions W _s , $s=1,\dots, \eta$. Each subregion W _s is described by a system of inequalities with smooth functions. Now we may reduce the problem (13.21)–(13.22) to the following optimization problem:

$$ F\left({u}^{*}\right)= \min \left\{F\left({u^s}^{*}\right),s=1,\dots, \eta \right\}, $$

where $F\left({u^s}^{*}\right)=\underset{u\in {W}_s}{ \min }F(u)$ is a nonlinear programming problem with smooth functions.

To solve the problem (13.21)–(13.22) we use the strategy, which employs the following optimization procedures:

• 1. Generation of a starting point from the feasible region of the problem (13.21)–(13.22). To this aim we use the starting point algorithm (SPA), based on homothetic transformations of geometric objects.

• 2. Search for a local minimum of the objective function F(u) of problem (13.21)–(13.22) by means of the Local Optimization with Feasible Region Transformation (LOFRT) procedure. The LOFRT procedure considerably reduces the dimension of the optimal packing problem, the number of inequalities in (13.22), as well as, the computational time.

• 3. Non-exhaustive search of local minima to get “good” local optimal solution of the problem (13.21)–(13.22).

Now we consider two practical problems: (1) packing of a set of ellipses into a rectangular container of minimal area; (2) packing of a set of certain 3D-objects into a cuboid container of minimal height. We use quasi-phi-functions defined in Sect. 13.3 for appropriate pairs of rotating objects in model (13.21)–(13.22) and, following the general solution strategy given above, we describe efficient optimization algorithms based on characteristics of our problems.

13.5 Application of Quasi-Phi-Functions for Optimal Packing of Ellipses

In the subsection we follow work [33]. Suppose a set of ellipses E _i , $i\in {I}_n$, is given to be placed in a rectangular container $\varOmega =\left\{\left(x,y\right)\in {R}^2:0\le x\le l,0\le y\le w\right\}$. Each ellipse E _i is defined by its semi-axes a _i and b _i , whose values are fixed. With each ellipse E _i we associate its eigen coordinate system whose origin coincides with the center of the ellipse and the coordinate axes are aligned with the ellipse’s axes. In that system the ellipse is described by parametric equations x = a cos t, y = b sin t, 0 ≤ t ≤ 2π. Continuous ellipse rotations and translation are allowed. In addition, minimal allowable distance ${\rho}_{ij}^{-}$ between two ellipses E _i and E _j , as well as between ellipse E _i and the frontier of container Ω may be given.

Optimal ellipse packing problem. Pack the set of ellipses E _i , $i\in {I}_n$, into a rectangular container Ω of minimal area taking into account distance constraints.

It should be noted that one of the dimensions (l or w) may be fixed.

Our approach, which is based on quasi-phi-functions, is capable of handling precise ellipses (without approximations) and thus finding an exact local optimal solution. The only other method of that sort was developed in [23]. The paper is entirely devoted to the problem of cutting ellipses from a rectangular plate of minimal area. It offers a good overview of related publications. The key idea of[23], just like ours, is to use separating lines to ensure that the ellipses do not overlap with each other. But their implementation of this idea is technically different. For a small number of ellipses they are able to compute a globally optimal solution subject to the finite arithmetic of global solvers at hand. However, for more than 14 ellipses none of the nonlinear programming (NLP) solvers available in GAMS can even compute a locally optimal solution. The authors of [23] develop a heuristic approach, in which the ellipses are added sequentially in a strip of a given width and variable length. The algorithm allows the authors to compute good solutions for up to 100 ellipses.

In order to compare the performance of the two methods, we applied our algorithm to some instances of the ellipse packing problem as used in [23] (see Sect. 13.7.1).

The vector $u=\left({u}_{\varOmega },{u}_1,{u}_2,\dots, {u}_n,\tau \right)$ of all variables in the ellipse packing problem is defined as follows: ${u}_{\varOmega }=\left(l,w\right)$ contains the variable length and width of rectangular container Ω; ${u}_i=\left({x}_i,{y}_i,{\theta}_i\right)$ contains placement parameters of ellipse E _i , $i\in {I}_n$; vector of additional variables τ now is defined as follows: $\tau =\left(t,{u}_P\right)$, if minimal allowable distances are specified and $\tau =(t)$, if there are no distance constraints. Here $t=\left({t}_{{}_1}^1,{t}_{{}_2}^1,\dots, {t}_{{}_1}^m,{t}_{{}_2}^m,{t}_{{}_1}^{'1},{t}_{{}_2}^{'1},\dots, {t}_{{}_1}^{'n},{t}_{{}_2}^{'n}\right)$, where ${t}_{{}_1}^k,{t}_{{}_2}^k$ are additional variables for the kth pair of ellipses, according to (13.9), $k=1,\dots, m$, $m=\frac{\left(n-1\right)n}{2}$, and ${t}_{{}_1}^{'i}$, ${t}_{{}_2}^{'i}$ are additional variables for each ellipse E _i , $i\in {I}_n$, according to (13.12). If minimal allowable distances are specified, we have to use adjusted quasi-phi-functions (13.11) and (13.13), instead of quasi-phi-functions (13.9) and (13.12). In that case ${u}_P=\left({u}_{{}_P}^1,\dots, {u}_{{}_P}^m\right),$ ${u}_{{}_P}^k=\left({\theta}_{{}_P}^k,{\mu}_{{}_P}^k\right)$.

We define the number of the problem variables $\sigma =2+3n+n\left(n-1\right)+2n={n}^2+4n+2$ if there are no distance constraints, and $\sigma =2+3n+2n\left(n-1\right)+2n=2{n}^2+3n+2$ if minimal allowable distances are given.

In mathematical model (13.21)–(13.22) for ellipse packing problem we set: $F(u)=l\cdot w$, ${\overset{\frown }{\varPhi}}_{ij}^{'}$ is an adjusted quasi-phi-function (13.11) defined for the pair of ellipses E _i and E _j , taking into account minimal allowable distance ${\rho}_{ij}^{-}$, ${\overset{\frown }{\varPhi}}_i^{'}$ is an adjusted quasi-phi-function (13.13) defined for the ellipse E _i and the object Ω (to hold the containment constraint), taking into account minimal allowable distance ${\rho}_i^{-}$. If ${\rho}_{ij}^{-}=0$ and ${\rho}_i^{-}=0,$ we replace an adjusted quasi-phi-function ${\overset{\frown }{\varPhi}}_{ij}^{'}$ by a quasi-phi-function Φ ^' _ij defined by (13.9) for each pair of ellipses to enforce the non-overlapping constraint and ${\overset{\frown }{\varPhi}}_i^{'}$ with quasi-function Φ ^' _i defined by (13.12) for each ellipse and the domain Ω to enforce the containment constraint.

Due to the forms of quasi-phi-functions in (13.9)–(13.13), the solution space W is now described by a system of inequalities with smooth functions, therefore problem (13.21)–(13.22) becomes a multiextremal nonlinear programming problem.

We follow here the solution strategy introduced in Sect. 13.4.

It is due to the LOFRT procedure our strategy can process large sets of non-identical ellipses (100 and more, see examples below). The reduction scheme used by our LOFRT algorithm is described below.

13.5.1 Starting Point Algorithm for Optimal Ellipse Packing Problem

In order to find a starting point u ⁰ that belongs to the feasible region W we apply the following algorithm based on homothetic transformation of ellipses. We assume here that homothetic coefficients h _i are variable provided that ${h}_i=h$, for $i=1,2,\dots, n$, and $0\le h\le 1$.

The algorithm consists of the following steps:

• 1. First we choose starting length and width for the container Ω ⁰. They must be sufficiently large to allow for a placement of all our ellipses with required distance constraints within Ω ⁰. For example, we can choose ${l}^0={w}^0=2{\displaystyle \sum_{i=1}^n{a}_i}+\left(n-1\right){\rho}^{-}$, ${\rho}^{-}=\underset{i,j\in {I}_n}{ \max }{\rho}_{ij}^{-}$.

• 2. Then we set $h={h}^0=\delta /\underset{i}{ \max {a}_i}$, where $\delta =0.01\left(\underset{i}{ \min }{b}_i\right)$.

• 3. Then we generate randomly, within Ω ⁰, a set of n non-overlapping equal circles of radius δ with randomly chosen centers $\left({x}_i^0,{y}_i^0\right),i\in {I}_n$.

• 4. Next we generate, randomly, a set of rotation parameters ${\theta}_i^0\in \left[0,2\pi \right)$, $i\in {I}_n$.

• 5. Then we find starting values for the additional variables τ ⁰ by a special optimization procedure that solves auxiliary problems of finding $\underset{u_i^{'}\in {R}^2}{ \max }{\varPhi}_i{'}\left({u}_i^0,{u}_i^{'}\right)$ (or $\underset{u_i^{'}\in {R}^2}{ \max }{\overset{\frown }{\varPhi{'}}}_i\left({u}_i^0,{u}_i^{'}\right)$) and $\underset{u_{ij}^{'}\in {R}^2}{ \max }{\varPhi}_{ij}{'}\left({u}_i^0,{u}_j^0,{u}_{ij}^{'}\right)$ (or $\underset{u_{ij}^{'}\in {R}^4}{ \max }{\overset{\frown }{\varPhi{'}}}_{ij}\left({u}_i^0,{u}_j^0,{u}_{ij}^{'}\right)$) for each quasi-phi-function (or, respectively, an adjusted phi-function) that is involved in (13.22), under fixed parameters ${u}_i=\left({x}_i^0,{y}_i^0,{\theta}_i^0,{\lambda}^0\right)$ for each ellipse.

  To solve the above auxiliary problems we use the following model:

  $$ \max \kappa, \kern0.5em s.t.\;u'\in {W}_{\kappa}^{'}, $$

  where ${W}_{\kappa}^{'}=\left\{\left(u',\kappa \right):{\varPhi}{'}\left({u}^0,{u}^{'}\right)\ge \kappa \right\}$, $\kappa \in {R}^1$ is a new auxiliary variable, function Φ′(u ⁰, u ^′) may take form of Φ ^′ _i (u ⁰ _i , u ^′ _i ) (or ${\overset{\frown }{\varPhi{'}}}_i\left({u}_i^0,{u}_i^{'}\right)$) and Φ ^′ _ij (u ⁰ _i , u ⁰ _j , u ^' _ij ) (or ${\overset{\frown }{\varPhi{'}}}_{ij}\left({u}_i^0,{u}_j^0,{u}_{ij}^{'}\right)$), u ^' is the vector of auxiliary variables and u ⁰ is the vector of fixed parameters for our quasi-phi-functions (respectively, adjusted phi-functions).

  Thus all our quasi-phi-functions (or normalized quasi-phi-functions) at the point ${u}^0=\left({l}^0,{w}^0,{u}_1^0,{u}_2^0,\dots, {u}_n^0,{\tau}^0\right)$ take non-negative values, where ${\tau}^0=\left({t}^0\right)$ (or, respectively, ${\tau}^0=\left({t}^0,{u}_P^0\right)$).

• 6. Now we take the starting point u ⁰ under fixed $l={l}^0$ and $w={w}^0$, and solve the following optimization problem:

  $$ \max h,\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {u}{'}\in {W}^{'}, $$

  (13.23)
  $$\begin{array}{lll} {W}^{\prime}&{=}\left\{{u}{\prime}{\in} {R}^{\sigma {+}1}:{\overset{\frown }{\varPhi}}_{ij}^{\prime}\ge 0,i{<}j{\in} {I}_n,{\overset{\frown }{\varPhi}}_i^{\prime}\ge 0,i{\in} {I}_n,\right.\nonumber\\ & \left.\qquad l{=}{l}^0,w{=}{w}^0,0\le h\le 1{\vphantom{\left\{{u}{\prime}{\in} {R}^{\sigma {+}1}:{\overset{\frown }{\varPhi}}_{ij}^{\prime}\ge 0,i{<}j{\in} {I}_n,{\overset{\frown }{\varPhi}}_i^{\prime}\ge 0,i{\in} {I}_n,\right.}}\right\}, \end{array}$$

  (13.24)

  where ${u}^{' }=\left(u,h\right)$ denotes an extended vector of variables and u denotes the original vector of variables for the problem (13.21)–(13.22).

  We note that if an optimal global solution is found, then $h=1$. The solution automatically respects all the non-overlapping and containment constraints.

  Thus, the point ${u}^{'0}=\left({l}^0,{w}^0,{u}_1^{'0},{u}_2^{'0},\dots, {u}_n^{'0},{\tau}^{'0},1\right)$ of global maximum of the problem (13.23)–(13.24) guarantees that point ${u}^0=({l}^0,{w}^0,{u}_1^{'0},{u}_2^{'0},\dots, {u}_n^{'0},$ belongs to feasible region W of problem (13.21)–(13.22).

  It should be noted that our algorithm by construction always finds the global solution of the problem (13.21)–(13.22). It is clear that the optimal solution of the above problem will automatically comply with all the non-overlapping and containment constraints.

• 7. Lastly, our algorithm returns the vector ${u}^0=\left({l}^0,{w}^0,{u}_1^{'0},{u}_2^{'0},\dots, {u}_n^{'0},{\tau}^{'0}\right)$ as a starting point for a subsequent search for a local minimum of the problem (13.21)–(13.22).

13.5.2 Algorithm of Local Optimization with Feasible Region Transformation in the Optimal Ellipse Packing Problem

Let ${u}^{(0)}\in W$ be one of the starting points found by the previous method. The main idea of the LOFRT algorithm consists in the following.

First we circumscribe a circle C _i of radius a _i around each ellipse E _i , $i=1,2,\dots, n$. Then for each circle C _i we construct an “individual” rectangular container ${\varOmega}_i\supset {C}_i\supset {E}_i$ with equal half-sides of length ${a}_i+\varepsilon$, $i\in {I}_n$, so that C _i , E _i and Ω _i have the same center (x ⁰ _i , y ⁰ _i ) subject to the sides of Ω _i being parallel to those of Ω. Here ε is a predefined fixed constant.

Further we fix the position of each individual container Ω _i and let the local optimization algorithm move the corresponding ellipse E _i only within the container Ω _i . It is clear that if distance between two individual containers Ω _i and Ω _j exceeds ${\rho}_{ij}^{-}$ (i.e. ${\overset{\frown }{\varPhi}}^{\varOmega_i{\varOmega}_j}\ge 0$), then we do not need to check the distance constraint for the corresponding pair of ellipses E _i and E _j .

The above key idea allows us to extract subregions of our feasible region W of the problem (13.21)–(13.22) at each step of our optimization procedure as follows.

We create an inequality system of additional constraints on the translation vector v _i of each ellipse E _i in the form: ${\varPhi}^{C_i{\varOmega}_i^{\ast }}\ge 0$, $i\in {I}_n$, where${\varPhi}^{C_i{\varOmega}_i^{\ast }}= \min \left\{-{x}_i+{x}_i^0+\varepsilon, -{y}_i+{y}_i^0+\varepsilon, {x}_i-{x}_i^0+\varepsilon, {y}_i-{y}_i^0+\varepsilon \right\}$ is the phi-function for the circle C _i and ${\varOmega}_i^{*}={R}^2\backslash \operatorname{int}{\varOmega}_i$.

The inequality ${\varPhi}^{C_i{\varOmega}_i^{\ast }}\ge 0$ is equivalent to the system of four linear inequalities $-{x}_i+{x}_i^0+\varepsilon \ge 0$, $-{y}_i+{y}_i^0+\varepsilon \ge 0$, ${x}_i-{x}_i^0+\varepsilon \ge 0$, ${y}_i-{y}_i^0+\varepsilon \ge 0$.

Then we form a new region defined by

$$ {W}_1=\left\{u\in {R}^{\sigma -{\sigma}_1}:{\overset{\frown }{\varPhi}}_{ij}^{'}\ge 0,\left(i,j\right)\in {\varXi}_1,{\overset{\frown }{\varPhi}}_i^{'}\ge 0,{\varPhi}^{C_i{\varOmega}_i^{\ast }}\ge 0,i\in {I}_n\right\}, $$

where ${\varXi}_1=\left\{\left(i,j\right):{\varPhi}^{\varOmega_i{\varOmega}_j}<0,i<j\in {I}_n\right\}$.

In other words, we delete from the system, which describes W, such quasi-phi-function inequalities for all pairs of ellipses whose individual containers do not overlap and we add additional inequalities ${\varPhi}^{C_i{\varOmega}_i^{\ast }}\ge 0$, which describe the containment of the circles C _i in their individual containers Ω _i , $i\in {I}_n$. Thus, we reduce the number of additional variables by σ ₁. Then our algorithm searches for a point of local minimum ${u}_{w_1}^{*}$ of the subproblem

$$ \min F\left({u}_{w_1}\right)\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {u}_{w_1}\in W\subset {R}^{\sigma -{\sigma}_1}. $$

When the point ${u}_{w_1}^{*}$ is found, it is used to construct a starting point u ⁽¹⁾ for the second iteration of our optimization procedure (note that the σ ₁ previously deleted additional variables τ ₁ have to be redefined by a special procedure used in SPA; see step 5, assuming ${h}^0=1$).

At that iteration we again identify all the pairs of ellipses with non-overlapping individual containers, form the corresponding subregion W ₂ (analogously to W ₁) and let our algorithm search for a local minimum ${u}_{w_2}^{*}\in {W}_2$. The resulting local minimum ${u}_{w_2}^{*}$ is used to construct a starting point u ⁽²⁾ for the third iteration, etc.

We stop our iterative procedure when $F\left({u}_{w_k}^{*}\right)=F\left({u}_{w_{k+1}}^{*}\right)$, where ${u}_{w_k}^{*}$ is a point of local minimum of the problem

$$ \min F\left({u}_{w_k}\right)\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {u}_{w_k}\in W\subset {R}^{\sigma -{\sigma}_k}, $$

where ${W}_k=\left\{u\in {R}^{\sigma -{\sigma}_k}:{\overset{\frown }{\varPhi}}_{ij}^{'}\ge 0,\left(i,j\right)\in {\varXi}_k,{\overset{\frown }{\varPhi}}_i^{'}\ge 0,{{\varPhi}}{}^{{C_i{\varOmega}_{ki}^{\ast }}}\ge 0,i\in {I}_n\right\}$, and ${\varXi}_k=\left\{\left(i,j\right):{\varPhi}^{\varOmega_{ki}{\varOmega}_{kj}}<0,i<j\in {I}_n\right\}$.

We claim that the point ${u}^{*}={u}^{(k)*^{\phantom{\Sigma}}}=\left({u}_{w_k}^{*},{\tau}_k\right)\in {R}^{\sigma }$ is a point of local minimum of the problem (13.21)–(13.22), where ${u}_{w_k}^{*}\in {R}^{\sigma -{\sigma}_k}$ is the last point of our iterative procedure and ${\tau}_k\in {R}^{\sigma_k}$ is a vector of the previously deleted additional variables (the variables can be redefined by the special procedure used in SPA; see step 5). The assertion comes from the fact that any arrangement of each pair of ellipses E _i and E _j subject to $\left(i,j\right)\in \varXi \backslash {\varXi}_k$ guarantees that there always exists a vector τ _k of additional variables such that ${\overset{\frown }{\varPhi}}_{ij}^{'}\ge 0,\left(i,j\right)\in \varXi \backslash {\varXi}_k$ at the point u ^(k) *. Here $\varXi =\left\{\left(i,j\right),i<j\in {I}_n\right\}$. Therefore the values of additional variables of the vector τ _k have no effect on the value of our objective function, i.e. $F\left({u}_{w_k}^{*}\right)=F\left({u}^{(k)*}\right)$. That is why, indeed, we do not need to redefine the deleted additional variables of the vector τ _k at the last step of our algorithm.

So, while there are O(n ²) pairs of ellipses in the container, our algorithm may in most cases only actively controls O(n) pairs of ellipses (this depends on the sizes of ellipses and the value of ε), because for each ellipse only its nearest neighbors have to be monitored. Thus our LOFRT algorithm allows us to reduce the problem (13.21)–(13.22) with O(n ²) inequalities and a O(n ²)-dimensional solution space W to a sequence of subproblems, each with O(n) inequalities and a O(n)-dimensional solution subspace W _k . This reduction is of a paramount importance, since we deal with nonlinear optimization problems.

13.6 An Application of Quasi-Phi-Function for the Optimal Packing of 3D-Objects

In the subsection we follow work [34]. Let ${O}_i\in \Big\{\mathrm{\mathbb{P}},\mathbb{S},\widehat{\mathbb{T}},\mathbb{T},\mathrm{\mathbb{C}},\mathbb{D},\overset{\frown }{\mathrm{\mathbb{C}}},\overset{\frown }{\mathbb{T}},\mathbb{E}\Big\}$, $i\in I=\left\{1,2,\dots, n\right\}$ be a collection of 3D-objects, where $I={\displaystyle \underset{j=1}{\overset{9}{\cup }}{I}_j}$, ℙ _i is a cuboid, $i\in {I}_1=\left\{1,2,\dots, {k}_1={n}_1\right\}$; ${\mathbb{S}}_i$ is a sphere, $i\in {I}_2;$ $\widehat{\mathbb{T}}$ is a cone, $i\in {I}_3;$ ${\mathbb{T}}_i$ is a truncated cone, $i\in {I}_4;$ ℂ _i is a straight circular cylinder, $i\in {I}_5;$ ${\mathbb{D}}_i$ is a spherical segment, $i\in {I}_6;$ ${\overset{\frown }{\mathrm{\mathbb{C}}}}_i$ is a spherocylinder $i\in {I}_7;$ ${\overset{\frown }{\mathbb{T}}}_i$ is a spherocone, $i\in {I}_8,$ ${\mathbb{E}}_i$ is a spherical disk, $i\in {I}_9$, where ${I}_j=\left\{{k}_{j-1}+1,{k}_{j-1}+2,\ldots,n={k}_{j-1}+{n}_j\right\}$ for $j=2,\dots, 9$.

And let $\varOmega =\left\{\left(x,y,z\right)\in {R}^3:0\le x\le w,0\le y\le l,{\eta}_1\le z\le {\eta}_2\right\}$ be a container of height $\eta ={\eta}_2-{\eta}_1$. We denote container Ω of variable height η by Ω(η).

Optimal 3D-object packing problem. Pack the given set of 3D-objects into container Ω of the minimal height.

We use mathematical model (13.21)–(13.22). Now the components of vector ${u=\left({u}_{\varOmega },q,\tau \right)\in {R}^{\sigma }}$ for the optimal 3D-object packing problem take the form: ${u}_{\varOmega }=\eta =\left({\eta}_1,{\eta}_2\right)\in {R}^2$; $q=\left({u}_1,\ldots,{u}_n\right)\in {R}^m$, $m=6{n}_1+3{n}_2+5\overset{9}{{\displaystyle \sum}_{j=3}}{n}_j$; $\tau ={u}_p=\left({u}_{p_{12}},{u}_{p_{13}},\dots, {u}_{p_{1n}},\dots, {u}_{p_{\left(n-1\right)n}}\right)$, where ${u}_{p_{ij}}\in {R}^3$, ${u}_p\in {R}^{\frac{3n\left(n-1\right)}{2}}$. The number of the problem variables is defined as $\sigma =2+m+\frac{3n\left(n-1\right)}{2}$. We set the objective function: $F\left(\eta \right)={\eta}_2-{\eta}_1$ in problem (13.21)–(13.22). To define the feasible region W we use: quasi-phi-functions derived in Sect. 13.3 (see formulas (13.5), (13.7), (13.14)–(13.20)) for non-overlapping constraints and phi-functions derived in [34] for containment constraints. To solve the problem we follow the general solution strategy introduced in Sect. 13.4.

13.6.1 Starting Point Algorithm for the Optimal 3D-Object Packing Problem

In order to find a starting point u ⁰ that belongs to the feasible region W we apply the following algorithm based on homothetic transformations of 3D-objects.

The algorithm consists of the following steps:

• 1. We cover each object O _i by sphere ${\mathbb{S}}_i$ of minimal radius ℜ ⁰ _i , assuming that local coordinate systems of O _i and ${\mathbb{S}}_i$ coincide, $i\in I$. Then we assume that ℜ _i , $i\in I$, are variable and form a vector $\Re =\left({\Re}_1,{\Re}_2,\dots, {\Re}_n\right)$.

• 2. Values of components of vector ${\eta}^0=\left({\eta}_1^0,{\eta}_2^0\right)$ are chosen such that ${O}_i\subset \varOmega \left({\eta}^0\right)$ for $i\in I$. We suppose that η ⁰₁ , η ⁰₂ are constants.

• 3. We take ${\Re}_i=0,$ $i\in I,$ and generate randomly a vector $v=\left({v}_1,\dots, {v}_n\right)$, so that ${v}_i\in \varOmega \left({\eta}^0\right)$, $i\in I$. As a result we form a point ${X}^{\diamond }=\left(v,\Re \right)=\left(v,0\right)$.

• 4. Taken a starting point ${X}^{\diamond }$ we solve the problem

  $$ {\kappa}_1\left(\widehat{\Re}\right)= max{\kappa}_1\left(\Re \right),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em X=\left(v,\Re \right)\in {W}_1\subset {R}^{4n}, $$

  (13.25)
  $$ \begin{array}{l}{W}_1=\Big\{X\in {R}^{4n}:{\varPhi}_{ij}\left({v}_i,{v}_j,{\Re}_i,{\Re}_j\right)\ge 0,i<j\in I,{\varPhi}_i\left({v}_i,{\Re}_i\right)\ge 0,\\ {}{\varphi}_i\left({\Re}_i\right)={\Re}_i^0-{\Re}_i\ge 0,{\Re}_i\ge 0,i\in I\Big\},\end{array} $$

  (13.26)

  where ${\kappa}_1\left(\Re \right)={\displaystyle \sum_{i=1}^n{\Re}_i}$, Φ _ij (v _i , v _j , ℜ _i , ℜ _j ) is a phi-function of ${\mathbb{S}}_i$ and ${\mathbb{S}}_j$, Φ _i (v _i , ℜ _i ) is a phi-function of ${\mathbb{S}}_i$ and Ω. We denote a local minimum point of problem (13.25)–(13.26) by $\widehat{X}=\left(\widehat{v},\widehat{\Re}\right)$.

• 5. To construct starting point ${u}^{\bullet}\in W$ for problem (13.21)–(13.22): we assume ${v}^{\bullet }=\widehat{v}$; generate ${\theta}_{x_i}^{\bullet },{\theta}_{y_i}^{\bullet },{\theta}_{z_i}^{\bullet}\in \left[0,2\pi \right]$, $i\in I$, randomly; define vector u ^• _p . In order to derive components ${u}_{p_{ij}}^{\bullet }$ of vector u ^• _p we construct separating planes for each pair of spheres S _i (v ^• _i ) and S _j (v ^• _j ), $i<j\in I$.

• 6. If ${\kappa}_1\left(\widehat{\Re}\right)=\overset{n}{{\displaystyle \sum}_{i=1}}{\Re}_i^0,$ then point ${u}^{\bullet }=\left({\eta}^0,{q}^{\bullet },{u}_p^{\bullet}\right)\in W$ is taken as a starting point. If ${\kappa}_1\left(\widehat{\Re}\right)<\overset{n}{{\displaystyle \sum}_{i=1}}{\Re}_i^0,$ then we use the following optimization procedure to define a starting point ${u}^{\bullet}\in W$.

  Assuming that each object O _i undergo the homothetic transformations with variable homothetic coefficient h _i , $i\in I$, we solve the problem

  $$ {\kappa}_2\left({h}^{*}\right)= max{\kappa}_2(h),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {u}^{' }=\left(u,h\right)\in {W}_2\subset {R}^{\sigma +n-2}, $$

  (13.27)
  $$\begin{array}{lll}{W}_2 & =\left\{{u}{\prime}\in {R}^{\sigma +n-2}:\kern0.5em {\varPhi}_{ij}{\prime}\left({u}_i,{u}_j,{u}_{p_{ij}},{h}_i,{h}_j\right)\ge 0,i<j\in I,{\varPhi}_i\left({u}_i,{h}_i\right)\ge 0,\right.\\ &\qquad\left.{\varphi}_i\left({h}_i\right)=1-{h}_i\ge 0,{h}_i\ge 0,i\in I\right\},\end{array}$$

  (13.28)

  where ${\kappa}_2(h)=\overset{n}{{\displaystyle \sum}_{i=1}}{\rho}_i{h}_i,$ ρ _i is a sum of metric characteristics (sizes) of O _i , $i\in I$, $h=\left({h}_1,{h}_2,\ldots,{h}_n\right)\in {R}^n$. We denote a local maximum point of problem (13.27)–(13.28) by ${u{'}}^{*}=\left({u}^{*},{h}^{*}\right)$ and take point ${u}^{\bullet }=\left({\eta}^0,{q}^{*},{u}_p^{*}\right)\in W$ as a starting point for problem (13.21)–(13.22).

13.6.2 Algorithm of Local Optimization with Feasible Region Transformation in the Optimal 3D-Object Packing Problem

Local optimization. Taking a starting point ${u}^{\bullet}\in W$, we can extract from the system of phi-inequalities in (13.22) a system of inequalities, describing a nonempty subregion of feasible region W of problem (13.21)–(13.22) and search for a local minimum of the problem. However in this case we deal with a huge number of inequalities in the system. We propose here the algorithm, which reduces the problem (13.21)–(13.22) to a sequence of nonlinear programming subproblems of smaller dimensions. The solution space of each subproblem is specified by the incomparably smaller number of inequalities. This allows us to decrease essentially the computational time. Our algorithm is based on two related ideas: constructing of subregions of feasible region W and decreasing of the number of inequalities, specifying the subregions. The first idea is described in, e.g., [31] and the second idea is introduced in Sect. 13.5 for the optimal ellipse packing problem.

Transition from a local minimum point to another one. Let ${u}^{0\ast }$ be a local minimum point of problem (13.21)–(13.22). In order to obtain next local minimum point ${u}^{1\ast}\ne {u}^{0\ast }$ of problem (13.21)–(13.22) we may generate a new starting point ${u}^{\bullet}\in W$ for problem (13.21)–(13.22) (see Sect. 13.6.1) and solve the problem using the local optimization algorithm mentioned above.

The other way is to apply a special algorithm to transit from the local minimum point ${u}^{0\ast }$ to a local minimum point ${u}^{1\ast }$ so that $F\left({\eta}^{1\ast}\right)<F\left({\eta}^{0\ast}\right).$ Let us consider the algorithm.

We solve the following problem:

$$ F\left({\eta}^{*}\right)= \min F\left(\eta \right),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {u}^{{''}}\in {W}_3\subset {R}^{\sigma +n}, $$

(13.29)

$$ \begin{array}{l}{W}_3=\Big\{{u}^{{''}}\in {R}^{\sigma +n}:{\varPhi}_{ij}^{'}\left({u}_i,{u}_j,{u}_{p_{ij}},{h}_i,{h}_j\right)\ge 0,i<j\in I,\\ {}\kern2em {\varPhi}_i\left({u}_i,\eta, {h}_i\right)\ge 0,{h}_i\ge 0,i\in I,\overset{n}{{\displaystyle \sum}_{i=1}}{V}_i{h}_i^3-\overset{n}{{\displaystyle \sum}_{i=1}}{V}_i\ge 0\Big\},\end{array} $$

(13.30)

where V _i is a volume of ${O}_i,i\in I.$ Here components of vector η are variable.

Then we assume that ${h}_i^0=1,$ $i\in I.$ Let ${u}^{0\ast }$ be a local minimum point of problem (13.21)–(13.22). We form a point ${u^{{''}}}^{0*}=\left({u}^{0*},1\right)$ and compute the steepest descent vector Z ⁰ at the point ${u^{{''}}}^{0\ast }$ for problem (13.29)–(13.30), using the iterative procedure

$$ {u^{{''}}}^k={u^{{''}}}^{0\ast }+{0.5}^{k-1}{Z}^0,\kern0.5em k\in M=\left\{1,2,\dots \right\}. $$

If ${h}_i^k>1,$ $i\in {J}_1\subset I$, then the appropriate object is expanded and, therefore, a free space around the true object occurs; if ${h}_i^k<1,$ $i\in {J}_2$, the appropriate object is shrunk.

It is evident that $F\left({\eta}^k\right)<F\left({\eta}^{0\ast}\right)$ for any $k\in M$ and, in the general case, ${u^{{''}}}^k\notin {W}_3.$ This allows us to define m such that: if $k\ge m$, then ${u^{{''}}}^k\in {W}_3.$

Assuming $k=m$, we take point u ^″m and define point ${u{'}}^m=\left({u}^m,{h}^{0m}\right)$, where ${h}^{0m}=\left({h}_1^{0m},{h}_2^{0m},\ldots,{h}_n^{0m}\right)$ and ${h}_i^{0m}=1,$ if $i\in I\backslash {J}_2,$ ${h}_i^{0m}={h}_i^m,$ if $i\in {J}_2.$ Whence, $\overset{n}{{\displaystyle \sum}_{i=1}}{V}_i{\left({h}_i^{0m}\right)}^3-\overset{n}{{\displaystyle \sum}_{i=1}}{V}_i<0$ if ${J}_2\ne \left\{\varnothing \right\}.$ Let $\eta ={\eta}^m,$ i.e. $F\left({\eta}^m\right)<F\left({\eta}^{0\ast}\right).$ Then we try to “change over” objects of collections $\Big\{{O}_i\left({u}_i^m,{h}_i^{0m}\right),$ $i\in {J}_1\Big\}$, and $\Big\{{O}_i\left({u}_i^m,{h}_i^{0m}\right)$, $i\in {J}_2\Big\}$, so that the value of κ ₂(h) in (13.27)–(13.28) increases with respect to point u′^m.

For the sake of simplicity, we assume that each object O _i is covered by a circular cylinder ${\mathrm{\mathbb{C}}}_i\supseteq {O}_i,$ $i\in I.$ Taking point u′^m, we generate a point ${\tilde{u}}^{' }$ as follows.

First we form index subsets ${J}_{11}\subset {J}_1$ and ${J}_{22}\subset {J}_2$ for which

$$ {r}_j^0{h}_j^m<{r}_i^0{h}_i^m,{e}_j^0{h}_j^m<{e}_i^0{h}_i^m,{r}_i^0\le {r}_j^0{h}_j^m,{e}_i^0\le {e}_j^0{h}_j^m,\;i\in {J}_1,\;j\in {J}_2. $$

(13.31)

Then we set ${\tilde{h}}_i=1,$ ${\tilde{u}}_i={u}_j^m,$ ${\tilde{u}}_j={u}_i^m,$ ${\tilde{h}}_j= \min \left\{{h}_j^m+{\varepsilon}_j,1\right\},$ ${\varepsilon}_j= \min \left\{{\varepsilon}_{1j},{\varepsilon}_{2j}\right\},$ ${\varepsilon}_{1j}=\frac{r_i^0{h}_i^m}{r_j^0}-{h}_j^m,$ ${\varepsilon}_{2j}=\frac{e_i^0{h}_i^m}{e_j^0}-{h}_j^m$.

In order to find the values of components of vector ${\tilde{u}}_p=\left({\tilde{u}}_{p_{12}},{\tilde{u}}_{p_{13}},\ldots,{\tilde{u}}_{p_{1n}},\ldots,\right.$ we solve the following problems:

$$ \max {\Phi}_{il}^{'}\left({u}_i,{u}_l,{\tilde{u}}_{p_{it}},{h}_i,{h}_l\right),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {\tilde{u}}_{p_{it}}\in {R}^3\kern0.5em \mathrm{f}\mathrm{o}\mathrm{r}\kern0.5em i\in {J}_{11},l\in I, $$

$$ \max {\Phi}_{jk}^{'}\left({u}_j,{u}_k,{\tilde{u}}_{p_{jk}},{h}_j,{h}_k\right),\kern0.5em \mathrm{s}.\mathrm{t}.\kern0.5em {\tilde{u}}_{p_{jk}}\in {R}^3\kern0.5em \mathrm{f}\mathrm{o}\mathrm{r}\kern0.5em i\in {J}_{22},k\in I. $$

If at least one of inequalities (13.31) is not fulfilled for $i\in {J}_1$ or $j\in {J}_2,$ then we set ${\tilde{h}}_i={h}_i^{0m},{\tilde{u}}_i={u}_i^{0m},{\tilde{h}}_j={h}_j^{0m},{\tilde{u}}_j={u}_j^{0m},{\tilde{u}}_{p_{ij}}={u}_{p_{ij}}^{0m}.$ Note that if ${\tilde{u}}{'}\ne {u{'}}^m$ then points ${\tilde{u}}^{' }$ and u′^m are in attraction zones of different local maximum points. We prove in [31] that: if ${\tilde{u}}{'}\ne {u{'}}^m$ then ${\kappa}_2\left(\tilde{h}\right)>{\kappa}_2\left({h}^{0m}\right).$

Starting from point ${\tilde{u}}{'}\in {W}_2$ we can obtain a new local maximum point ${{\tilde{u}}{'}}^{*}$ of problem (13.27)–(13.28) such that ${\kappa}_2\left({\tilde{h}}^{*}\right)>{\kappa}_2\left(\tilde{h}\right).$ If ${\kappa}_2\left({\tilde{h}}^{*}\right)=n,$ then ${\tilde{u}}^{*}=\left({\eta}^m,{\tilde{q}}^{*},{\tilde{u}}_p^{*}\right)\in W$ and $F\left({\eta}^m\right)<F\left({\eta}^{0\ast}\right).$ Since point ũ may not be a local minimum point of problem (13.21)–(13.22), we take the point as a starting point to solve problem (13.21)–(13.22). Then we obtain a local minimum point ${u}^{1\ast }$. Evidently, $F\left({\eta}^{1\ast}\right)\le F\left({\eta}^m\right)<F\left({\eta}^{0\ast}\right).$ The approach is described in detail in [31] for optimal packing problem of non-oriented parallelepipeds and spheres.

13.7 Computational Results

Here we present a number of examples to demonstrate the high efficiency of our methodology. We have run our experiments on an AMD Athlon 64 X2 5200+ computer. For local optimization we used the IPOPT code (https://projects.coin-or.org/Ipopt) developed by [36].

13.7.1 Examples for the Optimal Ellipse Packing Problem

First we give a new benchmark instances. We set the computational time limit for each example to search for at least 10 local minima. For our computational experiments we take $\varepsilon ={\displaystyle \sum_{i=1}^n{b}_i}/n$.

Example 1

n = 28, {$\left({a}_i,{b}_i\right)=\left(2.2,1.80\right)$, $i=1,\dots, 7$}, {$\left({a}_i,{b}_i\right)=\left(2.60,1.70\right)$, $i=8,\dots, 14$}, {$\left({a}_i,{b}_i\right)=\left(3.5,0.7\right)$, $i=15,\dots, 21$}, {$\left({a}_i,{b}_i\right)=\left(3.6,2.7\right)$, $i=22,\dots, 28$}. Figure 13.1a shows the packing of ellipses into a rectangular container, which corresponds to the local minimum point u. Container has sizes $\left({l}^{*},{w}^{*}\right)=\left(22.273763,24.126932\right)$ and area $F\left({u}^{*}\right)=$ 537.397581.

Fig. 13.1

Local optimal packing of ellipses in Example 1: (a) no distance constraints, (b) with distance constraints

Figure 13.1b shows the packing of ellipses into a rectangular container taking into account minimal allowable distance (${\rho}^{-}=0.5$ between each pair of ellipses), which corresponds to the local minimum point u. Container has sizes $\left({l}^{*},{w}^{*}\right)=\left(25.984532,25.024524\right)$ and area $F\left({u}^{*}\right)=$ 650.250548. The computational time limit is 1 h.

Example 2

n = 36, {$\left({a}_i,{b}_i\right)=\left(2.2,1.80\right)$, $i=1,\dots, 9$}, {$\left({a}_i,{b}_i\right)=\left(2.60,1.70\right)$, $i=10,\dots, 18$}, {$\left({a}_i,{b}_i\right)=\left(3.5,0.7\right)$, $i=19,\dots, 27$}, {$\left({a}_i,{b}_i\right)=\left(3.6,2.7\right)$, $i=28,\dots, 36$}. Figure 13.2a shows the placing of ellipses into a rectangular container, which corresponds to the local minimum point u. Container has sizes $\left({l}^{*},{w}^{*}\right)=\left(25.176786,27.380105\right)$ and area $F\left({u}^{*}\right)=$ 689.343044.

Fig. 13.2

Local optimal placement of ellipses in Example 2: (a) no distance constraints, (b) with distance constraints

Figure 13.2b shows the placing of ellipses into a rectangular container taking into account minimal allowable distance (${\rho}^{-}=0.5$ between each pair of ellipses), which corresponds to the local minimum point u. Container has sizes $\left({l}^{*},{w}^{*}\right)=\left(27.498755,30.282542\right)$ and area $F\left({u}^{*}\right)=$ 832.732196.

Further we give a couple of examples with our records to place a large number of ellipses. Time limit for these large example was set to 48 h.

Example 3

n = 140, $\Big\{\left({a}_i,{b}_i\right)=\left(222,\ 180\right)$, $i=1,\dots, 50$}, $\Big\{\left({a}_i,{b}_i\right)=\left(260,\ 170\right)$, $i=51,\dots, 90\Big\}$, $\Big\{\left({a}_i,{b}_i\right)=\left(350,\ 70\right)$, $i=91,\dots, 120\Big\}$, $\Big\{\left({a}_i,{b}_i\right)=\left(360,\ 270\right)$, $i=121,\dots, 140\Big\}$.

The local optimal ellipse packing is shown in Fig. 13.3, the container has sizes $\left({l}^{*},{w}^{*}\right)=\left(4854.0329,4970.3722\right)$ and area $F\left({u}^{*}\right)=$ 24126350.3955.

Fig. 13.3

Local optimal packing of ellipses in Example 3

Example 4

n = 150, {(a _i , b _i ), $i=1,\dots, 6=\left(2,1.5,1.5,1,1,0.8,0.9,0.75,0.8,\right.$}, {$\left({a}_i,{b}_i\right)=\left(1,\ 0.8\right)$, $i=7,\dots, 50$}, {(a _i , b _i ), $i=51,\dots, 56=\left(2,1.5,1.5,1,1,0.8,0.9,0.75,0.8,0.6,0.7,0.3\right)$}, {$\left({a}_i,{b}_i\right)=\left(1,\ 0.8\right)$, $i=57,\dots, 100$}, {(a _i , b _i ), $i=101,\dots, 106=\left(2,1.5,1.5,1,1,0.8,0.9,0.75,\right.$}, {$\left({a}_i,{b}_i\right)=\left(1,\ 0.8\right)$, $i=107,\dots, 150$}.

The local optimal packing is shown in Fig. 13.4, the container has sizes $\left({l}^{*},{w}^{*}\right)=\left(19.865110,22.839405\right)$ and area $F\left({u}^{*}\right)=453.70729$. Time limit is 48 h.

Fig. 13.4

Local optimal packing of ellipses in Example 4

We applied our method to some instances used in paper [23] and compare our local optimal solutions to theirs. Table 13.1 lists the examples. For each example the minimal area of the container found by our method happens to be smaller than the best solution reported in [23]. The improvement is not so big (1–2 %) for smaller sets of ellipses, but it becomes significant (8–9 %) for larger sets of ellipses. It should be noted that for examples TC02, TC03, and TC04 presented in [23] our method found the same optimal results.

Table 13.1 Comparison of our results to those in [23]

We set the computational time for the group of instances: up to 20 objects—time limit 2 h, up to 50—time limit 5 h, 100 objects—time limit 12 h.

Our ellipse packing instances are available at https://app.box.com/s/mo7xjvjve7v52p9movfi.

13.7.2 Examples for the Optimal 3D-Object Packing Problem

Example 5

$n=10,w=70\kern0.5em \mathrm{and}\kern0.5em l=70$. Types and sizes of 3D-objects are presented in Table 13.2.

Table 13.2 Types and sizes of 3D-objects

Figure 13.5 showsNote that ``Figs. 13.6, 13.7, and 13.8'' have been changed to ``Figs. 13.5, 13.6, and 13.7'' in captions and citations. Please check. a local optimal packing of 3D-objects.

Fig. 13.5

Packing of 3D-objects in Example 5

Placement parameters of objects are given in Table 13.3. Container has height $F\left({\eta}^{\ast}\right)=26,192$.

Table 13.3 Placement parameters of 3D-objects in Example 5

Below we give new nine benchmark instances: packings of 3D-objects (from 10 to 200). The input and output data for the instances are available at http://www.datafilehost.com/d/55384293.

Figure 13.6 illustrates The decimal comma has been changed to a decimal point in Tables 13.2 and 13.3. Please check, and correct if necessary. local optimal packings of 3D-objects into a cuboid container of minimal height.

Fig. 13.6

Local optimal 3D-packings: new nine instances (a–i)

The number and types of the objects are given in Table 13.4.

Table 13.4 The number and types of 3D-objects

Figure 13.7 demonstrates a diagram of the dependence of the computational time on the number of objects to be packed.

Fig. 13.7

Dependence of the computational time on the number of objects

13.8 Conclusions

In this chapter we introduce new functions, quasi-phi-functions, which we use for analytical description of non-overlapping, containment, and distance constraints. We employ the function for extended class of 2D- and 3D-objects, involving new shapes of objects, such as ellipses, spherocones, and spherocylinders for whichphi-functions could not be constructed. In addition, these functions (in common with phi-functions) take into account continuous translations and rotations of objects as well as variable sizes of objects. Our quasi-phi-functions are defined by simple enough formulas, which allow us to use nonlinear programming. We propose also fast algorithms to construct feasible starting points based on object homothetic transformations, as well as efficient optimization procedures to search for local extrema in optimal packing problems. We apply our quasi-phi-functions and the algorithms to 2D- and 3D-packing problems and demonstrate the high efficiency of our methodology.