Keywords

4.1 Introduction

This chapter summarizes and extends results descending from a long-lasting research effort aimed at solving complex three-dimensional packing problems arising in the space industry [1]. In this challenging context, the relevant issues could hardly be considered applying a standard typology. Quite often, indeed, the operational scenarios to deal with are characterized by the presence of tricky geometries and complex additional conditions that can even be of global impact, such as in the case of balancing.

Often irregularly shaped and of non-negligible dimensions, the objects involved cannot be realistically approximated in terms of single cuboids (i.e. rectangular parallelepipeds). Significant effort has therefore been addressed to allow for tetris-like items, i.e. objects consisting of clusters of mutually orthogonal (rectangular) parallelepipeds. Similarly, the domains (containers) to take account of are generally not box-shaped and often several internal volumes are not exploitable, since these correspond either to clearance/forbidden zones or actual holes. Additionally, separation planes (with no fixed position specified a priori) can partition the domain into sub-domains. Some items may be requested to assume pre-defined positions/orientations or are subject to placement restrictions, such as the requirement of having a given side parallel or orthogonal to a specified direction.

In order to cope with overall conditions such as balancing, when necessary in addition to those mentioned above, a Global Optimization (GO) based view is highly desirable. This is essentially based on a modeling philosophy, as opposed to a pure algorithmic one, consisting of sequential procedures limited to local search.

A number of modeling-based works are present in the literature, although these are usually restricted to the case of box-shaped items (e.g. [2–5]). On the other hand, very interesting studies consider strongly irregularly shaped objects, even though the adopted philosophy is mainly focused on local optimization [6–8].

This chapter emphasizes the solution of non-standard packing issues, in the context outlined above, by a GO approach. Mixed Integer Linear/Non-linear (MILP/MINLP) formulations have been conceived and a library of mathematical models set up. This supports ad hoc heuristics, implemented to obtain satisfactory, albeit probably sub-optimal (or at least non-optimal proven), solutions to a wide collection of real-world instances [1].

The general problem of placing tetris-like items orthogonally into a convex domain, without pair-wise intersection, so that the total volume loaded is maximized, is the main topic of this chapter.

Section 4.2 investigates a dedicated MILP model [1], specifically constructed to overcome the challenging computational difficulties that are typically associated with the problem in question, when formulated in terms of Mathematical Programming. It is, indeed, well known that, even when single parallelepipeds are involved (i.e., tetris-like items consisting of one component only), the relevant MILP models available in the specialist literature (e.g., [3, 4]) are very hard to solve. This holds also if a number of valid inequalities are purposely added. The model discussed in this section can be used to solve small-size instances, tout court. In addition, it can advantageously be adopted as a basic element of the above-mentioned heuristics that act recursively, following an overall greedy approach.

MINLP models (e.g., [2]) have been built up for the feasibility sub-problem, derived from the general one, when a set of items need to be loaded (without any possibility of rejection, provided that the instance is feasible) and no objective function is assigned. Moreover, they can be adopted [1] to improve approximate solutions where intersections between items are admitted, “minimizing” the overall overlap (actually this optimization target is attained only partially, through surrogate functions). An MINLP version, implemented for this specific case is summarized in Sect. 4.3.

An alternative formulation of the model reported in Sect. 4.2 (currently being looked into) is presented in Sect. 4.4. The relevant MILP model extends, in the case of tetris-like items and convex domains, previous formulations available in the literature, based on the discretization of the domain and often referred to as space-indexed or grid-based-position paradigms (e.g., [9, 10]). All models presented in Sects. 4.2, 4.3, and 4.4 are suitable for considering additional conditions, such as specific loading requirements or balancing. Nevertheless, these aspects, albeit frequent in a number of real-world applications, are not considered in this chapter and the reader is referred to [1] for an extensive discussion (except the space-indexed formulation). Section 4.5 introduces the generation of (two-dimensional) covering tetris-like items, providing outer approximation of polygons. The issue of simplifying the representation of complex objects in such a way is a very interesting optimization problem per se, especially considering its potential applications. The three-dimensional extension is not surveyed in this chapter (since it is quite straightforward). Section 4.6 proposes a novel heuristic approach, mainly based on the MILP model presented in Sect. 4.2.

An extensive experimental analysis has recently been carried out, concerning the MILP model presented in Sect. 4.2. One chapter of this book [11] reports and examines the computational results available to date, in depth, highlighting the advantages of the overall methodology suggested. Since this chapter is restricted to the computational aspects (assuming the relevant model as known) the present work serves also the scope of providing a topical framework. Fasano [1] offers an extensive bibliography, both on packing problems in general and on the more specific subjects considered here.

In order to state the general problem discussed in this chapter, the following definition is introduced.

A tetris-like item is a set of rectangular parallelepipeds positioned orthogonally, with respect to an (orthogonal) reference frame . This frame is called “local” and each parallelepiped is a “ component” .

Hereinafter, “tetris-like item ” will usually be simply referred to as “item,” if no ambiguity occurs; similarly, “rectangular parallelepipeds” are referred to as “parallelepipeds.”

A set I of N items, together with a domain D, consisting of a (bounded) convex polyhedron , is considered (see Fig. 4.1). This is associated with a given orthogonal reference frame, indicated in the following as the main frame. The general problem is to place items into D, maximizing the loaded volume, considering the following positioning rules:

Fig. 4.1
figure 1

Tetris-like item packing into a convex domain

