A New Class of Irregular Packing Problems Reducible to Sphere Packing in Arbitrary Norms

Abstract

Packing irregular objects composed by generalized spheres is considered. A generalized sphere is defined by an arbitrary norm. For three classes of packing problems, balance, homothetic and sparse packing, the corresponding new (generalized) models are formulated. Non-overlapping and containment conditions for irregular objects composed by generalized spheres are presented. It is demonstrated that these formulations can be stated for any norm. Different geometrical shapes can be treated in the same way by simply selecting a suitable norm. The approach is applied to generalized spheres defined by Lp norms and their compositions. Numerical solutions of small problem instances obtained by the global solver BARON are provided for two-dimensional objects composed by spheres defined in Lp norms to demonstrate the potential of the approach for a wide range of engineering optimization problems.

1. Introduction

Packing problems consist in arranging several geometrical objects in a larger object referred to as a container. The objects must be allocated subject to placement conditions, i.e., without mutual overlapping (non-overlapping condition) and all objects completely inside the container (containment condition). A certain criterion must be optimized, e.g., maximizing the number of objects allocated in a given container or minimizing the container’s metrical characteristics for given objects [1,2].

One of the most frequently studied placement problems is packing spherical objects, where a sphere is defined as the set of points whose distance from a center is bounded by a positive radius.

The non-overlapping condition for spheres simply states that the distance between each pair of the centers must be at least the sum of their radii. Correspondingly, the containment condition ensures for any sphere that the distance between the center of the sphere and the boundary of the container is larger than or equal to the sphere’s radius. Applications range from planning radio-surgical treatment of tumors [3,4] to studying structure of nanomaterials [5,6,7]; from spherical packing in coding theory [8,9] to modeling power bed fusion in additive manufacturing [10,11]. See also [12,13,14,15,16,17] and the references therein.

Packing spherical-like shapes having a certain symmetry can be found, e.g., in biology [18,19] and material sciences [20]. Super-ellipsoids are widely used to represent various forms of particles in granular and soft matter issues, see, e.g., [21,22]. Corresponding packing problems typically are solved by numerical simulation using discrete element methods [23].

Packing irregular objects (nesting) is one of the most challenging problems in packing issues. Special geometric tools are used for modeling irregular packing problems, such as raster point, direct trigonometry, no-fit polygon and phi-functions, to mention a few [24,25,26,27,28]. Irregular n-dimensional ($n\ge 4$) packing problems arising in multi-resource project management can be found in [29]. Packing objects presented by unions of spheres form an important class of irregular packing problems arising in studying multicomponent structures, e.g., in medicine and nanotechnology, see [30,31] and the references therein. A closely related problem is covering objects by spheres. This way, complex shapes can be represented approximately by a union of simple basic objects [32,33].

In most publications on sphere packing, spheres are defined by the Euclidean norm. However, many applied and theoretical packing problems, e.g., producing square, hexagonal or dodecagonal CMS sensors [34] or tiling non-overlapping distinct squares in a square container [35], can be considered as sphere packing for spheres defined in a suitable norm. To the best of our knowledge, using non-Euclidean norms to define distances in sphere packing problems was first proposed in [36,37,38]. Packing circular-like objects (circles, ellipses, regular polygons) defined by different norms was considered for containers approximated by a finite grid.

Irregular packing problems typically require special sophisticated modeling approaches and techniques to represent placement (non-overlapping, containment) conditions (see, e.g., [24] and the references therein). However, in many applications, the shapes involved are not spherical and possess similar properties, e.g., have certain levels of central symmetry [34,35]. Our objective in this paper is to describe and investigate a class of irregular packing problems where placement conditions can be stated as simple, as in sphere packing.

A new class of irregular packing problems referred to as Packing Objects Composed by Generalized Spheres (PCGS) is introduced. It is demonstrated that various geometrical shapes for objects/containers can be generated by simply choosing suitable norms, while maintaining the simplicity of presenting placement conditions. Some classical formulations are revisited, such as balance and/or sparse packing in a minimal spherical container, finding the maximal number of spheres placed in a spherical container, and packing irregular objects represented by unions of spheres. It is demonstrated that these formulations are norm-independent, i.e., can be stated for any norm used. Thus, different geometrical shapes can be treated in the same way by simply selecting a suitable norm.

The main contributions of this paper are

• The problem of Packing Objects Composed by Generalized Spheres (PCGS) is formulated for objects and containers represented by spheres in arbitrary norms.
• Non-overlapping and containment conditions considering allowable distances for irregular objects composed by generalized spheres are introduced. By means of a new composition condition, rotations and reflections of the irregular objects are enabled.
• The generalized balance, homothetic and sparse packing problems for objects composed by the generalized spheres are stated for various norms.

