Approximate Packing: Integer Programming Models, Valid Inequalities and Nesting

Abstract

Using a regular grid to approximate a container, packing objects is reduced to assigning objects to the nodes of the grid subject to non-overlapping constraints. The packing problem is then stated as a large scale linear 0-1 optimization problem. Different formulations for non-overlapping constraints are presented and compared. Valid inequalities are proposed to strengthening formulations. This approach is applied for packing circular and L-shaped objects. Circular object is considered in a general sense as a set of points that are all the same distance (not necessary Euclidean) from a given point. Different shapes, such as ellipses, rhombuses, rectangles, octagons, etc., are treated similarly by simply changing the definition of the norm used to define the distance. Nesting objects inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach.

9.1 Introduction

Packing problems generally consist of packing a set of items of known dimensions into one or more large objects or containers to minimize a certain objective (e.g. the unused part of the container or waste). Packing problems constitute a family of natural combinatorial optimization problems applied in computer science, industrial engineering, logistics, manufacturing and production processes (see, e.g., [1–4] and the references therein).

Along with industrial applications one may find packing problems in healthcare issues (e.g., [5, 6]). Wang [6] considered automated radiosurgical treatment planning for treating brain and sinus tumours. Radiosurgery uses the gamma knife to deliver a set of extremely high dose ionizing radiation, called “shots” to the target tumour area. For large target regions multiple shots of different intensity are used to cover different parts of the tumour. However, this procedure may result in large doses due to overlap of the different shots. Optimizing the number, positions and individual sizes of the shots can reduce the dose to normal tissue and achieve the required coverage.

Packing problems for regular shapes (circles and rectangles) of objects and/or containers are well studied (see, e.g., a review by [7] for circle packing). In circle packing problem the aim is to place a certain number of circles, each one with a fixed known radius inside a container. The circles must be totally placed in the container without overlapping. The shape of the container may vary from a circle, a square, a rectangular, etc. For the rectangular container there are two principal types of objectives [8, 9]: (a) regarding the circles (not necessary equal) as being of fixed size and the container as being of variable size and (b) regarding the circles and the container as being of fixed size and minimize “waste”. Examples of the first approach include: minimize the perimeter or the area of the rectangle; considering one dimension of the rectangle as fixed, minimize the other dimension (strip packing or open dimension problem). For the second approach various definitions of the waste can be used. The waste can be defined in relation to circles not packed or introducing a value associated with each circle that is packed (e.g., area of the circles packed).

Many variants of packing circular objects have been formulated as nonconvex (continuous) optimization problems with decision variables being coordinates of the centres [7]. Non-overlapping typically is assured by nonconvex constraints representing that the Euclidean distance separating the centres of the circles is greater than a sum of their radii. The nonconvex problems can be tackled by available nonlinear programming (NLP) solvers, however most NLP solvers fail to identify global optima and global optimization techniques have to be used [2, 10]. The nonconvex formulations of circular packing problem give rise to a large variety of algorithms which mix local searches with heuristic procedures in order to widely explore the search space. We will refer the reader to review papers presenting the scope of techniques and applications for regular packing problem (see, e.g., [8, 9, 11–13] and the references therein).

Irregular packing problems involve non-standard shapes of objects and/or containers. Irregular shapes are those that require non-trivial handling of the geometry [14, 31]. One of the most common representations for irregular shape is a polyhedral domain which may by nonconvex or multi-connected. Heuristic and metaheuristic algorithms are the basis for the solution approaches (see [3, 15] and the references therein).

Discrete approximations of objects by tetris-like items [3] and containers by grids [15–20] were recently used to simplify packing problems. This approach allows handling irregular shapes and reduces (approximately) packing problems to discrete optimization problems. To the best of our knowledge, the proposal to use a grid was first applied by Beasley [21] in the context of cutting problems.

This work is a continuation of Litvinchev and Ozuna [17]. Using a regular grid to approximate the container, packing is reduced to assigning the objects to the nodes of the grid subject to non-overlapping constraints. Different formulations for non-overlapping are considered and compared. Valid inequalities are proposed to strengthening formulations. This approach is applied for packing circular and L-shaped objects. Circular object is considered as a set of points that are all the same distance (not necessary Euclidean) from a given point. This way different shapes, such as ellipses, rhombuses, rectangles, octagons, etc. can be treated by simply changing the norm used to define the distance. Nesting objects inside one another is also considered. Numerical results are presented to demonstrate efficiency of the proposed approach.

The rest of the work is organized as follows. In Sect. 9.2 integer programming approximation of the packing problem is presented along with different formulations for non-overlapping. In Sect. 9.3 the proposed approach is applied to packing circular objects. Experimental results for packing different circular shapes are provided to demonstrate usefulness of valid inequalities proposed in Sect. 9.2. L-shaped objects and containers are considered in Sect. 9.4, while Sect. 9.5 presents concluding remarks and directions for the future research.