Full size image

  • each local reference frame has to be positioned orthogonally, with respect to the main one (orthogonality conditions );

  • for each item, each component has to be contained within D ( domain condition s);

  • the components of different items cannot overlap (non-intersection condition s).

4.2 Direct MILP Formulation

An MILP model for the general problem stated in Sect. 4.1 is described next, expanding on some aspects not pointed out in its previous discussion [1]. Recalling the basic concepts introduced there, the main orthogonal reference frame has origin O and axes w β , \( \beta \in \left\{1,2,3\right\}=B \). It is assumed, without loss of generality, that the whole domain D is entirely contained inside its first octant. Similarly, each local reference frame, associated with every item, is chosen so that all item components lie within its first octant. Its origin coordinates, with respect to the main reference frame , are denoted by o βi . The set Ω of all (24 possible) orthogonal rotation s, admissible for any local reference frame, with respect to the main one, is introduced.

The set of components of a generic item i is denoted by C i . For each item i, the set E hi of all (8) vertices associated with each of its components h is defined. An extension of this set is obtained by adding to E hi the geometrical center of component h. This extended set is denoted by \( {\hat{E}_{hi}}\). For each item i and each possible orthogonal orientation \( \omega \in \varOmega \), the following binary (0–1) variables are introduced:

  • \( {\chi}_i\in \left\{0,1\right\} \), with \( {\chi}_i=1 \) if item i is chosen; \( {\chi}_i=0 \) otherwise;

  • \( {\vartheta}_{\omega i}\in \left\{0,1\right\} \), with \( {\vartheta}_{\omega i}=1 \) if item i is chosen and it has the orthogonal orientation \( \omega \in \Omega \); \( {\vartheta}_{\omega i}=0 \) otherwise.

The orthogonality conditions can be expressed as follows:

$$ \forall i\in I {\displaystyle \sum_{\omega \in \varOmega }{\vartheta}_{\omega i}}={\chi}_i, $$
(4.1)
$$ \forall \beta \in B,\forall i\in I,\forall h\in {C}_i,\forall \eta \in {\overset{\frown }{E}}_{hi} $$
(4.2)
$$ {w}_{\beta \eta hi}={o}_{\beta i}+{\displaystyle \sum_{\omega \in \Omega}{W}_{\omega \beta \eta hi}{\vartheta}_{\omega i}}. $$

Here w βηhi (\( \forall \eta \in {\overset{\frown }{E}}_{hi} \)) are the vertex coordinates of component h, with respect to the main reference frame, or its geometrical center (\( \eta =0 \)), relative to item i; W ωβηhi are the projections on the axes w β of the coordinate differences between points \( \eta \in {\overset{\frown }{E}}_{hi} \) and the origin of the local reference frame, corresponding to orientation ω of item i.

The domain condition s are expressed as follows.

$$ \forall \beta \in B,\forall i\in I,\forall h\in {C}_i,\forall \eta \in {E}_{hi} $$
(4.3)
$$ {w}_{\beta \eta hi}={\displaystyle \sum_{\gamma \in V}{V}_{\beta \gamma }{\lambda}_{\gamma \eta hi}}, $$
$$ \forall i\in I,\forall h\in {C}_i,\forall \eta \in {E}_{hi} {\displaystyle \sum_{\gamma \in V}{\lambda}_{\gamma \eta hi}}={\chi}_i $$
(4.4)

Here V is the set of vertices delimiting D, V βγ are their coordinates (with respect to the main reference frame) and λ γηhi are non-negative variable s. These conditions correspond to the well-known necessary and sufficient condition s for a point to belong to a convex domain .

The non-intersection condition s are represented by the constraints shown below, see [1] for more details:

$$ \forall \beta \in B,\forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.5-1)
$$ {w}_{\beta 0hi}-{w}_{\beta 0kj}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{+}\right), $$
$$ \forall \beta \in B,\forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.5-2)
$$ {w}_{\beta 0kj}-{w}_{\beta 0hi}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{-}\right), $$
$$ \forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.6)
$$ {\displaystyle \sum_{\beta \in B}\left({\sigma}_{\beta hkij}^{+}+{\sigma}_{\beta hkij}^{-}\right)}\ge {\chi}_i + {\chi}_j-1, $$
$$ \forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.7-1)
$$ {\displaystyle \sum_{\beta \in B}\left({\sigma}_{\beta hkij}^{+}+{\sigma}_{\beta hkij}^{-}\right)}\le {\chi}_i, $$
$$ \forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.7-2)
$$ {\displaystyle \sum_{\beta \in B}\left({\sigma}_{\beta hkij}^{+}+{\sigma}_{\beta hkij}^{-}\right)}\le {\chi}_j. $$

Here the constants D β are the sides (respectively parallel to the main reference frame axes) of the parallelepiped, of minimum dimensions, containing D ; w β0hi and w β0kj are the center coordinates, with respect to the main reference frame, of components h and k of items i and j, respectively; L ωβhi and L ωβkj are their side projections on the w β axes, corresponding to the orientation ω; \( {\sigma}_{\beta hkij}^{+} \) and \( {\sigma}_{\beta hkij}^{-}\in \left\{0,1\right\} \).

The constraints (4.7-1) and (4.7-2) have been introduced with the purpose of tightening the model (they are not taken account of in the following). It is worth noticing that, in some particular situations, the above non-intersection constraints ((4.5-1), (4.5-2) and (4.6)) should be properly complemented, in order to avoid solutions that could hardly be considered as appropriate in practice (see [1]). Nonetheless, these aspects will be omitted here.