The rest of the paper is organized as follows. Section 2 presents basic definitions and introduces the PCGS problem. Section 3 considers generalized balance, homothetic and sparse packing problems for various Lp and composite norms. Numerical experiments for spheres defined by various norms are presented in Section 4. Some final remarks are provided in Section 5.

2. Mathematical Modeling

In this section a continuous optimization model for the PCGS problem is introduced based on an arbitrary norm $\parallel \cdot \parallel :{ℝ}^n\to [0,\infty ]$. It provides a unifying framework for various packing problems.

2.1. The Main Definitions

Let the set of generalized spheres, each with a fixed radius $r_i>0$ and a variable center ${\xi }_i\in {ℝ}^n$ be defined as follows:

$$S_i({\xi }_i):=\{x\in {ℝ}^n|\Vert x-{\xi }_i\Vert \le r_i\},i\in I:=\{1,\dots ,m\}.$$

The term generalized spheres is used to highlight that by choosing suitable norms, a spectrum of spatial shapes can be generated in ${ℝ}^n$. A family of the composed objects $\{A_k\subset {ℝ}^n|k\in J\}$, $J:=\{1,\dots ,K\}$ is defined as follows. Each object $A_k$ is a union of spheres $S_i({\xi }_i)$ ($i\in I_k$) $I_k\subset I$ such that

$$\begin{array}{l}•\hspace{1em}{I}_1,\dots ,I_K\mathrm{is}\mathrm{a}\mathrm{partition}\mathrm{of}I, \text{i.e.},I_{k_1}\cap I_{k_2}=\varnothing \mathrm{for}\mathrm{all}(k_1,k_2)\in J\times J\mathrm{with}{k}_1\ne k_2\mathrm{and}{\displaystyle \underset{k\in J}{\cup }}{I}_k=I;\\ •\hspace{1em}{A}_k={\displaystyle \underset{i\in I_k}{\cup }}{S}_i({\xi }_i);\\ •\hspace{1em}\Vert {\xi }_i-{\xi }_j\Vert =a_{ij}\mathrm{for}\mathrm{all}(i,j)\in {\Im }_k:=\{(i,j)\in I_k\times I_k|i<j\}\mathrm{for}k\in J,\end{array}$$

(1)

where $a_{ij}$ are given nonnegative numbers. Each set ${\Im }_k$ contains indices of all pairs of spheres from the composed object $A_k$.

The last condition (1) ensures that all pairwise distances between centers of the spheres remain constant under all changes of the coordinates of the centers. This condition guarantees shape preservation for the composed object under translation and rotation, and is referred to as the composition condition. Irregular objects composed by five generalized spheres defined in Lp norms ($p=1$, $p=2$, $p=\infty$) are illustrated in Figure 1.

Packing Objects Composed by Generalized Spheres (PCGS) aims to pack a family of objects $A_k, k\in J$ composed by spheres $S_i({\xi }_i)$, $i\in I_k$ in a larger sphere $S_0=\{x\in {ℝ}^n|\parallel x-{\xi }_0\parallel \le R\}$ (referred to as a container) to optimize a certain objective subject to appropriate placement conditions.

The following basic placement conditions are used in the PCGS problem:

(a)

a containment condition ensures that all composed objects are completely in the container,

(b)

a non-overlapping condition states that there is no overlapping between any pair of the composed objects.

To formulate conditions (a,b) the following notations are used. Let be a collection of all pairs $(k,l)$ of objects with $k<l$. Note that a pair of spheres in a single object $A_k$ may overlap, depending on the given values of $a_{ij}$ for $(i,j)\in {\Im }_k$ and $r_i$ for $i\in I_k$. The following set, denoted by $\mathfrak{K}$, will be used to state the pairwise non-overlapping for the composed objects:

$$\mathfrak{K}:=\{(k,l)\in J\times J|k<l\}.$$

Correspondingly, the containment and non-overlapping conditions can be written in the form

$$\parallel {\xi }_i-{\xi }_0\parallel \le R-r_i,\forall i\in I,$$

(2)

$$\parallel {\xi }_i-{\xi }_j\parallel \ge r_i+r_j,\forall (i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}.$$

(3)

Constraint (2) states that each sphere $S_i({\xi }_i)(i\in I)$ lies completely in the container $S_0$. Constraint (3) guarantees that any two spheres from different composed objects do not overlap. More specifically, the interiors of these two spheres do not intersect, while they may touch each other.

The basic placement conditions can be modified to represent specific packing situations.