9.2 Basic Constructions

Suppose we have non-identical objects G _k , $k\in K=\left\{1,2,\dots K\right\}$ which have to be packed in a container G. In what follows we will use the same notation G _k , G for the domain in ℝⁿ and for its boundary assuming that it is easy to understand from the context what do we mean. It is assumed that no two objects overlap with each other and each packed object lies entirely in the container. Denote by S _k the area of G _k . Let at most M _k objects G _k are available for packing and at least m _k of them have to be packed. Denote by p _i , $i\in I=\left\{1,2\dots, n\right\}$ the nodes of a grid covering the container, ${p}_i\in G$. It is assumed that the position of the object in the container is completely characterized by the position of its reference point. Define binary variables ${x}_i^k=1$ if the reference point of the object G _k is assigned to the node i; ${x}_i^k=0$ otherwise. In what follows we will say that the object is assigned to the node i if the corresponding reference point is assigned to that node and will denote this as G ⁱ _k . For fixed i, k let

$$ {N}_{ik}=\left\{\ j,l:i\ne j\;\mathrm{such}\;\mathrm{that}\;{G}_k^i\;\mathrm{overlaps}\;\mathrm{with}\;{G}_l^j\right\}\!. $$

Let n _ik be the cardinality of ${N}_{ik}:{n}_{ik}=\left|{N}_{ik}\right|$. Then the problem of maximizing the area covered by the objects can be stated as follows:

$$ \max {\displaystyle \sum_{i\in I}{\displaystyle \sum_{k\in K}{S}_k}}{x}_i^k $$

(9.1)

subject to

$$ {m}_k\le {\displaystyle \sum_{i\in I}{x}_i^k}\le {M}_k, k\in K, $$

(9.2)

$$ {\displaystyle \sum_{k\in K}{x}_i^k}\le 1, i\in I, $$

(9.3)

$$ {x}_i^k=0\;\mathrm{f}\mathrm{o}\mathrm{r}\;{G}_k^i\backslash \left(G\cap {G}_k^i\right)\ne \varnothing\quad \mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,\;k\in K, $$

(9.4)

$$ {x}_i^k+{x}_j^l\le 1,\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,\;k\in K,\;\left(j,l\right)\in {N}_{ik}, $$

(9.5)

$$ {x}_i^k\in \left\{0,1\right\}, i\in I,k\in K. $$

(9.6)

Constraints (9.6) ensure that the number of objects packed is between m _k and M _k ; constraints (9.3) that at most one object is assigned to any node; constraints (9.4) that G _k cannot be assigned to the node i if G ⁱ _k is not totally placed inside G; pair-wise constraints (9.5) guarantee that there is no overlapping between the objects; constraints (9.6) represent the binary nature of variables.

Remark 2.1

Linear non-overlapping constraints (9.5) are equivalent to a single quadratic constraint

$$ Q(x)\equiv {\displaystyle {\sum}_{i,k}{x}_i^k}{\displaystyle {\sum}_{j,l\in {N}_{ik}}{x}_j^l}=0\left(\le 0\right). $$

(9.7)

If (9.7) holds, then for ${x}_i^k=1$ we have ${\displaystyle {\sum}_{j,l\in {N}_{ik}}{x}_j^l}=0$ yielding ${x}_j^l=0,\left(j,l\right)\in {N}_{ik}$, and if ${x}_j^l=1$ at least for one pair $\left(j,l\right)\in {N}_{ik}$, then ${x}_i^k=0$. Thus (9.5) can be considered as a specific linearization of (9.7). Other linearizations and relaxations of (9.7), e.g. used for the quadratic assignment problem [22] can also be considered.

Below we present different formulations for the non-overlapping constraints (9.5) which remain valid for the general definition of N _ik .

By the definition of N _ik if $\left(j,l\right)\in {N}_{ik}$, then $\left(i,k\right)\in {N}_{jl}$. Thus a half of the constraints in (9.5) are redundant since we have:

$$ {x}_i^k+{x}_j^l\le 1,\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,\;k\in K,\;\left(j,l\right)\in {N}_{ik}, $$

$$ {x}_j^l+{x}_i^k\le 1,\;\mathrm{f}\mathrm{o}\mathrm{r}\;j\in I,\;l\in K,\;\left(i,k\right)\in {N}_{jl}. $$

We may eliminate any (none) of these two constraints to get the reduced equivalent formulation. This can be represented by multiplying constraints (9.5) by a fixed ${\lambda}_j^l\in \left\{0,1\right\}$:

$$ {x}_i^k{\lambda}_j^l+{x}_j^l{\lambda}_j^l\le {\lambda}_j^l,\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,\;k\in K,\;\left(j,l\right)\in {N}_{ik}, $$

(9.8)

subject to ${\lambda}_j^l+{\lambda}_i^k\ge 1$. This way either one of the redundant constraints is eliminated (${\lambda}_j^l+{\lambda}_i^k=1$) or no-one (${\lambda}_j^l+{\lambda}_i^k=2$). Since eliminating redundant constraints does not affect the feasible set, the problem (9.1)–(9.6) is equivalent to (9.1)–(9.4), (9.6), (9.8) for any λ fulfilling the normalized condition

$$ \lambda \in \Lambda =\left\{{\lambda}_j^l\in \left\{0,1\right\}:{\lambda}_j^l+{\lambda}_i^k\ge 1,\left(j,l\right)\in {N}_{ik}\right\}. $$

Similar to plant location problems [23] we can state non-overlapping conditions in a more compact form. Summing up constraints (9.7) over $\left(j,l\right)\in {N}_{ik}$ we get

$$ {x}_i^k{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}+{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}{x}_j^l\le {\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l},\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,k\in K. $$

(9.9)

Proposition 2.1

For any $\lambda \in \Lambda$ constraints (9.5), (9.6) are equivalent to constraints (9.6), (9.9).

Proof

If constraints (9.5) are fulfilled, then obviously constraints (9.9) hold by construction. Now let constraints (9.9) are fulfilled. Define

$$\begin{array}{cc} {N}_{ik}^1=\left\{\left(j,l\right)\in {N}_{ik}:{\lambda}_j^l=1\right\},\;{N}_{ik}^0=\left\{\left(j,l\right)\in {N}_{ik}:{\lambda}_j^l=0\right\},\;{N}_{ik}^1\cup {N}_{ik}^0={N}_{ik},\\ \ \ \ \qquad\left|{N}_{ik}^1\right|={n}_{ik}^1,\;\left|{N}_{ik}^0\right|={n}_{ik}^0. \end{array}$$

By (9.9) we have

$$ {x}_i^k{n}_{ik}^1+{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}^1}{x}_j^l}\le {n}_{ik}^1 $$

and hence,

$$ \mathrm{if}\;{x}_i^k=1,\;\mathrm{then}\;{x}_j^l=0\;\mathrm{f}\mathrm{o}\mathrm{r}\;\left(j,l\right)\in {N}_{ik}^1. $$

(9.10)

By the definition, if $\left(j,l\right)\in {N}_{ik}$, then $\left(i,k\right)\in {N}_{jl}$. Thus by (9.9) we have

$$ {x}_j^l{\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}+{\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}{x}_i^k\le {\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}\;\mathrm{f}\mathrm{o}\mathrm{r}\;j\in I,\;l\in K. $$

(9.11)

In particular, (9.11) is fulfilled for $\left(j,l\right)\in {N}_{ik}^0$. Since ${\lambda}_j^l+{\lambda}_i^k\ge 1$, then for $\left(j,l\right)\in {N}_{ik}^0$ all λ ^k _i in (9.11) are positive (${\lambda}_i^k=1$). Then by (9.11) we have:

$$ \mathrm{if} {x}_j^l=1\;\mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{at}\;\mathrm{least}\;\mathrm{o}\mathrm{ne}\;\left(j,l\right)\in {N}_{ik}^0,\;\mathrm{then}\;{x}_i^k=0. $$

(9.12)

Note that constraints (9.5) can be interpreted in two ways. First if ${x}_i^k=1$, then ${x}_j^l=0$ for all $\left(j,l\right)\in {N}_{ik}$. Second, if ${x}_j^l=1$ for at least one $\left(j,l\right)\in {N}_{ik}$, then ${x}_i^k=0$. Combining (9.10) and (9.12) we may conclude that if constraints (9.9) are fulfilled, then (9.5) hold.□

Remark 2.2

In Galiev and Lisafina [16] the compact formulation

$$ {x}_i{n}_i+{\displaystyle \sum_{j\in {N}_i}{x}_j}\le {n}_i\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I $$

(9.13)

was used to represent non-overlapping constraints for the case of packing identical circles. This corresponds to a singleton set K and all multipliers λ equal to 1 in (9.9).

Remark 2.3

Proposition 2.1 remains true for nonnegative (not necessary binary) multipliers λ subject to ${\lambda}_j^l+{\lambda}_i^k\ne 0$. The proof is similar.

As follows from Proposition 2.1, the non-overlapping constraints can be stated in different forms (see [20] for an illustrative example). We have a family of formulations equivalent to (9.5) and obtained for different multipliers λ in (9.9). To compare equivalent formulations, let