The most straightforward formulation relevant to the objective function, to maximize the volume loaded, is the following:

$$ max{\displaystyle \sum_{i\in I}{V}_i{\chi}_i}, $$
(4.8)

where V i represents the volume of item i.

The formulation represented by expressions (4.1)–(4.8) (with possible variants regarding the constraints) is notoriously inefficient, even when restricted to single parallelepipeds only, and the situation tends to become even worse when tetris-like items are involved.

The following expression has thus been suggested [1] as a promising alternative to (4.8):

$$ max{\sum_{i\in I,\ h\in {C}_i}\frac{V_{hi}}{{\sum\limits_{\alpha \in A}{L}_{\alpha hi}}}{\sum\limits_{\stackrel{\beta \in B,} {\omega \in \varOmega}}{L}_{\omega \beta hi}{\vartheta}_{\omega i}}}, $$
(4.9)

where L αhi , \( \alpha \in \left\{1,2,3\right\}=A \), are the sides of the generic component h of item i. It is assumed, without loss of generality, that \( {L}_{1hi}\le {L}_{2hi}\le {L}_{3hi} \).

As easily seen, the functions (4.8) and (4.9) are equivalent for any integer- feasible solution . Indeed, the following implications hold:

$$ \forall i\in I,\forall h\in {C}_i {\chi}_i=0\iff \frac{{\displaystyle \sum\limits_{\stackrel{\beta \in B,} {\omega \in \Omega}}{L}_{\omega \beta hi}{\vartheta}_{\omega i}}}{{\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}}=0, $$
(4.10-1)
$$ \forall i\in I,\forall h\in {C}_i {\chi}_i=1\iff \frac{{\displaystyle \sum\limits_{\stackrel{\beta \in B,} {\omega \in \Omega}}{L}_{\omega \beta hi}{\vartheta}_{\omega i}}}{{\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}}=1. $$
(4.10-2)

Both derive from (4.1), the second, in particular, is true in virtue of the fact that, in any integer-feasible solution: \( \forall i\in I/{\chi}_i=1 \), \( \exists !\omega \in \Omega /{\vartheta}_{\omega i}=1 \).

Since objective functions (4.8) and (4.9) are equivalent, they give rise to the same optimal (or sub-optimal) integer solutions. Nonetheless, quite different behaviors occur when dealing with (partial or total) LP-relaxations of the MILP model (as usually utilized by the solvers), making the choice for the second one highly preferable. Some considerations follow, in support of this point.

First of all, it is worth recalling that non-trivial intrinsic difficulties make the MILP approach very intricate, per se [1]. This is the case, for instance, of the implicit transitivity conditions. Considering, indeed, the generic triplet of components h, h′, h″ of items i, i′, i″, respectively, these can be expressed as follows: if, along the axis w β , h precedes h′ and h′ precedes h″ then h precedes h″, along the same axis. A major concern, moreover, is certainly represented by the non-intersection constraints (4.5-1) and (4.5-2), since they are of the big-M typology (well known for being, in general, very tough to cope with). Consequently, it is not surprising at all that a strong tendency to item overlapping prevails in the LP-relaxed solutions, making the task of finding an integer-feasible solution (albeit sub-optimal) demanding. As an immediate consideration, it should be noticed that the MILP model, related to (4.8), is characterized by a very weak correlation of the non-intersection constraints (4.5-1) and (4.5-2) with the χ i variables appearing in the objective function (the association is attained only indirectly through (4.1) to (4.4) and (4.6)). On the contrary, (4.9) acts directly on the terms L ωβhi ϑ ωi , appearing in (4.5-1) and (4.5-2), “minimizing” (in terms of a surrogate objective function), the overall overlapping between items. In order to see this point better, it is useful to introduce the variables \( {l}_{\beta hi}={\displaystyle \sum_{\omega \in \Omega}{L}_{\omega \beta hi}{\vartheta}_{\omega i}} \). For each component h of the generic item i, they represent indeed the lengths of the sides parallel to each w β axis, respectively (and consequently \( {l}_{\beta hi}\in \left[0,{L}_{3hi}\right] \), when an LP-relaxation is applied).

In order to go deeper into this matter, it is worth pointing out that a necessary condition for integer-feasibility is provided by the following (cf. 4.10-2):

$$ \forall i\in I,\forall h\in {C}_i {\chi}_i=1\Rightarrow {\displaystyle \sum_{\stackrel{\beta \in B,} {\omega \in \Omega}}{L}_{\omega \beta hi}{\vartheta}_{\omega i}=}{\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}. $$
(4.11)

When an LP-relaxation is applied to the model associated with objective function (4.9), the inequalities below hold:

$$ \forall i\in I,\forall h\in {C}_i {\displaystyle \sum_{\stackrel{\beta \in B,} {\omega \in \Omega}}{L}_{\omega \beta hi}{\vartheta}_{\omega i}\le }{\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}, $$
(4.12)

with \( {\vartheta}_{\omega i}\in \left[0,1\right] \).

In order to show this, a single component h of item i is selected. As easily gathered, depending on the specific orientation ϑ ωi taken by item i, each variable l βhi can assume only one value out of the following: L 1hi , L 2hi and L 3hi . More precisely, the following logical conditions hold:

$$ \forall \alpha \in A \left({l}_{1hi}={L}_{\alpha hi}\right)\underset{\bar{\mkern6mu}}{\vee}\left({l}_{2hi}={L}_{\alpha hi}\right)\underset{\bar{\mkern6mu}}{\vee}\left({l}_{3hi}={L}_{\alpha hi}\right), $$
(4.13-1)
$$ \forall \beta \in B \left({l}_{\beta hi}={L}_{1hi}\right)\underset{\bar{\mkern6mu}}{\vee}\left({l}_{\beta hi}={L}_{2hi}\right)\underset{\bar{\mkern6mu}}{\vee}\left({l}_{\beta hi}={L}_{3hi}\right), $$
(4.13-2)

where “\( \underset{\bar{\mkern6mu}}{\vee } \)” represents the “exclusive or.” As a straightforward consequence of what is specified above, for each α and β, there are eight cases in which \( {l}_{\beta hi}={L}_{\alpha hi} \), implying that the component side of length L αhi is parallel to the reference axis w β . The subsets \( {\Omega}_{\alpha \beta hi}\subset \Omega \), with \( \alpha \in A \) and \( \beta \in B \), are hereafter introduced: they represent, for each α and β all the orientations \( \omega \in \Omega \) such that \( {l}_{\beta hi}={L}_{\alpha hi} \). Evidently, the following conditions hold (with h and i fixed):

$$ \forall \alpha \in A {\displaystyle \underset{\beta \in B}{\cup }{\Omega}_{\alpha \beta hi}}=\Omega, $$
(4.14-1)
$$ \forall \alpha \in A,\forall \beta, \beta^{\prime}\in B {\Omega}_{\alpha \beta hi}\cap {\Omega}_{\alpha \beta \prime hi}=\O. $$
(4.14-2)

The equalities below are thus respected, in virtue of (4.1):

$$ {\sum_{\beta \in B}{l}_{\beta hi}=} {\sum_{\alpha \in A}}\ \sum_{\omega \in \Omega_{\stackrel{\alpha \beta hi,} {\beta \in B}}} {L}_{\alpha hi}{\vartheta}_{\omega i}={\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}\ {\chi}_i, $$
(4.15)

with \( {\vartheta}_{\omega i},{\chi}_i\in \left[0,1\right] \). This proves the validity of inequalities (4.12).

The key point associated with objective function (4.9) may be summarized as follows. It induces, indeed, in any LP-relaxation, to attain the upper bounds corresponding to (4.12), and thus to satisfy the (necessary) integer-feasibility conditions (4.11). On the other hand, the overall item overlapping, controlled by (4.5-1) and (4.5-2) is (indirectly) “minimized.” The adoption of objective function (4.9) has proved very efficient in practice [11].

4.3 An MINLP Model for the Feasibility Sub-problem

Non-linear formulations addressing the orthogonal placement of rectangles inside convex domains are available in the literature (e.g., [2, 12, 13]). The following section recalls an MINLP approach put forward in [1, 14], to which the reader is referred for a more in-depth discussion. The general packing problem, as stated in Sect. 4.1, is considered here in terms of feasibility only, i.e. it is expected that a number of preselected items can be loaded (otherwise the problem is infeasible).

For this purpose, all the variables χ i , corresponding to the given set of items, are set to one, keeping the orthogonality and domain constraints (4.1), (4.2), (4.3) and (4.4) unaltered. Since no objective function is provided a priori, an ad hoc one is introduced. It consists of penalty functions, representing the non-intersection constraints (4.5-1), (4.5-2) and (4.6) that are eliminated from the model. The corresponding expression is shown below:

$$ \begin{array}{ll}min \left\{\displaystyle\sum\limits_{\stackrel{\stackrel{\beta \in B,} {{}i,j\in I/i<j,}} {{{}\scriptsize{h}\scriptsize{\in} {\scriptsize{C}}_i,k\in {C}_j}}} max \left\{-{\left({w}_{\beta 0hi}-{w}_{\beta 0kj}\right)}^2+{\left[\frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}\right]}^2\right.\right.\\ \left.\left.\qquad\quad\ \ \ \qquad\qquad\qquad\qquad-{r}_{\beta hkij},0\vphantom{\left\{-{\left({w}_{\beta 0hi}-{w}_{\beta 0kj}\right)}^2+{\left[\frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}\right]}^2\right.}\right\}+{K}_P{ \displaystyle\sum\limits_{\stackrel{i,\ j\in I/i<j,} {{}h\in {C}_i,\ k\in {C}_j,}}{\displaystyle \prod_{\beta \in B}{r}_{\beta hkij}}}\vphantom{\left\{\displaystyle\sum\limits_{\stackrel{\stackrel{\beta \in B,} {{}i,j\in I/i<j,}} {{{}\scriptsize{h}\scriptsize{\in} {\scriptsize{C}}_i,k\in {C}_j}}}\right.}\right\}. \end{array}$$
(4.16)

Here \( {r}_{\beta hkij}\in \left[0,{D}_{\beta}^2\right] \), whilst K P is a positive coefficient (that represents an appropriate “weight”); the other terms have been defined in Sect. 4.2. The general problem, as stated in Sect. 4.1, has thus been reformulated in terms of an MINLP.