The distance condition for containment states that if the distance between the object $A_k$ $(k\in J)$ and the boundary of the container $S_0$ is at least ${\rho }_k\ge 0$, i.e.,

$$\parallel {\xi }_i-{\xi }_0\parallel \le R-r_i+{\rho }_k\forall i\in I_k,k\in J.$$

(4)

If ${\rho }_k=0$ for all $k\in J$, then (4) coincides with the containment constraint (2).

The distance condition for non-overlapping ensures that the distance between two objects $A_k$ and $A_l$ is at least ${\rho }_{kl}\ge 0$, i.e.,

$$\parallel {\xi }_i-{\xi }_j\parallel \ge r_i+r_j+{\rho }_{kl}\forall (i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}.$$

(5)

If all these ${\rho }_{kl}$ vanish, then (5) coincides with the non-overlapping condition (3).

A general mathematical model of the PCGS problem can now be presented as

$$\underset{(\xi ,\tau )}{\min }F(\xi ,\tau )\mathrm{subject}\mathrm{to}(\xi ,\tau )\in G,$$

(6)

where $\xi =({\xi }_0,{\xi }_i,i\in I)$ and $\tau$ is a vector of auxiliary variables (such as metrical characteristics of the objects or the container). The feasible set $G$ of (6) includes elements that satisfy the placement constraints (1)–(3) or (1), (4), (5). Additional constraints, like balance conditions, restrictions on the values of variables, prohibited spherical zones, etc., can be formulated as well.

Three specific classes of the PCGS model (6) will be considered in Section 3.

2.2. Useful Norms and Transformations

As was mentioned above, any norm can be used for the PCGS model. Below, several norms used in this study are listed, and some helpful transformations of the corresponding expressions are presented.

Lp norms. One of the widely known families of norms is the Lp norm that is defined as

$${\Vert x\Vert }_p={({\displaystyle \sum _k{\left|x_k\right|}^p})}^{1/p}\mathrm{for}\mathrm{p}\in [1,\infty ),$$

whereas for $\mathrm{p}=\infty$

$${\Vert x\Vert }_{\infty }=\underset{k}{\max }\left|x_k\right|$$

is the infinity norm.

For different $\mathrm{p}\in [1,\infty ]$, Lp norms generate different convex shapes of spheres in ${ℝ}^2$ and ${ℝ}^3$, e.g., diamonds (rhombuses), spheres (circles), objects with “round” angles, and cubes (squares) [39]. Figure 2 illustrates some shapes of unit spheres in ${ℝ}^2$ for $p=1,$ $p=1.5,$ $p=2,$ $p=3,$ $p=6$ and $p=\infty$.

Transforming the infinity norm ${\Vert x\Vert }_{\infty }$. Most NLP (NonLinear Programming) solvers do not permit the direct use of the expression $\underset{i=1,\dots ,n}{\max }\{|x_i|\}$ in NLP models. Therefore, we present the infinity norm

$${\Vert x\Vert }_{\infty }=\underset{i=1,\dots ,n}{\max }\{|x_i|\}$$

by a system of equations and inequalities.

Denote $t={\Vert x\Vert }_{\infty }$. By the definition of the maximum, we have

$$t\ge \left|x_i\right|,i=1,2,\dots ,n,$$

where $t$ provides the minimal value among all $t$ fulfilling the inequalities above.

Hence, calculating the norm is equivalent to the solution of the following optimization problem

$$\min \{t:t\ge |x_i|,i=1,2,\dots ,n\}.$$

For fixed $x_i$, $i=1,\dots ,n$, this is a linear programming problem. The corresponding dual problem has the form

$$\max \{{\displaystyle \sum _{i=1,\dots ,n}{\pi }_i\left|x_i\right|}:{\displaystyle \sum _{i=1,\dots ,n}{\pi }_i}=1,{\pi }_i\ge 0,i=1,\dots ,n\}.$$

By the duality theorem, a primal-dual pair $(t,\pi )$ is optimal if it is primal-dual feasible, and the objectives are equal, i.e.,

$$t={\displaystyle \sum _{i=1,\dots ,n}{\pi }_i\left|x_i\right|}$$

(7)

$$t\ge \left|x_i\right|,i=1,\dots ,n$$

(8)

$${\displaystyle \sum _{i=1,\dots ,n}{\pi }_i}=1,{\pi }_i\ge 0,i=1,\dots ,n.$$

(9)

That is, if $(t,\pi )$ satisfies the system (7)–(9), then $t=\underset{i=1,\dots ,n}{\max }\{|x_i|\}$ and vice versa.

Comment 1. 