$$ {P}_1=\left\{x\ge 0:{x}_i^k+{x}_j^l\le 1,\;\mathrm{f}\mathrm{o}\mathrm{r}\;i\in I,\;k\in K,\left(j,l\right)\in {N}_{ik}\right\}, $$

$$ {P}_2=\left\{x\ge 0:{x}_i^k{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}+{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}{x}_j^l\le {\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l},i\in I,k\in K\right\}, $$

where multipliers λ in P ₂ fulfil the normalizing condition stated in Proposition 2.1.

Proposition 2.2

${P}_1\subset {P}_2$.

Proof

Since constraints of P ₂ are a linear combination of those in P ₁ with nonnegative multipliers λ, then ${P}_1\subseteq {P}_2$. To show that ${P}_1\subset {P}_2$ we need to find a point in P ₂ that is not in P ₁.

This point can be constructed as follows. Choose $\left(i,k\right)\in {N}_{jl}$ and $\left(j,l\right)\in {N}_{ik}$ such that ${\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l},\;{\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}\ge 2$. Set to zero all the variables except x ^k _i , x ^l _j . Obviously all constraints in P ₂ corresponding to zero variables are fulfilled. Define x ^k _i , x ^l _j to fulfil the two remaining constraints as equalities:

$$ {x}_i^k{\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}+{x}_j^l={\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}, {x}_j^l{\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}+{x}_i^k={\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}. $$

Denote ${\overline{n}}_{ik}={\displaystyle \sum_{\left(j,l\right)\in {N}_{ik}}{\lambda}_j^l}, {\overline{n}}_{jl}={\displaystyle \sum_{\left(i,k\right)\in {N}_{jl}}{\lambda}_i^k}$ with ${\overline{n}}_{ik},{\overline{n}}_{jl}\ge 2$. The corresponding solution of the two equations above is

$$ {x}_i^k=\frac{{\overline{n}}_{jl}\left({\overline{n}}_{ik}-1\right)}{{\overline{n}}_{jl}{\overline{n}}_{ik}-1}<1, {x}_j^l=\frac{{\overline{n}}_{ik}\left({\overline{n}}_{jl}-1\right)}{{\overline{n}}_{jl}{\overline{n}}_{ik}-1}<1 $$

with

$$ {x}_i^k+{x}_j^l=1+\frac{1+{\overline{n}}_{jl}{\overline{n}}_{ik}-{\overline{n}}_{jl}-{\overline{n}}_{ik}}{{\overline{n}}_{jl}{\overline{n}}_{ik}-1}>1.$$

This point violates corresponding constraint in P ₁ and hence ${P}_1\subset {P}_2$ as desired.□

As follows from Proposition 2.2, the pairwise formulation (9.1)–(9.6) is stronger than the compact one (9.1)–(9.4), (9.6), (9.9) in the sense of Wolsey [23].

In general, checking if the object is not totally placed inside the container is tricky. However, for a convex container and a polygonal object this problem can be simplified as stated below.

Proposition 2.3

Let G be a convex set and G _k be a (not necessary convex) polygon. Let ${v}_{ki}^t,t=1,\dots, {T}_k$ be all vertices of G ⁱ _k . Then ${G}_k^i\subseteq G$ iff ${v}_{ki}^t\in G,t=1,\dots, {T}_k$.

Proof

If ${G}_k^i\subseteq G,$ then obviously all vertices of G ⁱ _k are in G. Let now ${v}_{ki}^t\in G,t=1,\dots, {T}_k$. Consider the convex hull of G ⁱ _k , $conv\left({G}_k^i\right)=\left\{y:y={\displaystyle {\sum}_t{\alpha}_t{v}_{ki}^t},{\displaystyle {\sum}_t{\alpha}_t=1,}{\alpha}_t\ge 0\right\}$. Since all vertices of G ⁱ _k are in G, then by convexity of G any convex linear combination of vertices also belongs to G and hence $conv\left({G}_k^i\right)\subseteq G$. By the definition of convex hull, ${G}_k^i\subseteq conv\left({G}_k^i\right)$ and hence ${G}_k^i\subseteq G$ as desired.□

Good upper (dual) bounds are very important to solve integer programming problems. We may expect that the upper bound obtained by the linear programming relaxation of the problem (9.1)–(9.6) provides a poor upper bound for the optimal objective. For example, for packing equal circles in a rectangular container the objective value of the LP-relaxation grows linearly with respect to the number of grid nodes (see [20] for details).

To tightening the LP-relaxation we consider valid inequalities ensuring that no grid node is covered by two objects. To present this family, define matrix [α ^k _ij ] as follows. Let ${\alpha}_{ij}^k=1$ if G ⁱ _k covers a node j, ${\alpha}_{ij}^k=0$ otherwise. The following constraints ensure that no nodes of the grid can be covered by two objects:

$$ {\displaystyle \sum_{k\in K}{\displaystyle \sum_{j\in I}{\alpha}_{ij}^k}}{x}_j^k\le 1, i\in I. $$

(9.14)

Note that (9.14) is not equivalent to the non-overlapping constraints (9.5).

9.3 Circular Objects

Define a circular object C _k as a set of points that all are at most the distance R _k from a given point called centre, ${C}_k=\left\{y:\left\Vert y-{y}_{0k}\right\Vert \le {R}_k\right\}$. Here the norm used to define the object is not necessary the Euclidean [32]. Let d _ij be the distance between node points i, j in the sense of the norm used to define the circular object.

The set N _ik in (9.5) is now defined as follows: ${N}_{ik}=\left\{j,l:i\ne j,{d}_{ij}<{R}_k+{R}_l\right\}$. For matrix [α ^k _ij ] in (9.14) we have ${\alpha}_{ij}^k=1$ for ${d}_{ij}<{R}_k$, ${\alpha}_{ij}^k=0$ otherwise.

Using different norms we can use constructions of the previous section for packing different geometrical objects of the same shape. For example, a circular object in the maximum norm ${\left\Vert y\right\Vert}_{\infty }:={ \max}_r\left\{\left|{y}_r\right|\right\}$ is represented geometrically by a square, taxicab norm ${\left\Vert y\right\Vert}_1:={\displaystyle {\sum}_r\left|{y}_r\right|}$ yields a rhombus. In a similar way we may handle rectangles, ellipses, etc. Using a superposition of norms, we can consider more complex circular objects. For

$$ \left\Vert y\right\Vert :={ \max}_r\left\{\left|{y}_r\right|,\gamma {\displaystyle {\sum}_r\left|{y}_r\right|}\right\} $$

and a suitable $0.5<\gamma <1$ we get an octagon, an intersection of a square and a rhombus.

A numerical experiment was designed to evaluate the performance of different non-overlapping formulations and to see the impact of the valid inequalities for packing circular objects in a rectangular container.

In the first part of the experiment the test bed set of 9 instances from ([16], Table 3) was used for packing maximal number of circles into a rectangle of width 3 and height 6. A rectangular uniform grid of size Δ along both sides of the container was used. It was assumed that the supply of the objects is unlimited and constraints (9.2) were relaxed. Similar to [16] the nodes located too close (close than a radius) to the boundary were eliminated from consideration and thus constraints (9.4) were omitted. In all experiments optimization problems were solved by the system CPLEX 12.6 [24]. The runs were executed on a desktop computer with CPU AMD FX 8350 8-core processor 4 GHz and 32 GB RAM.

The following four formulations were compared: pairwise formulation (9.1)–(9.6) (Cmpl), reduced formulation (9.1)–(9.6) without redundant constraints (CmplH), compact formulation (9.13) as in Galiev and Lisafina [16] (Cmpct), and compact formulation obtained by summing up constraints in the reduced formulation (9.1)–(9.6) (CmpctH). All these four formulations were combined with valid inequalities (cuts) (9.14), the corresponding formulations are denoted by CmplC, CmplHC, CmpctC, CmpctHC. The results of the numerical experiment are given in Table 9.1. Here the first three columns present instance number, circle radius, and grid size Δ. The last columns give CPU time (in seconds) for different formulations. For all problem instances $mipgap=0$ was set for running CPLEX. In this table asterisk indicates that the computation was interrupted after the computation time exceeded 12-h CPU. Number of binary variables and optimal packings are presented in Table 9.2 in columns (n _Δ) and (C), correspondingly.

Table 9.1 CPU-time for circles (gap 0 %)

Table 9.2 LP-relaxations

As we can see from Table 9.1, CPU time for complete formulations is lower than for the compact, especially for large instances. Eliminating redundant constraints typically (but not always) reduces CPU time. Although eliminating redundancy does not change corresponding LP-relaxation, it may affect the path selected by branch and bound technique and thus result in increase/decrease of CPU time.

Introducing valid inequalities decreases CPU time for all problem instances and for all problem formulations. Although introducing valid inequalities slightly increases time to solve the LP-relaxation, the effect of improving quality of the LP-bound becomes more important for the convergence of the overall branch and bound scheme. That is why CPU time decreases significantly for hard instances 6, 7, 9, while for “easy” instances the decrease may be relatively modest. Moreover, with valid inequalities CPU time necessary to get provably optimal solution ($\mathit{mipgap}\,{=}\,0$) is comparable with that reported in Galiev and Lisafina [16] for their heuristic approach.