It is immediately seen that the objective function (4.16) is non-negative and that a zero-global -optimal solution of the above defined model exists if and only if the constraints (4.1), (4.2), (4.3), (4.4), (4.5-1), (4.5-2) and (4.6) (with all variables χ i set to one) define a feasible region . This objective function, indeed, “minimizes” the intersection between items (indirectly) and any global optimum provides a solution to the feasibility sub-problem under discussion.

The MINLP model outlined in this section, even if theoretically suitable for solving the general problem stated in Sect. 4.1, when a given set of items is requested to be loaded, is, per se, very hard to solve. Search for sub-optimal solutions can however be profitably adopted to improve the initial or intermediate ones, obtained by heuristic procedures [1], where intersection between items is admitted. In such a case, the MINLP model is utilized to reduce the overall overlapping.

4.4 Grid-Based Position MILP Model

The space-indexed approach (e.g., [9, 10]) can be advantageously reconsidered to include operational scenarios that are quite frequent in practice. Relevant extensions, albeit still addressed to box-shaped items and domains, are aimed at allowing for additional conditions, such as stability and load bearing (cf. [15]). This section focuses instead on a grid-based-position MILP model, conceived as an alternative to the one discussed in Sect. 4.2, focusing on the orthogonal packing of tetris-like items, inside a convex region.

The given domain (of Sect. 4.1) is discretized, so that it is associated with a set of internal points whose coordinates are supposed to be integer. The main reference frame, still defined as in Sect. 4.1, thus becomes a unit-cube grid, whose node coordinates are indicated as \( \left({n}_1,{n}_2,{n}_3\right)\in D \). Tetris-like items are grouped on a typology basis. The set of all types τ is denoted by T.

The following assumptions relevant to each tetris-like item are made:

  • the local reference frame has a pre-fixed orientation (orthogonal with respect to the main one);

  • the local reference frame origin can only be positioned on grid points; all component vertices have integer coordinates.

Remark 4.1

It should be observed that the prefixed orientation assumption does not represent an actual limitation. Orthogonal rotations of the same object can, indeed, simply be considered by introducing a set of pre-oriented items (one for each possible orthogonal orientation).

For each type τ, the sub-set of grid points in which the local frame origin can be positioned (so that the corresponding item is entirely inside the domain D) is introduced. It is denoted hereinafter by D τ .

The binary variables \( {\chi}_{\tau {n}_1{n}_2{n}_3}\in \left\{0,1\right\} \) are then defined, with the following meaning:

\( {\chi}_{\tau {n}_1{n}_2{n}_3}=1 \) :

if one item of type τ is positioned with its local reference origin in the grid node of coordinates (n 1, n 2, n 3);

\( {\chi}_{\tau {n}_1{n}_2{n}_3}=0 \) :

otherwise.

A possible modeling of the general problem (of Sect. 4.1) is shown next, considering the orthogonality, domain, and non-intersection conditions. The first are implicitly respected by the orientation of each item type that is imposed a priori. The second ones are stated by introducing, for each type τ, the grid point sub-sets D τ . The non-intersection conditions, instead, need to be expressed through dedicated constraints.

The following inequalities prevent the positioning of more than one local reference frame in the same grid points:

$$ \forall {n}_1,{n}_2,{n}_3\in D { \sum_{\stackrel{\tau \in T/}{{}{n}_1,{n}_2,{n}_3\in {D}_{\tau}}}{\chi}_{\tau {n}_1{n}_2{n}_3}}\le 1. $$
(4.17)

Furthermore, for each pair (τ, τ ′) of item types (including the case when \( \tau^{\prime }=\tau \)) and each grid node \( \left({n}_1,{n}_2,{n}_3\right)\in {D}_{\tau } \), the set \( {F}_{\tau \prime \tau {n}_1{n}_2{n}_3} \) is introduced. Except for point (n 1, n 2, n 3), it contains all the forbidden positions, for all item types, when a τ one is assumed to be placed in (n 1, n 2, n 3). Each set \( {F}_{\tau \prime \tau {n}_1{n}_2{n}_3} \) is built as follows:

  • position virtually any item i of type τ (indicated as i τ ) in node \( \left({n}_1,{n}_2,{n}_3\right)\in {D}_{\tau } \) ;

  • identify for any item i τ ′ all the surrounding nodes \( \left(n{\prime}_1,n{\prime}_2,n{\prime}_3\right)\in {D}_{\tau \prime } \) where overlapping between i τ ′ and i τ would occur (at least partially), should i τ ′ be positioned in (n ′ 1, n ′ 2, n ′ 3).

The inequalities below prevent the overlapping of items, on the basis of the forbidden positions:

$$ \forall \tau, \tau^{\prime}\in T,\forall {n}_1,{n}_2,{n}_3\in {D}_{\tau } $$
(4.18)
$$ {\displaystyle \sum_{n{\prime}_1,n{\prime}_2,n{\prime}_3\in {F}_{\tau \prime \tau {n}_{{}_1}{n}_{{}_2}{n}_{{}_3}}}{\chi}_{\tau \prime n{\prime}_1n{\prime}_2n{\prime}_3}}\le \left( 1-{\chi}_{\tau {n}_1{n}_2{n}_3}\right)\left|{F}_{\tau \prime \tau {n}_1{n}_2{n}_3}\right|, $$

where \( \left|{F}_{\tau \prime \tau {n}_1{n}_2{n}_3}\right| \) indicate the cardinalities of the corresponding sets.

For each typology τ, a maximum number N τ of items are available. These conditions are represented as follows:

$$ \forall \tau \in T {\displaystyle \sum_{n_1,{n}_2,{n}_3\in {D}_{\tau }}{\chi}_{\tau {n}_1{n}_2{n}_3}}\le {N}_{\tau }. $$
(4.19)

The objective function has the following form:

$$ max{\displaystyle \sum_{\stackrel{\tau \in T,} {{}{n}_1,{n}_2,{n}_3\in {D}_{\tau}}} {V}_{\tau }{\chi}_{\tau {n}_1{n}_2{n}_3}}, $$
(4.20)

denoting by V τ the volume associated with each item type τ.

It should be noticed that, whilst the discretized model discussed in this section is very simple, since it consists of three groups of constraints only, the generation of both sets D τ and \( {F}_{\tau^{\prime} \tau {n}_1{n}_2{n}_3} \) is, instead, non-trivial. An ad hoc preprocessing phase has to be envisaged, in order to generate the model instances in practice. These quite tricky aspects are not discussed here.

As for the model discussed in Sect. 4.2, also in this case additional conditions, such as balancing, could quite easily be introduced. They are, however, not taken into account here. It should, moreover, be observed, that the grid-based position model, as formulated in this section is (at least) theoretically susceptible to extensions contemplating any irregularly shaped item type. In such cases, the above-mentioned pre-processing phase should be carried out appropriately.

4.5 An MILP Approach for the Tetris-Like Approximation of Irregular Items

The problem of approximating irregular objects, in terms of covering, by means of tetris-like items, can be regarded per se as an optimization problem. This section provides some topical insights, restricting the discussion to the two-dimensional case of convex polygons (the three-dimensional generalization is quite straightforward). More precisely, the issue under consideration can be stated as follows:

Given a convex polygon, cover it with a minimum-surface tetris-like item, consisting of N R components (rectangles).

Evidently, the larger N R is, the better approximation of the polygon is possible. Moreover, in the problem general statement formulated above, it could be implicit that the dimensions of each rectangle may vary with continuity within given ranges. The formulation provided hereinafter, however, is based on quite a simplified approach. It restricts the selection of the rectangles to a finite number of possibilities, resulting from a proper discretization carried out a priori.

Given a pre-oriented polygon, we shall consider it with respect to an orthogonal frame with origin O and axes w β , \( \beta \in \left\{1,2\right\}=B \) (the same symbolism already utilized in the three-dimensional case is maintained, as no ambiguity occurs). The axis w 1 will represent the “horizontal,” while w 2 the “vertical” one. The edges of the polygon are subsequently discretized, by drawing “horizontal” straight lines that identify a set of border points including all polygon vertices, see Fig. 4.2.

Fig. 4.2
figure 2

Polygon covering by a (2D-)tetris-like item

Full size image

The sets of all such lines and points are indicated as H and Γ respectively, corresponding to generic indexes r and γ. For each pair of lines \( \left(r,r^{\prime}\right)\in H \), all the enclosed border points determine the set Γ rr ′. The relevant coordinates are referred to as W rr ′ βγ , with \( \beta \in B \) and \( \gamma \in {\varGamma}_{rr\prime } \).

For each Γ rr ′, the following lower and upper bounds are defined:

$$ \forall \beta \in B \underline{W}_{rr\prime \beta }=\underset{\gamma \in {\Gamma}_{rr\prime }}{min}\left\{{W}_{rr\prime \beta \gamma}\right\},\;{\overline{W}}_{rr\prime \beta }=\underset{\gamma \in {\Gamma}_{rr\prime }}{max}\left\{{W}_{rr\prime \beta \gamma}\right\}. $$
(4.21)

The rectangle R rr ′, corresponding to the straight lines r and r′, delimited by the vertices listed here, is introduced:

$$ {V}_{rr\prime LL}\left(\underline{W}_{rr\prime 1},\underline{W}_{rr\prime 2}\right), {V}_{rr\prime LU}\left(\underline{W}_{rr\prime 1},{\overline{W}}_{rr\prime 2}\right), $$
(4.22)
$$ {V}_{rr\prime UL}\left({\overline{W}}_{rr\prime 1},\underline{W}_{rr\prime 2}\right), {V}_{rr\prime UU}\left({\overline{W}}_{rr\prime 1},{\overline{W}}_{rr\prime 2}\right). $$

Next, the binary variables \( {\chi}_{rr\prime}\in \left\{ 0, 1\right\} \) are defined as:

\( {\chi}_{rr\prime }= 1 \) :

if rectangle R rr ′ is selected as a component of the covering tetris-like item;

\( {\chi}_{rr\prime }=0 \) :

otherwise.

The (continuous) variables below are also introduced:

$$ \forall \gamma \in \varGamma, \forall r, r^{\prime}\in H {\chi}_{\gamma rr^\prime} \in [ 0, 1].$$

They are assigned as per the following condition:

\( {\chi}_{\gamma rr\prime }= 1 \) :

if the border point \( \gamma \in \varGamma \) is covered by the selected rectangle R rr ′;

\( {\chi}_{\gamma rr\prime }=0 \) :

otherwise.

The following inequalities correlate the variables χ γrr ′ and χ rr ′:

$$ \forall r,r^{\prime}\in H/r<r^{\prime} {\displaystyle \sum_{\gamma \in {\Gamma}_{rr\prime }}{\chi}_{\gamma rr\prime }} = \left|{\Gamma}_{rr\prime}\right|{\chi}_{rr\prime }, $$
(4.23)