For binary ${\pi }_i\in \{0,1\}$ the system (7)–(9) obviously defines the infinity norm. Constraint (8) follows from the definition of maximum, while constraints (7), (9) ensure that at least one inequality in (8) is fulfilled as equality. However, as shown above, the integrality of ${\pi }_i$ is not necessary.

Comment 2. 

Since $\left|x\right|=\max \{x,-x\}$ for any number x, with the same arguments as above, $\left|x\right|$ can be represented by a system of equations and inequalities.

Composition of norms. The maximum of a finite number of norms is also a norm [39]. In particular, for $\alpha ,\beta \in [1,\infty ]$,

$${\Vert x\Vert }_{comp}=\max \{{\Vert x\Vert }_{\alpha },{\Vert x\Vert }_{\beta }\},$$

defines a norm.

Consider the example

$${\Vert x\Vert }_{comp}=\max \{{\Vert x\Vert }_{\infty },\gamma {\Vert x\Vert }_1\}=\max \{\left|x_1\right|,\left|x_2\right|,\dots \left|x_n\right|,\gamma (\left|x_1\right|+\left|x_2\right|+\dots \left|x_n\right|)\},$$

where the first $n$ terms correspond to ${\Vert x\Vert }_{\infty },$ while the second term with $\gamma >0$ corresponds to a weighted sum norm ${\Vert x\Vert }_1.$

For example, for $x\in {ℝ}^2$ and $0.5<\gamma <1$, the unit sphere ${\Vert x\Vert }_{comp}\le 1$ has an octagonal shape, an intersection of a square and a rhombus (diamond). Especially for $\gamma =1/\sqrt{2}$, the regular octagon is obtained (Figure 3).

3. Some Cases of PCGS Problems

In this section, the following three variants of the PCGS problem are considered for ${\Vert x\Vert }_p$ and ${\Vert x\Vert }_{\infty }$: balance, homothetic, and sparse packing for a general case, $x\in {ℝ}^n$, and a particular case, $x\in {ℝ}^2$.

3.1. Generalized Balance Packing Problems (GBPP)

In GBPP, a family of the composed spherical objects must be placed inside a minimal spherical container subject to a given minimal allowable distance between each pair of objects as well as between each object and the boundary of the container. Moreover, a certain correspondence between the gravity centers of the objects and the container must be ensured.

Let minimal allowable distances ${\rho }_{kl}$ between each pair of objects $A_k$ and $A_l$, $k\in J$, $l\in J$, $k<l$, as well as minimal allowable distances ${\rho }_k$ between each object $A_k$, $k\in J$, and the boundary of the container $S_0$ be given, i.e.,

$$dist(A_k({\xi }_k),A_l({\xi }_l))\ge {\rho }_{kl}\iff dist(S_i({\xi }_i),S_j({\xi }_j))\ge {\rho }_{kl}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\begin{gathered} dist(A_k({\xi }_k),S_0^{*})\ge {\rho }_k\iff dist(S_i({\xi }_i),S_0^{*})\ge {\rho }_k\mathrm{for}i\in I_k,k\in J.\mathrm{Here} \\ {S}_0^{*}=R^n\backslash \mathrm{int}{S}_0. \end{gathered}$$

General model for ${\Vert x\Vert }_p$. GBPP is formulated as a nonlinear programming problem in the form

$$\underset{(\xi ,R)}{\min R}$$

(10)

subject to

$$\Vert {\xi }_i-{\xi }_0\Vert \le R-r_i-{\rho }_k\mathrm{for}i\in I_k,k\in J,$$

(11)

$$\Vert {\xi }_i-{\xi }_j\Vert \ge r_i+r_j+{\rho }_{kl}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(12)

$$\Vert {\xi }_i-{\xi }_j\Vert =a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(13)

$${\displaystyle \sum _i^m}{w}_i{\xi }_i={\xi }_0,$$

(14)

where ${\xi }_0$ is fixed.

In problems (10)–(14), constraints (11)–(12) define the minimal allowable distances between objects as well as between each object and the boundary of the container, (13) presents the composition condition, while (14) is a balance condition. The latter guarantees that the gravity center of the system of spheres $S_i({\xi }_i)$, $i\in I$ coincides with the center of the container $S_0$. In (14), $w_i$ is the weight of $S_i({\xi }_i)$, $i\in I$.

Mathematical Models of GBPP for two-dimensional spheres defined by the infinity norm. Then, the model (10)–(14) can be written as

$$\underset{(x,y,R)}{\min R}$$

subject to