Table 9.2 presents values of the LP-relaxations with/without valid inequalities for packing equal circles (C), ellipses (E), rhombuses (R) and octagons (O) into the same $3\times 6$ rectangle using the same values Δ for the grid. The standard Euclidean and taxicab norms were used to define circles and rhombuses, while norms

$$ \left\Vert y\right\Vert :={\left(2{y}_1^2+{y}_2^2\right)}^{1/2}\;\mathrm{and}\;\left\Vert y\right\Vert := \max \left\{\left|{y}_1\right|,\left|{y}_2\right|,\left(1/\sqrt{2}\right)\left(\left|{y}_1\right|+\left|{y}_2\right|\right)\right\} $$

were used for ellipses and octagons. The same values of radii as in Table 9.1 were used to define circular objects. In Table 9.2 the first three columns present instance number, number of binary variables (n _Δ) and value of the LP-relaxation without valid inequalities (LP). For all circular objects the optimal value of the LP-relaxation was 0.5n _Δ (all variables equal to 0.5). The last eight columns give the value of the optimal integer solution (in bold) and the value LPC of the LP-relaxation improved by the valid inequalities (next to bold). We see that introducing valid inequalities improves significantly the quality of the LP bound for all shapes of the objects. The detailed study of this subject for the case of circles one can find in Litvinchev et al. [20] for the same test bed instances. Packings for the instance 7 are presented in Fig. 9.1.

Fig. 9.1

Packing equal circular objects for instance 7

In many applied problems packing smaller objects inside a larger one is permitted. For example, in tube industry the tubes are produced in a continuous extract machine and cut to the length of the container used for shipping. Before being placed in the container they may be inserted inside other, thicker tubes, so that usage of container space is maximized. Since all the tubes have the same length, maximizing container load is equivalent to maximizing the area filled with circles (rings) in a section of the container. Similar problems arise, e.g. in stacking up different containers to form a tower [25] and in visualization of large hierarchical data by 3D nested cylinders [26]. In tube industry the process is usually named telescoping [27], in optimized packing context the terms nesting [2] or recursive packing [28] are used. Although the term nesting is also used for packing irregular objects [15], we will use nesting for packing smaller objects inside larger ones assuming that it is easy to understand from the context what do we mean.

To consider nesting circular objects inside one another, we only need to modify the non-overlapping constraints. In order to C ⁱ _k be non-overlapping with other objects being packed (including objects placed inside C ⁱ _k ), it is necessary that ${x}_j^l=0$ for $j\in I, l\in K$, such the ${R}_k-{R}_l<{d}_{ij}<{R}_k+{R}_l$ for ${R}_k>{R}_l$. Let

$$ {\Omega}_{ik}=\left\{j,l:i\ne j,{R}_k-{R}_l<{d}_{ij}<{R}_k+{R}_l, {R}_k>{R}_l\right\}. $$

Then the non-overlapping constraints for packing circular objects with nesting can be stated as

$$ {x}_i^k+{x}_j^l\le 1,\ \mathrm{f}\mathrm{o}\mathrm{r}\ i\in I;k\in K;\left(j,l\right)\in {\Omega}_{ik}. $$

(9.15)

Constraints (9.3) have to be omitted in case of nesting.

If nesting is permitted it may be necessary to take into account the difference between external and internal sizes of the object, i.e. consider the object as a circular ring (a region bounded by two concentric circular objects) having a positive thickness. To consider nesting-subject-to-thickness we need only to redefine the set Ω _ik . Let g _k be the thickness of the circle C _k . For Ω _ik defined as

$$ {\Omega}_{ik}=\left\{j,l:i\ne j,{R}_k-{g}_k-{R}_l<{d}_{ij}<{R}_k+{R}_l, {R}_k-{g}_k>{R}_l\right\} $$

we get non-overlapping constraints similar to (9.15).

The results for packing two different octagons in a square 30 × 30 container maximizing the total area of the packed objects are presented in Table 9.3. Here the first three columns give instance number, radii, and a number of grid nodes (integer variables). The last columns give the total area without nesting (N−), with nesting (N+) and with nesting and thickness (N+T), number of small (O1) and large (O2) objects packed, as well as corresponding CPU time in sec. The thickness g _k was defined as 0.1R _k . The packings obtained for the instance 1 are presented in Fig. 9.2.

Table 9.3 Packing 2 different octagons

Fig. 9.2

Packing two octagons for instance 1

9.4 L-shaped Objects and Containers

In this section we consider packing L-shaped objects. These shapes appear, e.g. in packing interpretations of scheduling with non-constant operational cycles [3]. Let L-object (see Fig. 9.3) be a superposition of rectangles ($A\times b$) and ($a\times B$) with edges parallel to the principal axes, $A>a>0$, $B>b>0$ and the principal corner considered as a reference point.