where \( \left|{\Gamma}_{rr\prime}\right| \) indicates the cardinality of Γ rr ′. These expressions highlight the obvious implication that if a rectangle R rr ′ is selected, then all the associated border points are covered by it (and vice versa). With this in mind, the inequalities below are introduced to guarantee that each border point is actually covered:

$$ \forall \gamma \in \Gamma {\displaystyle \sum_{r,r^{\prime}\in H/r < r^{\prime }}{\chi}_{\gamma rr\prime }}\ge 1. $$
(4.24)

Since the number of selected rectangles has to be equal to N R , the following equations hold:

$$ {\displaystyle \sum_{r,r^{\prime}\in H/r<r^{\prime }}{\chi}_{rr\prime }={N}_R}. $$
(4.25)

The objective function is stated below:

$$ min{\displaystyle \sum_{\stackrel{r,r^{\prime}\in H/} {{}r<r^{\prime}}}{S}_{rr\prime }{\chi}_{rr\prime }}, $$
(4.26)

where the terms S rr ′ represent the surfaces associated with each rectangle, respectively.

Remark 4.2

Ingenuity is needed to extend the approach proposed to non-convex polygons. As a first consideration, the rectangles R rr ′ should be split in the corresponding sub-rectangles actually covering parts of the polygon. This way, each term S rr ′ would be calculated (more precisely) as the sum of the sub-rectangles’ surfaces. The situation is even more complicated when the non-convexities are related to the presence of internal “holes.” All these aspects may well become the subject of a dedicated research.

4.6 Heuristics

An overall modeling-based heuristic methodology has been developed to tackle real-world scenarios, generally consisting of large-scale instances, characterized by tricky geometries dealt with by tetris-like approximations, in the presence of additional conditions such as balancing. In [1] a range of models and procedures were discussed in a general framework, providing the basis to build alternative solution strategies. A novel and promising approach, representing the objective of ongoing research, is, instead, discussed here (see [11] for experimental results). Prior to proceeding with the topical discussion, the basic concept of abstract configuration [1] is recalled, providing the following two definitions.

Constraints of the types

$$ {w}_{\beta 0hi}-{w}_{\beta 0kj}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}, $$
$$ {w}_{\beta 0kj}-{w}_{\beta 0hi}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}, $$

corresponding to either \( {\sigma}_{\beta hkij}^{+}=1 \) or \( {\sigma}_{\beta hkij}^{-}=1 \) in (4.5-1) and (4.5-2), respectively, are called relative position constraint s.

Given a set of N items and the corresponding N C pairs of components belonging to different items, an abstract configuration consists of N C relative position constraint s, exactly one for each pair, giving rise to a feasible solution in any unbounded domain .

A method to extract an abstract configuration from any approximate solution, with intersections between items, has been shown [1]: this subject is not discussed here, referring to the cited work. As previously, the whole process discussed in this section is essentially based on the following modules: Initialization, Packing, Item-exchange, and Hole-filling. In the versions investigated here, they are based on the MILP model presented in Sect. 4.2. In the following, the heuristic overall logic is outlined first and then the basic modules are considered.

4.6.1 Overall Logic

As in the heuristics looked into in the previous work, the search algorithm consists of a recursive procedure that, at each step, activates one of the above-mentioned modules. An abstract configuration is generated at each step tentatively improving the previous one; the best-so-far solution is retrieved when the current step does not meet its objective. The search process is terminated when a satisfactory, albeit non-optimal proven solution (in terms of loaded volume) is found. Since for real-world instances the computational task is quite demanding, at each step, only sub-optimal solutions are sought, interrupting the optimization on the basis of suitable stopping rules.

The Initialization phase is aimed at solving a feasibility sub-problem, with the scope of providing a good starting abstract configuration. An LP-relaxation of the general MILP model of Sect. 4.2 is adopted. All the N items available are considered, although some of them may be rejected subsequently, during the search process. This module seeks for a first approximate solution, enclosing all the items inside the domain and “minimizing” their total overlapping indirectly. An abstract configuration is directly provided by the solution obtained. The MINLP model of Sect. 4.3 may be adopted, if opportune, to further reduce (although without a guarantee for eliminating) the intersection between items. In this case, a procedure able to extract abstract configurations from approximate solutions with overlapping has to be available.

The abstract configuration derived from the Initialization step is imposed to the Packing module that offers, by means of the general MILP model of Sect. 4.2, a non-approximate (albeit usually still sub-optimal) solution, maximizing the loaded volume and rejecting items if necessary. Both Item-exchange and Hole-Filling phases are devoted to the improvement, if possible, of the Packing solution, providing (if successful) upgraded abstract configurations. Also for these steps the general MILP model of Sect. 4.2 is utilized, and non-approximate solutions are found.

The Item-exchange module is aimed at carrying out advantageous exchanges between non-loaded and loaded items. Two subsets of non-loaded and loaded items, respectively, are selected. The relative positions (corresponding to the current abstract configuration) relevant to both subsets are set free. A further optimization step, aimed at maximizing the loaded volume, is subsequently performed. If, in the thus obtained solution, the loaded volume has been increased, the current abstract configuration is upgraded correspondingly. Otherwise, the best-so-far solution is retrieved. Alternatively, relative position exchanges can be activated among a subset of non-loaded items only, in order to perturb the current abstract configuration.