$$\max \{\left|x_i-x_0\right|,\left|y_i-y_0\right|\}\le R-r_i-{\rho }_k\mathrm{for}i\in I_k,k\in J,$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}\ge r_i+r_j+{\rho }_{kl}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}=a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$${\displaystyle \sum _i^m}{w}_i{x}_i=x_0,{\displaystyle \sum _i^m}{w}_i{y}_i=y_0,$$

$$x=(x_i,i\in I),y=(y_i,i\in I),$$

where $(x_0,y_0)$ is fixed.

According to the results for transforming the infinity norm in Section 2, the above model can be equivalently transformed to the following optimization problem

$$\underset{(x,y,v,u,\pi ,R)}{\min R}$$

subject to

$$v_i={\pi }_i^x\left|x_i-x_0\right|+{\pi }_i^y\left|y_i-y_0\right|\mathrm{for}i\in I$$

$$v_i\le R-r_i-{\rho }_k\mathrm{for}i\in I_k,k\in J$$

$$v_i\ge \left|x_i-x_0\right|,v_i\ge \left|y_i-y_0\right|\mathrm{for}i\in I$$

$${\pi }_i^x+{\pi }_i^y=1,{\pi }_i^x\ge 0,{\pi }_i^y\ge 0\mathrm{for}i\in I$$

$$u_{ij}={\pi }_{ij}^x\left|x_i-x_j\right|+{\pi }_{ij}^y\left|y_i-y_j\right|\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\begin{gathered} u_{ij}\ge \left|x_i-x_j\right|,u_{ij}\ge \left|y_i-y_j\right|,u_{ij}\ge r_i+r_j+{\rho }_{kl} \\ \mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}, \end{gathered}$$

$${\pi }_{ij}^x+{\pi }_{ij}^y=1,{\pi }_{ij}^x\ge 0,{\pi }_{ij}^y\ge 0\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}=a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$${\displaystyle \sum _i^m}{w}_i{x}_i=x_0,{\displaystyle \sum _i^m}{w}_i{y}_i=y_0,$$

where

$$x=(x_i,i\in I),y=(y_i,i\in I),$$

$$v=(v_i,i\in I),u=(u_{ij},(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}),$$

$$\pi =({\pi }_i^x,{\pi }_i^y,i\in I,{\pi }_{ij}^x,{\pi }_{ij}^y,(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}).$$

Mathematical model of GBPP for a composite norm. Assume for simplicity that each object consists of one sphere. Then, the model (10)–(14) for the composite norm

$${\Vert x\Vert }_{comp}=\max \{\left|x\right|,\left|y\right|,\gamma (\left|x\right|+\left|y\right|)\}$$

becomes

$$\underset{(x,y,R)}{\min R}$$

subject to

$$\max \{\left|x_i-x_0\right|,\left|y_i-y_0\right|,\gamma (\left|x_i-x_0\right|+\left|y_i-y_0\right|)\}\le R-r_i\mathrm{for}i\in I,$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|,\gamma (\left|x_i-x_j\right|+\left|y_i-y_j\right|)\ge r_i+r_j\mathrm{for}(i,j)\in I\times I,i<j,$$

$${\displaystyle \sum _i^m}{w}_i{x}_i=x_0,{\displaystyle \sum _i^m}{w}_i{y}_i=y_0,$$

$$x=(x_i,i\in I),y=(y_i,i\in I).$$

This model can be further adjusted for the case when objects are composed by multiple spheres.

3.2. Generalized Homothetic Packing Problems (GHPP)

This problem is aimed to pack a family of scaled objects inside a spherical container of a given radius maximizing the scaling parameter.

Consider a family of objects composed by a union of scaled spheres

$$S_i(\lambda ,{\xi }_i)=\{x\in {ℝ}^n:\Vert x-{\xi }_i)\Vert \le \lambda r_i\},$$

where $0\le \lambda \le 1$.

General model for ${\Vert x\Vert }_p$. GHPP is formulated as a nonlinear programming problem in the form

$$\underset{(\xi ,\lambda )}{\max \lambda }$$

(15)

subject to

$$\Vert {\xi }_i-{\xi }_0\Vert \le R-\lambda r_i\mathrm{for}\mathrm{all}i\in I,$$

(16)

$$\Vert {\xi }_i-{\xi }_j\Vert \ge \lambda (r_i+r_j)\mathrm{for}\mathrm{all}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(17)

$$\Vert {\xi }_i-{\xi }_j\Vert =\lambda a_{ij}\mathrm{for}\mathrm{all}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(18)

$$0\le \lambda \le 1,$$

(19)

where ${\xi }_0$ is fixed.