Fig. 9.3

L-object

To state the problem (9.1)–(9.6) we need to specify constraints (9.4), (9.5), i.e. present a constructive way to check if the object is totally placed inside the container and if the objects overlap. Suppose we have two L-objects, L _i and L _j , with the reference points located at (y _1i , y _2i ) and (y _1j , y _2j ). Introducing binary variables ${z}_i,{z}_j\in \left\{0,1\right\}$ these objects can be represented as follows:

$$ {L}_i=\Big\{\left({y}_1,{y}_2,{z}_i\right):{z}_i\in \left\{0,1\right\},0\le {y}_1-{y}_{1i}\le {A}_i+{z}_i\left({a}_i-{A}_i\right), $$

$$ 0\le {y}_2-{y}_{2i}\le {b}_i+{z}_i\left({B}_i-{b}_i\right)\Big\}, $$

$$ {L}_j=\Big\{\left({y}_1,{y}_2,{z}_j\right):{z}_j\in \left\{0,1\right\},0\le {y}_1-{y}_{1j}\le {A}_j+{z}_j\left({a}_j-{A}_j\right), $$

$$ 0\le {y}_2-{y}_{2j}\le {b}_j+{z}_j\left({B}_j-{b}_j\right)\Big\}. $$

We wonder if ${L}_i\cap {L}_j\ne \varnothing$. This holds if the system of inequalities

$$ \max \left\{{y}_{1i},{y}_{1j}\right\}\le {y}_1\le \min \left\{{y}_{1i}+{A}_i+{z}_i\left({a}_i-{A}_i\right),{y}_{1j}+{A}_j+{z}_j\left({a}_j-{A}_j\right)\right\}, $$

$$ \max \left\{{y}_{2i},{y}_{2j}\right\}\le {y}_2\le \min \left\{{y}_{2i}+{b}_i+{z}_i\left({B}_i-{b}_i\right),{y}_{2j}+{b}_j+{z}_j\left({B}_j-{b}_j\right)\right\} $$

is consistent at least for one combination of binary z _i , z _j . This can be verified by inspection.

Substituting ${z}_i={z}_j=0$ yields

$$ \max \left\{{y}_{1i},{y}_{1j}\right\}\le \min \left\{{y}_{1i}+{A}_i,{y}_{1j}+{A}_j\right\},\max \left\{{y}_{2i},{y}_{2j}\right\}\le \min \left\{{y}_{2i}+{b}_i,{y}_{2j}+{b}_j\right\}. $$

For ${z}_i={z}_j=1$ we have

$$ \max \left\{{y}_{1i},{y}_{1j}\right\}\le \min \left\{{y}_{1i}+{a}_i,{y}_{1j}+{a}_j\right\},\max \left\{{y}_{2i},{y}_{2j}\right\}\le \min \left\{{y}_{2i}+{B}_i,{y}_{2j}+{B}_j\right\}. $$

Substituting ${z}_i=1,{z}_j=0$ yields

$$ \max \left\{{y}_{1i},{y}_{1j}\right\}\le \min \left\{{y}_{1i}+{a}_i,{y}_{1j}+{A}_j\right\},\max \left\{{y}_{2i},{y}_{2j}\right\}\le \min \left\{{y}_{2i}+{B}_i,{y}_{2j}+{b}_j\right\}. $$

And finally for ${z}_i=0,{z}_j=1$ we get

$$ \max \left\{{y}_{1i},{y}_{1j}\right\}\le \min \left\{{y}_{1i}+{A}_i,{y}_{1j}+{a}_j\right\},\max \left\{{y}_{2i},{y}_{2j}\right\}\le \min \left\{{y}_{2i}+{b}_i,{y}_{2j}+{B}_j\right\}. $$

Thus if at least one pair of inequalities above hold, then ${L}_i\cap {L}_j\ne \varnothing$. In a similar way we can check overlapping for the other composite objects, e.g., for star-shapes represented as a superposition of a square and a rhombus.

To check if L-object is totally placed inside a convex container we can use Proposition 2.3 since all vertices of the object are easily identified. However, for rectangular and L-shaped containers with all edges parallel to the principal axes we can state constraints (9.4) based on simple geometrical considerations.

Below we present results of a numerical experiment for packing L-objects in rectangular and L-shaped containers. The normalized objective was defined as the total area of the objects divided over the area of the smallest object. For the case of equal objects the normalized objective coincides with the number of objects.