The Hole-filling module has the scope of incrementing the loaded volume, by exploiting the empty spaces still available. For this purpose, a subset of unloaded items is selected. All relative positions (corresponding to the current abstract configuration), relevant to them are set free and a further optimization step performed (to maximize the loaded volume). Again, the current abstract configuration is upgraded only if an improvement has been obtained with the new solution.

The four modules discussed above can be activated repeatedly, following different strategies (e.g., the Initialization itself could, time after time, be executed also during the process, with the imposition of “partial” abstract configurations, restricted to subsets of items already loaded). In the following, the use of the general MILP model of Sect. 4.2, corresponding to each phase, is illustrated.

4.6.2 Use of the General MILP Model

The Initialization module, in the version considered here, focuses on the use of a specific LP-relaxation of the general MILP model of Sect. 4.2. As the relevant sub-problem is expressed in terms of feasibility, all variables χ i (\( \forall i\in I \)) are set to 1. The l βhi variables, introduced in Sect. 4.2, are reconsidered instead. These are not defined any longer as \( {l}_{\beta hi}={\displaystyle \sum_{\omega \in \Omega}{L}_{\omega \beta hi}{\vartheta}_{\omega i}} \), but simply as continuous variables subject to the following bounds:

$$ \forall \beta \in B,\forall i\in I,\forall h\in {C}_i {L}_{1hi}\le {l}_{\beta hi}\le {L}_{3hi}. $$
(4.27)

Here, as previously specified, L 1hi and L 3hi represent the sides associated with h, of minimum and maximum length, respectively. The non-intersection conditions (4.5-1) and (4.5-2) and the objective function (4.9) are rewritten as follows:

$$ \forall \beta \in B,\forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.28-1)
$$ {w}_{\beta 0hi}-{w}_{\beta 0kj}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({l}_{\beta hi}+{l}_{\beta kj}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{+}\right), $$
$$ \forall \beta \in B,\forall i,j\in I/i<j,\forall h\in {C}_i,\forall k\in {C}_j $$
(4.28-2)
$$ {w}_{\beta 0kj}-{w}_{\beta 0hi}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({l}_{\beta hi}+{l}_{\beta kj}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{-}\right), $$
$$ max{\displaystyle \sum_{i\in I,h\in {C}_i}\frac{V_{hi}}{{\displaystyle \sum_{\alpha \in A}{L}_{\alpha hi}}}{\displaystyle \sum_{\beta \in B}{l}_{\beta hi}}}. $$
(4.29)

If the sub-problem related to the model above is infeasible, then all lower bounds L 1hi (in 4.27) are subsequently reduced until a feasible solution is obtained. The variables \( {\sigma}_{\beta hkij}^{+/-} \), for which in the obtained solution \( {\sigma}_{\beta hkij}^{+/-}=1 \), directly provide an abstract configuration for the subsequent steps of the heuristic procedure. They are referred to as \( {\tilde{\sigma}}_{\beta hkij}^{+/-} \).

The Packing, Item-exchange, and Hole-filling modules exploit, totally or partially, the currently available abstract configuration. The non-intersection inequalities (4.5-1) and (4.5-2) corresponding to the above-mentioned \( {\tilde{\sigma}}_{\beta hkij}^{+/-} \) variables are maintained in the model (in addition to (4.6)), whilst the others are eliminated together with all the redundant \( {\sigma}_{\beta hkij}^{+/-} \) variables (i.e., those that are not correlated to any \( {\tilde{\sigma}}_{\beta hkij}^{+/-} \)). The non-intersection constraints, relative to the (thus “imposed”) abstract configuration, are hence rewritten, for the relevant indexes, in the following form:

$$ {w}_{\beta 0hi}-{w}_{\beta 0kj}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{+}\right), $$
(4.30-1)
$$ \underset{\bar{\mkern6mu}}{\vee } $$
$$ {w}_{\beta 0kj}-{w}_{\beta 0hi}\ge \frac{1}{2}{\displaystyle \sum_{\omega \in \Omega}\left({L}_{\omega \beta hi}{\vartheta}_{\omega i}+{L}_{\omega \beta kj}{\vartheta}_{\omega j}\right)}-{D}_{\beta}\left(1-{\sigma}_{\beta hkij}^{-}\right) $$
(4.30-2)
$$ {\sigma}_{\beta hkij}^{+/-}\ge {\chi}_i + {\chi}_j-1, $$
(4.31)

with \( {\sigma}_{\beta hkij}^{+/-}\in \left[0,1\right] \) (i.e. they are no longer considered as binary variables).

4.7 Conclusion

Non-standard packing problems that involve non-box-shaped items and domains, in the presence of additional constraints, are usually very tough to solve. This chapter, extending the author’s previous work, discusses the issue of placing tetris-like items orthogonally into a convex domain. A Global Optimization point of view, focused on MILP/MINLP formulations, is looked into for the purpose of providing models that are suitable for treating additional loading restriction rules and global conditions such as balancing.

An efficient heuristic procedure, aimed at finding satisfactory solutions to real-world instances, is proposed. This approach will be the objective of future investigation, focused on the MILP/MINLP search strategies.

The issue of covering irregularly shaped objects with tetris-like items consisting of a given number of components of minimum total volume, itself, leads to a non-trivial optimization problem. Insights on its two-dimensional version, relevant to the optimal outer approximation of polygons, are provided. A further contribution appearing in this book is dedicated to the computational aspects relevant to the MILP model discussed in this chapter.