The inequality (16) describes the containment condition $S_i(\lambda ,{\xi }_i)\subset S_0$, while (17) ensures non-overlapping of $S_i(\lambda ,{\xi }_i)$ and $S_j(\lambda ,{\xi }_j)$. By (18), the composition condition is included, while (19) describes the restriction on the homothetic coefficient $\lambda$.

Mathematical models of GHPP for two-dimensional spheres defined by the infinity norm. The model (15)–(19) for the infinity norm ${\Vert x\Vert }_{\infty }$ takes the form

$$\underset{(x,y,\lambda )}{\max \lambda }$$

subject to

$$\max \{\left|x_i-x_0\right|,\left|y_i-y_0\right|\}\le R-\lambda r_i\mathrm{for}i\in I,$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}\ge \lambda (r_i+r_j)\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}=\lambda a_{ij}.\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$0\le \lambda \le 1,$$

$$x=(x_i,i\in I),y=(y_i,i\in I).$$

The above model can be equivalently written as

$$\underset{(x,y,v,u,\pi ,\lambda )}{\max \lambda }$$

subject to

$$v_i={\pi }_i^x\left|x_i-x_0\right|+{\pi }_i^y\left|y_i-y_0\right|\mathrm{for}i\in I$$

$$v_i\le R-\lambda r_i,v_i\ge \left|x_i-x_0\right|,v_i\ge \left|y_i-y_0\right|\mathrm{for}i\in I$$

$${\pi }_i^x+{\pi }_i^y=1,{\pi }_i^x\ge 0,{\pi }_i^y\ge 0\mathrm{for}i\in I$$

$$u_{ij}={\pi }_{ij}^x\left|x_i-x_j\right|+{\pi }_{ij}^y\left|y_i-y_j\right|,u_{ij}\ge \lambda (r_i+r_j)\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$${\pi }_{ij}^x+{\pi }_{ij}^y=1,{\pi }_{ij}^x\ge 0,{\pi }_{ij}^y\ge 0\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}=\lambda a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$0\le \lambda \le 1,$$

$$x=(x_i,i\in I),y=(y_i,i\in I),v=(v_i,i\in I),u=(u_{ij},(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}),$$

$$\pi =({\pi }_i^x,{\pi }_i^y,i\in I_k,{\pi }_{ij}^x,{\pi }_{ij}^y,(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K}),$$

where $(x_0,y_0)$ is fixed.

Comment 3. 

This problem always has a global solution. If the above problem has a global solution with the objective value ${\lambda }^{*}=1$, then this solution corresponds to a feasible arrangement of full-size spheres $S_i(x_i)$, $i\in I$, (with original radii $r_i$, $i\in I$), inside $S_0$. If the global solution has the objective value ${\lambda }^{*}<1$, then it is possible to arrange all $m$ spheres with reduced radii ${\lambda }^{*}{r}_i$, $i\in I$ inside $S_0$.

3.3. Generalized Sparse Packing Problems (GSPP)

This problem is aimed to pack a family of objects inside a spherical container of a given radius maximizing a minimal distance between each pair of objects as well as between each object and the boundary of the container.

Mathematical model of GSPP with Lp norm. This model can be given as

$$\underset{(\xi ,\rho )}{\max \rho }$$

(20)

subject to

$$\Vert {\xi }_i-{\xi }_0\Vert \le R-r_i-\rho \mathrm{for}i\in I,$$

(21)

$$\Vert {\xi }_i-{\xi }_j\Vert \ge (r_i+r_j+\rho )\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(22)

$$\Vert {\xi }_i-{\xi }_j\Vert =a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

(23)

$$\rho \ge 0,$$

(24)

where ${\xi }_0$ is fixed.

Constraints in (21) present the distance condition between spheres and the boundary of the container, while those in (22) guarantee the distance condition between spheres belonging to different objects. The equations in (23) present the composition condition (1), while the inequality (24) describes the restriction on the parameter ρ.

Mathematical model of GSPP for two-dimensional spheres defined by the infinity norm. Then, the model (20)–(24) becomes

$$\underset{(x,y,\rho )}{\max \rho }$$

subject to

$$\max \{\left|x_i-x_0\right|,\left|y_i-y_0\right|\}\le R-r_i-\rho \mathrm{for}i\in I,$$

$$\max \{\left|x_i-x_j\right|,\left|y_i-y_j\right|\}\ge r_i+r_j-\rho \mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|(y_i-y_j)\right|\}=a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$0\le \rho \le R-\underset{i\in I}{\max }{r}_i,$$

$$x=(x_i,i\in I),y=(y_i,i\in I).$$

This model can be equivalently transformed to

$$\underset{(x,y,v,u,\pi ,\rho )}{\max \rho }$$

subject to