In the first part of the experiment the test bed set of 6 instances was used for packing maximal number of equal L-objects into a rectangular container of width 3 and height 6. Two types of the objects were considered with the shapes corresponding to $A=B=2R$ and $B=0.5A=2R$. The thickness of L-object was defined as $a=b=0.3R$ in both cases. A rectangular uniform grid of size $\Delta =0.15R$ (a half of the thickness) was used. The results of the numerical experiment are given in Table 9.4. The first three columns present instance number, value of R and a number of binary variables n _Δ. The next five columns present indicators for the case $A=B$: the optimal value of integer solution z; value of the LP-relaxation without and with valid cuts, LP and LP+C; CPU time in sec. to get integer solution without and with valid cuts, T and T+C. The last five columns present similar indicators for the case $B=0.5A$. For all problem instances $mipgap=0$ was set for running CPLEX.

Table 9.4 Equal L-objects

As we can see from Table 9.4 introducing valid inequalities improves significantly the LP-bound and reduces CPU-time, especially for hard instances.

In the second part of the experiment two different L-objects were packed in a square 30 × 30 container maximizing the total normalized area of the packed objects. Four instances were considered according to the shape of the objects. For instances 1 and 3 $A=B=2R$ and for instances 2 and 3, $B=0.5A=2R$. In all cases $a=b=R$. Two values of R were considered and for $R={R}_2$ (large object) the minimal number of the objects to be packed was set to two, ${m}_2=2$ in (9.2).

The results are presented in Table 9.5. Here the first four columns give instance number, radii R ₁, R ₂, number n _Δ of grid nodes (integer variables) and the value z of the optimal solution. Columns 5 and 6 give the number of small (L1) and large (L2) objects in the optimal solution, while column 7 indicates corresponding CPU time in sec. for the case of using the valid inequalities (9.14). Asterisk indicates that the computation was interrupted after the computation time exceeded 1,800 s. CPU time and the value in parenthesis gives the corresponding mipgap. Columns 8 and 9 present the value of the LP-relaxation without (LR) and with (LR+C) valid inequalities. The last three columns give the number of objects packed (L1+, L2+) and CPU time (T+) for the case of nesting allowed. Optimal packings for instances 1–4 are presented in Figs. 9.4 and 9.5 for the case without nesting and in Figs. 9.6 and 9.7 for nesting allowed.

Table 9.5 Packing 2 different L-objects

Fig. 9.4

Instances 1, 2

Fig. 9.5

Instances 3, 4

Fig. 9.6

Instances 1, 2 with nesting

Fig. 9.7

Instances 3, 4 with nesting

In the final part of experimentation L-shaped container was considered for $A=B=30$, $a=b=12$. Two instances were considered according to the shape of the two different L-objects. For the first instance $A=B=2R$ for both objects and for the second $B=0.5A=2R$. In all cases $a=b=R$. Two values of R were used, ${R}_1=1$, ${R}_2=5.3$ and for $R={R}_2$ we set ${m}_2=2$ in (9.2). A rectangular uniform grid of size $\Delta = \min \left\{{R}_1,{R}_2\right\}=1$ was used giving ${n}_{\Delta}=637$ grid nodes in the L-container. The optimal solution was obtained in less than 1 s. CPU time. For the first instance ($A=B=2R$) the optimal solution gives 108 small and 2 large L-objects without nesting and (120, 4) for nesting allowed. For the second instance ($B=0.5A=2R$) we get (33, 2) and (71, 2) objects, respectively. The optimal packings are presented in Figs. 9.8 and 9.9.

Fig. 9.8

Instance 1

Fig. 9.9

Instance 2

9.5 Conclusions

Integer programming formulations were considered for approximated packing objects in a container. Using a grid approximation of the container packing problems can be transformed into optimal assignment of the objects (reference points) to nodes of the grid subject to non-overlapping constraints. In this work we used linear non-overlapping constraints. However, as noted in Remark 2.1, the problem (9.1)–(9.6) is closely related to the quadratic assignment problem and corresponding approaches can be also used for packing problems. Some results in this direction are in course.

Valid inequalities (9.14) were proposed to strengthening the formulation and our numerical experiments demonstrate that the value of the LP-relaxation can be tightened significantly by (9.14). Moreover, aggregating valid cuts not only improve the value of the relaxation, but also change the structure of the optimal LP-solution. A simple LP-based heuristic is proposed in Litvinchev et al. [29] for packing circular objects.

Grid approximation of the container results in a large-scale integer optimization problem. Using decomposition and/or aggregation techniques [30] to split the nodes of the grid into smaller subsets (container decomposition) and/or creating “macro nodes” (nodes aggregation) may be helpful to cope with high dimension. Some results in this direction are in course.

A critical question in grid approximation is how to choose parameters of the grid, e.g. shape and number of nodes, to get a reasonable trade-off between computational burden and proximity to the true optimal packing. The use of non-uniform and/or adaptive grids seems to be interesting direction for the future research.