$$v_i={\pi }_i^x\left|x_i-x_0\right|+{\pi }_i^y\left|y_i-y_0\right|\mathrm{for}i\in I$$

$$v_i\le R-r_i-\rho ,v_i\ge \left|x_i-x_0\right|,v_i\ge \left|y_i-y_0\right|\mathrm{for}i\in I$$

$${\pi }_i^x+{\pi }_i^y=1,{\pi }_i^x\ge 0,{\pi }_i^y\ge 0\mathrm{for}i\in I$$

$$u_{ij}={\pi }_{ij}^x\left|x_i-x_j\right|+{\pi }_{ij}^y\left|y_i-y_j\right|,$$

$$u_{ij}\ge r_i+r_j-\rho \mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$$\max \{\left|x_i-x_j\right|,\left|(y_i-y_j)\right|\}=a_{ij}\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

$${\pi }_{ij}^x+{\pi }_{ij}^y=1,{\pi }_{ij}^x\ge 0,{\pi }_{ij}^y\ge 0\mathrm{for}(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K},$$

where $x=(x_i,i\in I),$ $y=(y_i,i\in I),$ $v=(v_i,i\in I)$, $u=(u_{ij},(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K})$, $\pi =({\pi }_i^x,{\pi }_i^y,i\in I_n,{\pi }_{ij}^x,(i,j)\in I_k\times I_l,(k,l)\in \mathfrak{K})$.

4. Computational Results

In this section, computational results for three classes of generalized packing problems considered in Section 3 are provided for the 2D case and various Lp norms. Solutions of NLP problems obtained by the solver BARON (Branch-And-Reduce Optimization Navigator) [40,41,42] using the NEOS server and the AMPL (A Mathematical Programming Language) platform [43] are reported and graphically presented. In what follows, we refer to the solution as “global” if BARON is stopped by fulfilling the optimality criterion, i.e., upper and lower bounds for the objective value coincide. Otherwise, the best solution obtained by BARON within a given time interval is presented.

4.1. Computational Results for Generalized Balance Packing Problem (GBPP)

Example 1. 

For this problem instance, the same input data as in [44] were used: $m=5$, $\{r_i,i=1,\dots ,5\}=\left\{0.1,0.2,0.3,0.5,0.8\right\}$, $\{w_i,i=1,\dots ,5\}=\left\{0.0785,0.314,0.7065,1.9625,5.024\right\}$. The global solutions obtained by BARON for different values of p are presented in Figure 4.

Example 2. 

For this problem instance, $m=4$ regular octagons and an octagonal container were represented as spheres in the composite norm considered in Section 2.2 with $\gamma =0.7071$. Here, $\{r_i,i=1,\dots ,4\}=\left\{1,2,3,4\right\}$, $\{w_i,i=1,\dots ,4\}=\left\{1,2,3,4\right\}$. The global solution obtained by BARON with $R^{*}=6.99999$ is shown in Figure 4f.

Example 3. 

These problem instances present irregular objects composed by spheres defined in Lp norms. The following three datasets were considered:

(a) 

$K=3,m=4$, $A_1=S_1\cup S_2,A_2=S_3,A_3=S_4$, $\{r_i,i=1,\dots ,4\}=\left\{3,2,1,1\right\}$;

(b) 

$K=2,m=4$, $A_1=S_1\cup S_2,A_2=S_3\cup S_4$, $\{r_i,i=1,\dots ,4\}=\left\{3,2,2,3\right\}$;

(c) 

$K=6,$ $m=9$, $A_1=S_1\cup S_2\cup S_3\cup S_4,$ $A_2=S_5,$ $A_3=S_6,$ $A_4=S_7,$ $A_5=S_8,$ $A_6=S_9$, $\{r_i,i=1,\dots ,9\}=\left\{4,4,4,4,2,3,3,3,3\right\}$.

Corresponding global solutions for different values of p obtained by BARON are presented in Figure 5 and Figure 6.

Example 4. 

These problem instances present irregular objects composed by spheres defined in Lp norms. The following two datasets were considered:

(a) 

$K=2,$ $m=5$, $A_1=S_1\cup S_2\cup S_3,$ $A_2=S_4,$ $A_3=S_5$, $\{r_i,i=1,\dots ,5\}=\left\{3,2,1,3,2)\right\}$;

(b) 

$K=2,$ $m=6$, $A_1=S_1\cup S_2\cup S_3,$ $A_2=S_4\cup S_5\cup S_6$, $\{r_i,i=1,\dots ,6\}=\left\{4,2,1,4,2,1)\right\}$;

Corresponding best solutions for different values of p obtained by BARON within 600 s are presented in Figure 7 and Figure 8.

4.2. Computational Results for Generalized Homothetic Packing Problem (GHPP)

Example 5. 

For this problem instance, $R=3$, $r_i=1$, $i=1,\dots ,m$. If the optimal value of the scaling parameter ${\lambda }^{*}=1$, then m unit spheres can be completely arranged in a spherical container of the given radius. Corresponding global solutions obtained by BARON are presented for different values of p in Figure 9.

4.3. Computational Results for Generalized Sparse Packing Problem (GSPP)

Example 6. 

For this problem instance, $R=3$, $m=4$, $r_i=1$, $i=1,\dots ,4$. Corresponding global solutions obtained by BARON are presented for different values of p in Figure 10.

Example 7. 

These problem instances present irregular objects composed by spheres defined in Lp norms. The following dataset was considered: $R=12$, $K=2,$ $m=6$, $A_1=S_1\cup S_2\cup S_3,$ $A_2=S_4\cup S_5\cup S_6$, $\{r_i,i=1,\dots ,6\}=\left\{4,2,1,4,2,1\right\}$. The best solutions obtained by BARON within 600 s. are presented for different values of $p$ in Figure 11.

5. Conclusions

A new class of packing problems for n-dimensional objects defined by spheres in terms of an arbitrary norm is introduced and referred to as Packing Objects Composed by Generalized Spheres (PCGS). The main advantage of PCGS is the simplicity of formulating placement conditions for a wide range of regular and irregular shapes. However, in the proposed modeling scheme, the shapes of the components used in the composed objects must have a certain central symmetry. This approach may be considered as a reasonable alternative to the known modeling techniques in irregular packing. For example, for the irregular problem instances presented in Figure 5, Figure 6, Figure 7, Figure 8 and Figure 11, the phi-function technique (see [24,45] and the references therein) can also be used. However, to formulate placement conditions by this technique, different phi-functions must be constructed for different shapes used in the composed objects. In our approach, the placement conditions have the same generic form for all shapes defined by generalized spheres. Studying similarities and differences between the proposed modeling approach and known modeling tools for irregular packing is an interesting area for future research.

In PCGS problems, the container and the spheres are assumed to have the same shapes, i.e., they are defined by the same norm. This is the case, e.g., in clustering problems where a number of similar objects are substituted by a single larger object having the same shape. However, using the following correspondence between the values of different Lp norms [39],

$${\Vert x\Vert }_p\le {\Vert x\Vert }_r\le n^{(1/r)-(1/p)}{\Vert x\Vert }_p\mathrm{for}x\in {ℝ}^n,1\le r<p$$

solutions obtained for a PCGS problem can be used to construct feasible solutions for packing problems where the shapes for the container and spheres are different. This can be useful, e.g., in constructing initial solutions in heuristic approaches.

The norm used in the composition condition (1) does not affect the shape of spheres considered in a PCGS problem. So, different norms can be used in composition and layout conditions. In computational experiments presented in the paper, the same norms were used for both conditions. Considering different norms in composition and layout conditions is an interesting area for future research.

In some packing problems, continuous rotations or reflections of the objects are not allowed. In this case, (1) can be replaced by the condition

$${\xi }_i-{\xi }_j=a_{ij},\forall (i,j)\in {\Im }_k,k\in J,$$

where $a_{ij}$ are given vectors. This condition ensures the shape conservation for all objects $A_k$ $(k\in J)$ only under translation. In this particular case, in addition to the length of vector $a_{ij}$, the direction of the vector is also taken into account. Correspondingly, condition (1) may be defined as $\Vert {\xi }_i-{\xi }_j\Vert =\Vert a_{ij}\Vert$, and different norms on the left and right sides of the equation can be used.

Instead of “rigid” composed objects with fixed pairwise distances between centers of the corresponding spheres, “soft” composed objects can be considered. In this case, the composition condition (1) must be modified, allowing a limited variation of the pairwise distances.

In this paper, numerical experiments were presented for the two-dimensional case of PCGS problems. Results for the 3D case are on the way. However, the models and transformations proposed in the paper are also valid for objects defined in ${ℝ}^n,n\ge 4$. It would be also interesting to test higher-dimensional problem instances arising, e.g., in multi-resource project management [29].

Only small illustrative numerical examples solved by BARON were considered in the paper. The objective was to demonstrate the ability of the proposed modeling approach to handle different shapes in a unified way. However, to treat large problems with many objects, special numerical techniques must be proposed. In particular, it can be checked whether conventional exact and heuristic algorithms designed for packing Euclidean spheres (see, e.g., [46,47,48] and the references therein) are or can be made norm independent. Some results in this direction are on the way.