Consecutive ones matrices for multi-dimensional
orthogonal packing problems

Cédric Joncour, Arnaud Pêcher

► To cite this version:

Cédric Joncour, Arnaud Pêcher. Consecutive ones matrices for multi-dimensional orthogonal packing problems. Journal of Mathematical Modelling and Algorithms, 2012, Journal of Mathematical Modelling and Algorithm, 11 (1), pp.23-44. 10.1007/s10852-011-9167-z. hal-00652574

HAL Id: hal-00652574

https://inria.hal.science/hal-00652574v1

Submitted on 15 Dec 2011

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY-SA 4.0 - Attribution - ShareAlike - International
License
# Consecutive ones matrices for multi-dimensional orthogonal packing problems *

Cédric Joncour · Arnaud Pêcher

Received: 1 July, 2010 / Accepted: ???

**Abstract** The multi-dimensional orthogonal packing problem (2d-OPP) is a well studied decisional problem. Given a set of items with rectangular shapes, the problem is to decide whether there is a non-overlapping packing of these items in a rectangular bin. The rotation of items is not allowed. A powerful characterization of packing configurations by means of interval graphs was recently introduced. In this paper, we propose a new algorithm using consecutive ones matrices as data structure. This new algorithm is then used to solve the two-dimensional orthogonal knapsack problem. Computational results are reported, which show its effectiveness.

**Keywords** orthogonal packing problem · interval graph · consecutive ones matrices

## 1 Introduction

The two-dimensional orthogonal packing problem (2d-OPP) is a well studied NP-hard optimization problem [16, 21, 27]. Given a set of items $\mathcal{I}$ with rectangular shapes (each item $i \in \mathcal{I}$ has a width $w_i$ and an height $h_i$), the problem is to decide whether the set of items is feasible, that is whether there is a non-overlapping packing in a rectangular bin of width $W$ and height $H$. Rotation of items is not allowed (see Figure 1). The two-dimensional orthogonal knapsack problem (2d-OKP) is to compute the maximum value of a feasible set: if every item $i \in \mathcal{I}$ has a positive value $p_i$, the aim is to exhibit a feasible subset of items $\mathcal{I}' \subset \mathcal{I}$ such that $\sum_{i \in \mathcal{I}'} p_i$ is maximal (see Figure 1).

Many authors gave MIP formulations introducing a discretization of the space [3, 11, 4, 7], or relying on the relative position of items [10, 23, 24, 25]. Caprara and Monaci [8] gave a comparative study of several Branch & Bound algorithms solving strip packing problem. Baldacci and Boschetti proposed a cutting plane approach to solve this problem [1]. Constraint programming was also used to provide exact algorithms [5, 6, 15, 22, 25, 26]. Dual feasible functions were also used by several authors (see [14] for a recent survey).

We consider the *D*-dimensional orthogonal packing problem and the *D*-dimensional orthogonal knapsack problem (with $D \ge 2$). Fekete and Schepers [18, 19] introduced a new approach using graph theory. Their algorithm is one of the fastest, even in the two dimensional case. They used some tuple of interval graphs as data structures to store a feasible packing. Though Fekete and Schepers’ algorithm is very efficient, there are still symmetry issues. We propose a new algorithm using some consecutive ones matrices as data structures, due to Fulkerson and Gross’s characterization of interval graphs. Our approach is able to eliminate some of these symmetry issues.

This paper is organized as follows. In the first section, we introduce the model used to check if a set of items has a feasible packing. We describe also the algorithm to check feasibility and we exhibit several optimizations to handle symmetry issues. In the second section, we describe how the knapsack problem is solved, and give computational results with respect to standard benchmarks.

<footnote>* This research was partially supported by the ANR Project GraTel ANR-blan-09-blan-0373-01, 2010-2012.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: A feasible selection of items for 2d-OKP with $p_i = 1, \forall i \in \mathcal{I}$</figcaption></figure>

## 2 A new algorithm to solve orthogonal packing

### 2.1 Consecutive ones matrices for orthogonal packing

Let $n$ denote the number of items and $D$ be the dimension of the Euclidean space. Let $\mathcal{I} = \{1, \dots, n\}$ be a set of items. For every $d \in \{1, \dots, D\}$ and $i \in \mathcal{I}$, let $w_i^d$ be the width of item number $i$ w.r.t. dimension $d$. For every $d \in \{1, \dots, D\}$, let $W^d$ be the width of the bin w.r.t. dimension $d$. The set of items $\mathcal{I}$ is feasible (see Figure 1) if there is a tuple of coordinates $(x_i^1, \dots, x_i^D) \in \mathbb{R}_D^+$ for every item $i \in \mathcal{I}$ such that:

$$ \forall i \in \mathcal{I}, \forall d \in \{1, \dots, D\} : x_i^d + w_i^d \le W^d, \quad (1) $$

$$ \forall i, j \in \mathcal{I} (i \neq j), \exists d \in \{1, \dots, D\} : [x_i^d, x_i^d + w_i^d] \cap [x_j^d, x_j^d + w_j^d) = \emptyset. \quad (2) $$

We denote by feasible packing, a set of tuple of coordinates of a feasible set of items satisfying the constraints (1) and (2). A feasible packing verifies touching assumption if every item is immediately to the "right" of an other item or touches the "left border" (w.r.t. every dimension):

$$ x_i^d \in \{0\} \cup \{x_j^d + w_j^d : j \in \mathcal{I} \setminus \{i\}\}, \quad \forall i \in \mathcal{I}, d \in \{1, \dots, D\}. \quad (3) $$

**Lemma 1** For every feasible set of items $\mathcal{I}$, there is an associated feasible packing which verifies touching assumption.

*Proof* Let $(x_i^1, \dots, x_i^D)_{i \in \mathcal{I}} \in \mathbb{R}_D^+$ be a feasible packing associated to the set of items $\mathcal{I}$, which does not satisfy touching assumption. There is an item $i \in \mathcal{I}$ and $d \in \{1, \dots, D\}$ such that:

$$ x_i^d \notin \{0\} \cup \{x_j^d + w_j^d : j \in \mathcal{I} \setminus \{i\}\}. $$

Let $\tilde{x}_i^d = \max\{x_j^d + w_j^d : j \in \mathcal{I}, x_j^d + w_j^d \le x_i^d\}$. And, for every $(d', i') \neq (d, i)$ $(d' \in \{1, \dots, D\}, i' \in \mathcal{I})$, let $\tilde{x}_i^{d'} = x_i^{d'}$. Let us check that $(\tilde{x}_i^d, \dots, \tilde{x}_i^D)_{j \in \mathcal{I}}$ is a feasible packing associated to $\mathcal{I}$.

We have, for every $(d', i')$, $\tilde{x}_i^{d'} + w_i^{d'} \le x_i^{d'} + w_i^{d'} \le W^d$. Hence the constraint (1) is valid for these new coordinates.

It remains to check property (2). $\forall i' \in \mathcal{I} (i' \neq i)$, we have to prove that there is $d' \in \{1, \dots, D\}$ such that $[\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) \cap [\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) = \emptyset$. But, for every $i' \in \mathcal{I} (i' \neq i)$, there is $d'$ such that $[x_i^{d'}, x_i^{d'} + w_i^{d'}) \cap [x_i^{d'}, x_i^{d'} + w_i^{d'}) = \emptyset$. So,

- If $d' \neq d$, then $[\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) \cap [\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) = \emptyset$ because $\tilde{x}_i^{d'} = x_i^{d'}$.

- For $d' = d$, we have $x_i^{d'} + w_i^{d'} \le x_i^{d'}$ or $x_i^{d'} + w_i^{d'} \le x_i^{d'}$.

- If $x_i^{d'} + w_i^{d'} \le x_i^{d'}$, then $\tilde{x}_i^{d'} + w_i^{d'} = x_i^{d'} + w_i^{d'} \le \max\{x_j^{d'} + w_j^{d'} : j \in \mathcal{I}, x_j^{d'} + w_j^{d'} \le x_i^{d'}\} = \tilde{x}_i^{d'}$.

- If $x_i^{d'} + w_i^{d'} \le x_i^{d'}$, then $\tilde{x}_i^{d'} + w_i^{d'} \le x_i^{d'} + w_i^{d'} \le x_i^{d'} = \tilde{x}_i^{d'}$.

Therefore, $[\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) \cap [\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'}) = \emptyset$, for all $i' \in \mathcal{I} (i' \neq i)$. Furthermore, for every $i', i'' \in \mathcal{I} \setminus \{i\}$, we have $[\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'} \cap [\tilde{x}_i^{d'}, \tilde{x}_i^{d'} + w_i^{d'} = \emptyset$. Hence the constraint (2) is satisfied. Thus $(\tilde{x}_i^1, \dots, \tilde{x}_i^D)_{i \in \mathcal{I}}$ is a feasible packing associated to $\mathcal{I}$ with one item less not satisfying touching assumption than $(x_i^1, \dots, x_i^D)_{i \in \mathcal{I}}$. By iterating, we build this way a feasible packing associated to $\mathcal{I}$ satisfying touching assumption. $\square$

<footnote n="118">118 Route de Narbonne, 31062 Toulouse Cedex 9, France
E-mail: arnaud.pecher@irit.fr</footnote>
Let $G = (V, E)$ be a simple undirected graph. A stable set of $G$ is a subset of $V$ such that every pair of vertices are not adjacent. For every vertex $i \in V$, let $w_i \in \mathbb{R}$ be its weight. The weighted stability number $\alpha(G, w)$ of $G$ is the maximal sum of weights of a stable set. Given a finite multi-set of intervals of $\mathbb{R}$, an interval graph $G = (V, E)$ is an undirected graph such that each interval corresponds to a vertex of the graph, and two vertices are adjacent if and only if the corresponding intervals overlap.

Following Fekete and Schepers [18, 19], a packing class is a collection of $D$ graphs $G_1, \dots, G_D$ with (shared) vertex set $\mathcal{I}$ and edge sets $E(G_d)$ such that:

P1: for every $d \in \{1, \dots, D\}$, $G_d$ is an interval graph,

P2: for every $d \in \{1, \dots, D\}$, for every stable set $S$ of $G_d$, $\sum_{s \in S} w_s^d \le W^d$ (equivalently $\alpha(G_d, w^d) \le W^d$),

P3: $\bigcap_{d \in \{1, \dots, D\}} E(G_d) = \emptyset$.

See Figure 2, for an illustration of the relationship between a feasible packing and a packing class.

<figure><img src="image_3.png" /><figcaption>Fig. 2: A Fekete & Schepers' packing class with respect to a 2d-packing</figcaption></figure>

Therefore to check whether a set of items is feasible, the algorithm of Fekete and Schepers enumerates all packing classes associated to $\mathcal{I}$. However, in some cases, there are distinct packings of a feasible set of items whose associated packing classes are different (see Figure 3). Hence there are still symmetry issues in this model. Furthermore Ferreira and Oliveira [20] noticed that some so-called degenerated packing classes are unnecessarily enumerated by Fekete and Schepers' algorithm.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Symmetry issues in Fekete & Schepers' model</figcaption></figure>

A binary matrix $M \in \mathcal{M}_{n,m}(\mathbb{I})$ has the consecutive ones property if for every row $i$ and $k \le k'$, $M_{ik} = 1$ and $M_{ik'} = 1$ implies $M_{il} = 1$ for all $k \le l \le k'$ (for every row, the set of 1s occur consecutively).

If $v$ and $w$ are two binary vectors of same size, we write $v > w$, if $v$ is of lexicographic order greater or equal than $w$. Let $M'$ and $M''$ be two matrices in $\mathcal{M}_{n,m}(\mathbb{I})$. $M' > M''$ if $\exists l \in \{1, \dots, m\}$ such that $\forall k < l, Q_k' = Q_k''$ and $Q_l' > Q_l''$. We write $M' \sim M''$, if they have the same set of column vectors ($M''$ can be obtained from $M'$ by permuting columns). In this case, $M'$ and $M''$ are said to be equivalent.
Let $G$ be a graph with $n$ vertices ($\mathcal{V} = \{1, \dots, n\}$) and $m$ maximal cliques $Q_1, \dots, Q_m$. A matrix $M \in \mathcal{M}_{n,m}(\mathbb{B})$ is a vertex/clique matrix of $G$ if for every $1 \le i \le n$ and $1 \le k \le m$, the vertex $i$ belongs to the maximal clique $Q_k$ if and only if $M_{ik} = 1$ (see Example 3), that is each column is the characteristic vector of a maximal clique.

We are now ready to state Fulkerson and Gross’ characterization of interval graphs:

**Theorem 2 (Fulkerson and Gross (1965))** A graph $G$ is an interval graph if and only if there is a vertex/clique matrix of $G$ which has the consecutive ones property.

**Example 3** Let $G$ be the interval graph with the interval graph representation as depicted on the left part of the figure below. Then the matrix as defined on the right part is a vertex/clique matrix of $G$, which has the consecutive ones property.

<figure><img src="image_5.png" /></figure>

Without loss of generality, let $\mathcal{I}$ be a set of items and $\forall d \in \{1, \dots, D\}$, let $m^d \le n$. From now on, for every $d \in \{1, \dots, D\}$, let $M^d \in \mathcal{M}_{n,m^d}(\mathbb{B})$ be a matrix with the consecutive ones property. $\forall k \in \{1, \dots, m^d\}$, let $Q_k^d = \{i \in \mathcal{I} : M_{ik}^d = 1\}$ be the set of items in column $k$ and let $C_k^d \in \mathbb{B}^n$ be the column $k$ of matrix $M^d$ ($C_k^d$ is the characteristic vector of $Q_k^d$); a column $C_k^d$ is said to be maximal if $Q_k^d$ is not included in $Q_l^d$ for every $l \ne k$. Let $Q_{m^d+1}^d = \emptyset$ and $\mathcal{D}^d = \{Q_1^d, \dots, Q_{m^d}^d\}$. We define the width $\lambda_k^d$ of $Q_k^d$ by:

$$ \lambda_k^d = \max_{i \in \mathcal{I}, i \notin Q_{k-1}^d} \left\{ w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d \right\}. \quad (4) $$

A strip decomposition associated to $\mathcal{I}$ is a D-tuple of consecutive ones matrices $(M^1, \dots, M^D) \in \mathcal{M}(\mathbb{B})$ with non-zero rows such that:

- For every dimension $d \in \{1, \dots, D\}$,

$$ \text{every column of } M^d \text{ is maximal,} \quad (5) $$

$$ \forall i \in \mathcal{I}, \forall k \in \{1, \dots, m^d\} \text{ such that } i \in Q_k^d, \text{ we have } w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d > 0, \quad (6) $$

$$ \sum_{k \in \{1, \dots, m^d\}} \lambda_k^d \le W^d. \quad (7) $$

- For every pair $i, j \in \mathcal{I}$ ($i \ne j$), there is a dimension $d \in \{1, \dots, D\}$ such that:

$$ \forall k \in \{1, \dots, m^d\}, i \notin Q_k^d \text{ or } j \notin Q_k^d. \quad (8) $$

Figure 4 gives an illustration of a strip decomposition and of cliques widths. We have the following basic Lemma, which is useful for some proofs:

**Lemma 4** For every $i \in \mathcal{I}$ and $d \in \{1, \dots, D\}$, $w_i^d \le \sum_{1 \le k \le m^d / i \in Q_k^d} \lambda_k^d$.

*Proof* For every $i \in \mathcal{I}$ and $d \in \{1, \dots, D\}$, let $l \in \{1, \dots, m^d\}$ such that $i \in Q_l^d$ and $i \notin Q_{l+1}^d$.

$$ \text{We have } \lambda_l^d = \max_{j \in \mathcal{I}, j \in Q_l^d} \left\{ w_j^d - \sum_{1 \le k < l / j \in Q_k^d} \lambda_k^d \right\} \ge w_i^d - \sum_{1 \le k < l / i \in Q_k^d} \lambda_k^d. \text{ Hence } w_i^d \le \sum_{1 \le k \le m^d / i \in Q_k^d} \lambda_k^d. \quad \square $$

We now formally establish the link between feasible packings and strip decompositions (see Figure 4 again for an example).
<figure><img src="image_6.png" /><figcaption>Fig. 4: A strip decomposition w.r.t. the first dimension of a 2d-orthogonal packing</figcaption></figure>

**Lemma 5** If we have a feasible packing for $\mathcal{I}$ with touching assumption then there is a strip decomposition associated to $\mathcal{I}$.

*Proof* By Lemma 1, there is an associated feasible packing $(x_i^1, \dots, x_i^D) \in \mathbb{R}_D^+$ for every item $i \in \mathcal{I}$, which satisfies touching assumption. For all $d \in \{1, \dots, D\}$, let $X^d = \{x \in \mathbb{R} : \exists i \in \mathcal{I}, x = x_i^d\}$. Let $m^d = |X^d|$. Write $X^d = \{X_1^d, \dots, X_{m^d}^d\}$ with the convention $X_1^d < \dots < X_{m^d}^d$. Since the feasible packing verifies touching assumption, for every $d \in \{1, \dots, D\}$, $k \in \{2, \dots, m^d\}$, there exists $i \in \mathcal{I}$ such that $X_k^d = x_i^d + w_i^d$. Moreover, $X_1^d = 0$. Let $X_{m^d+1}^d = \max\{x_i^d + w_i^d : i \in \mathcal{I}\}$.

Obviously, for every $d \in \{1, \dots, D\}$, there is a surjective function $\sigma^d: \mathcal{I} \to \{1, \dots, m^d\}$ such that $\forall i \in \mathcal{I}, x_i^d = X_i^d/\sigma^d(i)$. $\forall d \in \{1, \dots, D\}, k \in \{1, \dots, m^d\}$, let $Q_k^d = \{i \in \mathcal{I} | x_i^d \le X_k^d < x_i^d + w_i^d\}$. Let $M^d \in \mathcal{M}_{(n,m^d)}(\mathbb{I})$ be the boolean matrix such that $M_{ik}^d = 1$ if and only if $i \in Q_k^d$.

- $M^d$ has the consecutive ones property. In fact, $\forall i \in \mathcal{I}$, let $k, l \in \{1, \dots, m^d\}$, with $X_k^d \le X_l^d$, such that $i \in Q_k^d$ and $i \in Q_l^d$. Then, by definition, $x_i^d \le X_k^d < x_i^d + w_i^d$ and $x_i^d \le X_l^d < x_i^d + w_i^d$. So, $\forall h \in \{1, \dots, m^d\}$ such that $X_k^d \le X_h^d \le X_l^d$, we have this inequality: $x_i^d \le X_k^d \le X_h^d \le X_l^d < x_i^d + w_i^d$. So, $i \in Q_h^d$. Thus $M^d$ verifies the consecutive ones property.

- Let us check that every column of $M^d$ is maximal. Let $1 \le k < k' \le m^d$ and $C_k^d$ (resp. $C_{k'}^d$) be the characteristic vector of $Q_k^d$ (resp. $Q_{k'}^d$). Since the feasible packing verifies touching assumption, let $i$ (resp. $i'$) $\in \mathcal{I}$ be an item such that $x_i^d + w_i^d = X_{k+1}^d$ (resp. $x_{k'}^d = X_{k'}^d$). By definition, $X_k^d < X_{k'}^d$. Obviously, $i' \notin Q_k^d$ and $i' \in Q_{k'}^d$. Hence, $Q_{k'}^d \not\subseteq Q_k^d$. Moreover, $X_{k+1}^d \le X_{k'}^d$. Hence, $i \in Q_k^d$ and $i \notin Q_{k'}^d$. Thus, $Q_k^d \not\subseteq Q_{k'}^d$ and so $C_k^d$ is maximal.

- $\forall d \in \{1, \dots, D\}, \forall k \in \{1, \dots, m^d\}$, let $\lambda_k^d = \max_{i \in \mathcal{I} \atop i \notin Q_{k+1}^d} \left\{ w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d \right\}$.

Let $\mathcal{I}_k^d = \{i \in \mathcal{I} | x_i^d \le X_k^d < x_i^d + w_i^d \le X_{k+1}^d\} = \{i \in \mathcal{I} / i \in Q_k^d, i \notin Q_{k+1}^d\}$. As, the feasible packing verifies touching assumption, we have $X_k^d = \max_{i \in \mathcal{I}_k^d} \{x_i^d + w_i^d\}$ for $k \in \{2, \dots, m^d\}$.

Let us show by induction that $\lambda_k^d = X_{k+1}^d - X_k^d > 0$, $\forall k \in \{1, \dots, m^d\}$.

$$ \text{For } k = 1, \lambda_1^d = \max_{i \in \mathcal{I}_k^d} \{w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d\} = \max_{i \in \mathcal{I}_k^d} \{w_i^d\} = X_2^d - X_1^d > 0. $$
$$
\begin{align*}
. \quad \text{For } k \ge 2, \lambda_k^d &= \max_{i \in \mathcal{I}_k^d} \left\{ w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d \right\} \\
&= \max_{i \in \mathcal{I}_k^d} \left\{ w_i^d - \sum_{1 \le l < k / i \in Q_l^d} (X_l^d - X_{l+1}^d) \right\} \quad \text{by induction hypothesis} \\
&= \max_{i \in \mathcal{I}_k^d} \{w_i^d + X_{\sigma^d(i)}^d - X_k^d\} = \max_{i \in \mathcal{I}_k^d} \{x_i^d + w_i^d\} - X_k^d = X_{k+1}^d - X_k^d > 0.
\end{align*}
$$

So, $\forall d \in \{1, \dots, D\}$:

$$
\sum_{k \in \{1, \dots, m^d\}} \lambda_k^d = \sum_{k \in \{1, \dots, m^d\}} (X_{k+1}^d - X_k^d) = X_{m^d+1}^d - X_1^d = \max\{x_i^d + w_i^d : i \in \mathcal{I}\} \le W^d.
$$

$$
\begin{align*}
. \quad \forall k \in \{1, \dots, m^d\}, \forall i \in \mathcal{I}_k^d, w_i^d - \sum_{1 \le l < k / i \in Q_l^d} \lambda_l^d &= w_i^d - \sum_{1 \le l < k / i \in Q_l^d} (X_l^d - X_{l+1}^d) \\
&= w_i^d + X_{\sigma^d(i)}^d - X_k^d = x_i^d + w_i^d - X_k^d > 0.
\end{align*}
$$

- Since we have a feasible packing, due to the constraint (2), we get $\forall i, j \in \mathcal{I} (i \neq j)$, $\exists d \in \{1, \dots, D\} : [x_i^d, x_i^d + w_i^d] \cap [x_j^d, x_j^d + w_j^d] = \emptyset$. Hence, $x_i^d + w_i^d \le x_j^d$ or $x_j^d + w_j^d \le x_i^d$. Thus, $\forall k \in \{1, \dots, m^d\}$, by definition of $Q_k^d$, $i \notin Q_k^d$ or $j \notin Q_k^d$.

Therefore $(M^1, \dots, M^D)$ is a strip decomposition associated to $\mathcal{I}$.

☐

We now prove the converse:

**Lemma 6** If we have a strip decomposition associated to $\mathcal{I}$ then there is a feasible packing for $\mathcal{I}$ with touching assumption.

*Proof* Let a D-tuple $(M^1, \dots, M^d)$ of matrix which verify strip decomposition conditions. $\forall d \in \{1, \dots, D\}, \forall i \in \mathcal{I}$, let $f_i^d$ (resp. $l_i^d$) $\in \{1, \dots, m^d\}$ be the smallest (resp. biggest) index $k \in \{1, \dots, m^d\}$ such that $M_{ik}^d = 1$.

Let $x_i^d = \sum_{k \in \{1, \dots, f_i^d - 1\}} \lambda_k^d$, $\forall d \in \{1, \dots, D\}, \forall i \in \mathcal{I}$. We have to verify that the set of coordinates $x_i^d$ defines a feasible packing.

$$
- \forall d \in \{1, \dots, D\}, \forall i \in \mathcal{I}, x_i^d + w_i^d = \sum_{k \in \{1, \dots, f_i^d - 1\}} \lambda_k^d + w_i^d \le \sum_{k \in \{1, \dots, f_i^d - 1\}} \lambda_k^d + \sum_{k \in \{f_i^d, \dots, f_i^d\}} \lambda_k^d \le W^d.
$$

Hence the constraint (1) is satisfied.

- $\forall i, j \in \mathcal{I} (i \neq j)$, it exists $d \in \{1, \dots, D\}$ such that $\forall k \in \{1, \dots, m^d\}$, $i \notin Q_k^d$ or $j \notin Q_k^d$. As, $M^d$ is a consecutive ones matrix, then, $l_i^d < f_i^d$ or $f_j^d < l_j^d$. So, $x_i^d + w_i^d \le x_j^d$ or $x_j^d + w_j^d \le x_i^d$. Thus the constraint (2) is satisfied.

- It remains to check that the touching assumption holds. $\forall d \in \{1, \dots, D\}, i \in \mathcal{I}, x_i^d = \sum_{k \in \{1, \dots, f_i^d - 1\}} \lambda_k^d$. Let $j =$

$$
\underset{i' \in \mathcal{I} \atop i' \notin Q_{f_i^d-1}^d}{\operatorname{argmax}} \left\{ w_{i'}^d - \sum_{1 \le l < f_{i'}^d - 1 / i' \in Q_l^d} \lambda_l^d \right\}.
$$

$$
\text{So, } \lambda_{f_i^d-1}^d = w_j^d - \sum_{1 \le l < f_i^d - 1 / j \in Q_l^d} \lambda_l^d. \text{ Thus, } w_j^d = \sum_{f_j^d \le l < f_i^d - 1} \lambda_l^d. \text{ So, } x_i^d = \sum_{k \in \{1, \dots, f_j^d - 1\}} \lambda_k^d + \sum_{k \in \{f_j^d, \dots, f_i^d - 1\}} \lambda_k^d = x_j^d + w_j^d.
\hfill \square
$$

☐

2.2 The algorithm to check feasibility

Due to Lemmas 5 and 6, to check feasibility, we only have to design an algorithm which returns whether there
is a strip decomposition associated to the set of items $\mathcal{I}$. We proceed dimension by dimension, by enumerating all
consecutive ones matrices which satisfy the strip decomposition constraints (5), (6), (7) and (8).

The core of the recursion to enumerate consecutive ones matrices is described in Algorithm 1. Notice that the number of columns of a matrix of a strip decomposition is at most *n* (the number of items), but we do not know it when we are looking for a strip decomposition. Therefore our algorithm enumerates square *n* × *n*-matrices, such that there is an index *m* implying all columns with index at most *m* are maximal, and the remaining ones are 0 columns.

By applying algorithm 1, we consider at this stage only one dimension, and this is a main point of our approach: almost all the work is done in first dimension.
To ensure that constraint (8), is satisfied, we proceed like this: for every dimension $d \in \{1, ..., D-1\}$, let $S_d$ denote the set of all matrices output by Algorithm 1 w.r.t. dimension $d$. Then for the last dimension $d = D$, for every $(D-1)$-tuple of matrices $(M^1, ..., M^{D-1}) \in S_1 \times ... \times S_{D-1}$, we look for a consecutive ones matrix by using Algorithm 1, such that constraint (8) is satisfied. If any, we have a strip decomposition, and the set of items is feasible. If we fail to find out such a tuple of matrices, the set of items is not feasible.

## 2.3 Early detection of unfeasibility

Let $\mathcal{I}$ be a feasible set of items. In this subsection, we exhibit additional constraints which are valid for all strip decompositions associated to $\mathcal{I}$. These constraints are used in the algorithm to reduce the enumeration tree of strip decompositions.

**Available width for items which are not packed yet** Assume that the first $k$ columns in Algorithm 1 are set. Every item which has only 0 entries in these columns has to be packed in the remaining columns. Therefore, the following constraint is a valid constraint (see Figure 5).

**Lemma 7** For every $d \in \{1, ..., D\}$ and $k \in \{1, ..., m^d\}$,

$$ \sum_{l \in \{1, ..., k\}} \lambda_l^d + \max_{i \notin \{Q_1^d, ..., Q_k^d\}} w_i^d \le W^d. \qquad (9) $$

*Proof* Indeed, $\forall d \in \{1, ..., D\}$ and $k \in \{1, ..., m^d\}$, $\max_{i \notin \{Q_1^d, ..., Q_k^d\}} w_i^d \le \sum_{l \in \{k+1, ..., m^d\}} \lambda_l^d$. $\square$

**"Height" of the column** In the bi-dimensional case, a maximal clique $Q$ w.r.t. one dimension induces a stable set in the other dimension. Therefore, for every column $Q$, the sum of weights of the items of $Q$ (the "height" of $Q$) can not exceed the size of the container in the other dimension. In $D$ dimensions, we have this valid following constraint:

**Lemma 8** For every $d \in \{1, ..., D\}$ and $k \in \{1, ..., m^d\}$,

$$ \sum_{i \in Q_k^d} \left( \prod_{d' \in \{1, ..., D\} \atop d' \neq d} w_i^{d'} \right) \le \prod_{d' \in \{1, ..., D\} \atop d' \neq d} W^{d'}. \qquad (10) $$

**Require:** (int) $n$, (bool[$n$][$n$]) $mat$

**Ensure:** print all $n \times n$ matrices with consecutive ones property, satisfying strip decompositions constraints (5), (6), and (7), and no 0 row

```
recursion(int row, int column)
1: if column > n + 1 then
2:     return
3: end if
4: if row > n + 1 then
5:     if ((every column of index at most column is maximal) and
6:          (constraints (6) and (7) are satisfied)) then
7:         if number of non empty rows = n then
8:             print matrix mat
9:         else
10:     recurse(1, column+1)
11: end if
12: return
13: end if
14: mat(row, column)=true
15: if mat is still a consecutive ones matrix then
16:     recurse(row+1, column)
17: end if
18: mat(row, column)=false
19: recurse(row+1, column)
```

**Algorithm 1:** recursive generation of consecutive ones matrices satisfying strip decompositions constraints (5), (6), and (7) without 0 rows
<figure><img src="image_7.png" /><figcaption>Fig. 5: Width of item x has to fit in the grey part of the container</figcaption></figure>

Proof Let $d \in \{1, \dots, D\}$ and $k \in \{1, \dots, m^d\}$. Due to Lemma 4,

$$ \sum_{i \in Q_k^d} \left( \prod_{d' \in \{1, \dots, D\} \atop d' \neq d} w_i^{d'} \right) \le \sum_{i \in Q_k^d} \left( \prod_{d' \in \{1, \dots, D\} \atop d' \neq d} \sum_{l \in \{1, \dots, m^{d'}\}} \lambda_l^{d'} \right). $$

Let $\mathcal{L} = \{1, \dots, m^1\} \times \dots \times \{1, \dots, m^{d-1}\} \times \{1, \dots, m^{d+1}\} \times \dots \times \{1, \dots, m^D\}$. For every $i \in \mathcal{I}$ and $d' \in \{1, \dots, D\}$ with $(d' \neq d)$, let $L_i^{d'} = \{l \in \{1, \dots, m^d\} : i \in Q_i^{d'}\}$. Let $\mathcal{L}_i = L_i^1 \times \dots \times L_i^{d-1} \times L_i^{d+1} \times \dots \times L_i^D \subseteq \mathcal{L}$.

Notice that $\mathcal{L}_i$ is not empty since $L_i^{d'} \neq \emptyset$ for every $d' \in \{1, \dots, D\}$ with $d' \neq d$.

Let $P, Q$ and, for every $i \in \mathcal{I}$, $P_i$ be the multivariate polynomials of $\mathbb{R}[X_i \in \mathcal{I}]$ defined by:

$$ Q = \sum_{(l_1, \dots, l_{d-1}, l_{d+1}, \dots, l_D) \in \mathcal{L}} X_{(1,l_1)} X_{(2,l_2)} \dots X_{(d-1,l_{d-1})} X_{(d+1,l_{d+1})} \dots X_{(D,l_D)}, $$

$$ P_i = \sum_{(l_1, \dots, l_{d-1}, l_{d+1}, \dots, l_D) \in \mathcal{L}_i} X_{(1,l_1)} X_{(2,l_2)} \dots X_{(d-1,l_{d-1})} X_{(d+1,l_{d+1})} \dots X_{(D,l_D)}, $$

$$ P = \sum_{i \in Q_i^k} P_i. $$

For every $d' \in \{1, \dots, D\}$ with $(d' \neq d)$, $\forall (l_1, \dots, l_{d-1}, l_{d+1}, \dots, l_D) \in \mathcal{L}$, let the variable $X_{(d',l_{d'})}$ take the value $\lambda_{l_{d'}}^{d'}$ and denote by $P(\lambda)$ (resp. $Q(\lambda)$, $P_i(\lambda)$) the corresponding value of $P$ (resp. $Q$, $P_i$ for every $i \in \mathcal{I}$). By definition, $\forall i, j \in \mathcal{I}$ ($i \neq j$), $\exists d' \in \{1, \dots, D\}$ such that $\forall l \in \{1, \dots, m^{d'}\}$, $i \notin Q_i^{d'}$ or $j \notin Q_j^{d'}$. Hence, for every pair of distinct elements $i, j \in Q_k^d$, we have $\mathcal{L}_i \cap \mathcal{L}_j = \emptyset$. Hence, the polynomial $P$ is an homogeneous polynomial of degree $D-1$ such that all non-zero coefficients are equal to 1.

$$ \sum_{i \in Q_k^d} \left( \prod_{d' \neq d} \sum_{l \in \{1, \dots, m^{d'}\}} \lambda_l^{d'} \right) = \sum_{i \in Q_i^k} P_i(\lambda) = P(\lambda) \le Q(\lambda) = \prod_{d' \neq d} \left( \sum_{l \in \{1, \dots, m^{d'}\}} \lambda_l^{d'} \right) $$

Therefore, the inequality (10) is a valid inequality as for all $d' \in \{1, \dots, D\}$, $\sum_{l \in \{1, \dots, m^{d'}\}} \lambda_l^{d'} \le W^{d'}$. $\square$

Available volume for items which are not packed yet Assume that the first $k$ columns in Algorithm 1 are set. The sum of all items volume which have only 0 entries in these columns has to be packed in the remaining volume. Therefore, the following constraint is a valid constraint (see Figure 6).

**Lemma 9** For every $d \in \{1, \dots, D\}$ and $k \in \{1, \dots, m^d\}$,

$$ \left( \prod_{d' \in \{1, \dots, D\} \atop d' \neq d} W^{d'} \right) \left( \sum_{l \in \{1, \dots, k\}} \lambda_l^{d'} \right) + \sum_{i \in Q_k^d \cap Q_{k+1}^d} \left( \left( w_i^d - \sum_{l \in \{1, \dots, k\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\} \atop d' \neq d} w_i^{d'} \right) \right) + \\ \sum_{i \notin \{Q_1^d, \dots, Q_k^d\}} \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \le \prod_{d' \in \{1, \dots, D\}} W^{d'} \quad (11) $$

Proof Due to Lemma 4, $\forall d \in \{1, \dots, D\}$ and $k \in \{1, \dots, m^d\}$, we have:
$$- \sum_{i \in Q_k^d \cap Q_{k+1}^d} \left( \left( w_i^d - \sum_{l \in \{1, \dots, k\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_{i^{d'}} \right) \right) \le \sum_{i \in Q_k^d \cap Q_{k+1}^d} \left( \left( \sum_{l \in \{k+1, \dots, m^d\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_{i^{d'}} \right) \right) \\ - \sum_{i \notin \{Q_1^d, \dots, Q_k^d\}} \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \le \sum_{i \notin \{Q_1^d, \dots, Q_k^d\}} \left( \left( \sum_{l \in \{k+1, \dots, m^d\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \right)$$

Hence,

$$\sum_{i \in Q_k^d \cap Q_{k+1}^d} \left( \left( w_i^d - \sum_{l \in \{1, \dots, k\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \right) + \sum_{i \notin \{Q_1^d, \dots, Q_k^d\}} \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \le \\ \sum_{i \in \{Q_{k+1}^d, \dots, Q_{m^d}^d\}} \left( \left( \sum_{l \in \{k+1, \dots, m^d\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \right) = \sum_{l \in \{k+1, \dots, m^d\}} \left( \lambda_l^d \left( \sum_{i \in Q_l^d} \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \right)$$

Due to the valid inequality (10), we get

$$\sum_{i \in Q_k^d \cap Q_{k+1}^d} \left( \left( w_i^d - \sum_{l \in \{1, \dots, k\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \right) + \sum_{i \notin \{Q_1^d, \dots, Q_k^d\}} \left( \prod_{d' \in \{1, \dots, D\}} w_i^{d'} \right) \le \\ \left( \sum_{l \in \{k+1, \dots, m^d\}} \lambda_l^d \right) \left( \prod_{d' \in \{1, \dots, D\}} w^{d'} \right)$$

Therefore, the inequality (11) is a valid inequality. □

So, due to lemmas 7, 8, 9, we only have to generate columns satisfying constraints (9), (10) and (11).

<figure><img src="image_8.png" /><figcaption>Fig. 6: Sum of areas of remaining items to be packed can not exceed the area of the grey part of the container</figcaption></figure>

## 2.4 Breaking some symmetry issues

Notice that the first matrix printed by Algorithm 1 is the biggest matrix satisfying strip decomposition constraints without 0 rows, with respect to the lexicographic order (as defined in Section 1). Hence, if during the recursion, we are able to detect that the packing is feasible, then a solution with biggest lexicographic order should have been already found, in which case we can safely stop it and return that the packing is infeasible.

Let us see a small example: assume that in the enumerating process, we are in step 1 below (the star (resp. —) denotes current position (resp. unset positions))

$$\left( \begin{array}{c} 1 \ 0 \ 0 \ - \\ 0 \ 1 \ 0 \ - \\ 0 \ 0 \ \ast \ - \\ 0 \ 0 \ \ - \ - \end{array} \right) \quad \left| \quad \left( \begin{array}{c} 0 \ 1 \ 0 \ - \\ 1 \ 0 \ 0 \ - \\ 0 \ 0 \ \ast \ - \\ 0 \ 0 \ \ - \ - \end{array} \right) \right. \\ \text{step 1} \qquad \text{step 2}$$
Then step 2 must have been visited before by the recursion, hence a feasible solution, if any, should have been found before: in this case, there are no feasible solutions.

By detecting such configurations, this is how we handle symmetry issues. This contributed mainly to our algorithm's efficiency. This subsection is devoted to such breaking symmetries procedures.

Such symmetry issues arise naturally when two items are identical (they have same widths w.r.t. all dimensions), since the corresponding rows may be swapped safely. These symmetry issues are easily dealt with.

Let $M \in \mathcal{M}_{n,m}(\mathbb{I}B)$ be a $0/1$ matrix. For every $1 \le p \le m$ and $1 \le q \le m-p$, we denote by $\text{SM}_{p,q}(M)$ the submatrix $M'$ of $M$ made of the columns numbered from $p$ to $p+q-1$, that is for every $1 \le i \le n$ and $1 \le j \le q$, $M'_{i,j} = M_{i,j+p-1}$.

A submatrix $\text{SM}_{p,q}(M)$ is a block of $M$ if for every $i, j$ such that $M_{i,j} = 1$ and $p \le j \le p+q-1$, we have $M_{i,1} = M_{i,2} = \dots, M_{i,p-1} = 0$ and $M_{i,p+q} = M_{i,p+q+1} = \dots = M_{i,m} = 0$. We denote by $\text{B}_{p,q}(M)$ a submatrix $\text{SM}_{p,q}(M)$ of $M$ which is a block of $M$ (see Figure 7). Roughly speaking with respect to strip decompositions, every item which belongs to a clique of a block can not belong to the cliques outside of the block.

<figure><img src="image_9.png" /><figcaption>Fig. 7: Block $B_{2,2}(M)$</figcaption></figure>

**Lemma 10** Let $(M^1, \dots, M^D)$ be a strip decomposition. For every $d \in \{1, \dots, D\}$ such that $M^d$ has two blocks $B_{p_1,q_1}(M^d)$ and $B_{p_2,q_2}(M^d)$ with $p_1+q_1 \le p_2$ and $B_{p_2,q_2}(M^d) > B_{p_1,q_1}(M^d)$ then there is a matrix $M^d$ such that $M^d > M^d$ and the D-tuple of matrices $(M^1, \dots, M^d, \dots, M^D)$ is an equivalent strip decomposition (see Figure 8).

*Proof* Let $M^d$ be the matrix obtained from $M^d$ by swapping the two blocks $B_{p_1,q_1}(M^d)$ and $B_{p_2,q_2}(M^d)$: the columns $C_k^{id}$ of $M^d$ are given by

$$C_k^{id} = \begin{cases} C_k^d & \text{if } k < p_1 \\ C_{k+p_2-p_1}^d & \text{if } p_1 \le k < p_1+q_2 \\ C_{k+q_1-q_2}^d & \text{if } p_1+q_2 \le k < p_2+q_2-q_1 \\ C_{k+p_1+q_1-p_2-q_2}^d & \text{if } p_2+q_2-q_1 \le k < p_2+q_2 \\ C_k^d & \text{if } p_2+q_2 \le k \end{cases}$$

It is straightforward to check that $(M^1, \dots, M^{id}, \dots, M^D)$ is an equivalent strip decomposition to $(M^1, \dots, M^d, \dots, M^D)$ such that $M^{id} > M^d$. $\square$

Hence, due to Lemma 10, we stop the main recursion when there are two blocks which are not in decreasing lexicographic order (right case in Figure 8).

Notice that given a block, it is possible to permute the columns such that the first column is bigger w.r.t. the lexicographic order than the last one (see Figure 9). We are going to push this argument further to a slightly more general structure than blocks.

A submatrix $\text{SM}_{p,q}(M)$ is an inner block of $M$ if, for every $i, j$, such that $M_{i,j} = 1$ and $p \le j \le p+q-1$, we have $(M_{i,1} = M_{i,2} = \dots = M_{i,p-1} = 0$ and $M_{i,p+q} = M_{i,p+q+1} = \dots = M_{i,m} = 0)$ or $(M_{i,p} = M_{i,p+1}, \dots = M_{i,p+q-1} = 1)$. We denote by $\text{IB}_{p,q}(M)$ a submatrix $\text{SM}_{p,q}(M)$ of $M$ which is an inner block of $M$ (see Figure 10). Roughly speaking with respect to strip decompositions, every item which belongs to a clique of an inner block must belong to all cliques of the inner block or can not belong to the cliques outside of the inner block. An inner block $\text{IB}_{p,q}(M)$ is minimal if $Q_p > Q_{p+q-1}$.

**Lemma 11** Let $(M^1, \dots, M^D)$ be a strip decomposition associated to the set of items $\mathcal{I}$. For every $d \in \{1, \dots, D\}$ such that $M^d$ is an inner block $\text{IB}_{p,q}(M^d)$ not "minimal" then there is a matrix $M^d$ such that $M^d > M^d$ and the D-tuple of matrices $(M^1, \dots, M^d, \dots, M^D)$ is another strip decomposition associated to $\mathcal{I}$ (see Figure 11).
<figure><img src="image_10.png" /><figcaption>Fig. 8: Permuting two blocks gives two equivalent strip decompositions</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 9: Permutation of columns within a block</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 10: Inner block IB<sub>2,2</sub></figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Fig. 11: Permutation of columns within an inner block</figcaption></figure>

*Proof* Let $d \in \{1, \dots, D\}$ such that $M^d$ has an inner block matrix $IB_{p,q}(M^d)$ which is not minimal.

Let $\alpha_{p,q}^d = \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d$ and $\beta_{p,q}^d = \sum_{k \in \{1, \dots, p+q-1\}} \lambda_k^d$. For every item $i \in \mathcal{I}$ and for every $\delta \in \{1, \dots, D\}$, let $f_i^\delta$ (resp. $l_i^\delta \in \{1, \dots, m^\delta\}$ be the smallest (resp. biggest) index $k \in \{1, \dots, m^\delta\}$ such that $M_{i,k}^\delta = 1$; and let $x_i^\delta = \sum_{k \in \{1, \dots, f_i^\delta-1\}} \lambda_k^\delta$.

According to the proof of Lemma 6, $(x_i^1, \dots, x_i^D)_{i \in \mathcal{I}}$ is a feasible packing. We are going to build another feasible packing $(x_i^{l_i^1}, \dots, x_i^{l_i^D})_{i \in \mathcal{I}}$ with $x_i^{l_i^\delta} = x_i^\delta$ whenever $\delta \in \{1, \dots, D\}$ ($\delta \neq d$) and $i \in \mathcal{I}$ such that the associated strip decomposition, as defined in the proof of Lemma 5, has bigger lexicographic order, with respect to dimension $d$:

- $\forall i \in \mathcal{I}$ and $\delta \in \{1, \dots, D\}$ with $\delta \neq d$, let $x_i^{l_i^\delta} = x_i^\delta$.

- $\forall i \in \mathcal{I}$ such that $f_i^d < p$ or $l_i^d > p+q-1$, let $x_i^{l_i^d} = x_i^d = \sum_{k \in \{1, \dots, f_i^d-1\}} \lambda_k^d$.

- $\forall i \in \mathcal{I}$ such that $f_i^d \ge p$ and $l_i^d \le p+q-1$, let $x_i^{l_i^d} = \alpha_{p,q}^d + (\beta_{p,q}^d - \sum_{k \in \{1, \dots, l_i^d\}} \lambda_k^d)$. Hence, we have:

$$x_i^{l_i^d} = \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d + \sum_{k \in \{l_i^d+1, \dots, p+q-1\}} \lambda_k^d.$$

Let us check that inequalities (1) with respect to dimension $d$ of a feasible packing are satisfied:

- $\forall i \in \mathcal{I}$ such that $f_i^d < p$ or $l_i^d > p+q-1$, $x_i^{l_i^d} + w_i^d \le W^d$.

- $\forall i \in \mathcal{I}$ such that $f_i^d \ge p$ and $l_i^d \le p+q-1$, due to Lemma (4), we have:

$$x_i^{l_i^d} + w_i^d \le \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d + \sum_{k \in \{l_i^d+1, \dots, p+q-1\}} \lambda_k^d + \sum_{k \in \{f_i^d, \dots, l_i^d\}} \lambda_k^d \le W^d.$$

Let us check that constraints (2) of a feasible packing are satisfied. If $(i, j) \in \mathcal{I}^2$ ($i \neq j$) is a pair of items such that $[x_i^d, x_i^d + w_i^d] \cap [x_j^d, x_j^d + w_j^d) \neq \emptyset$, then there is nothing to prove. Assume that $(i, j) \in \mathcal{I}^2$ ($i \neq j$) is a pair of items such that $[x_i^d, x_i^d + w_i^d] \cap [x_j^d, x_j^d + w_j^d) = \emptyset$. We are going to show that $[x_i^{l_i^d}, x_i^{l_i^d} + w_i^d] \cap [x_j^{l_j^d}, x_j^{l_j^d} + w_j^d) = \emptyset$ (which implies that constraint (2) is satisfied for the pair $(i, j)$). There are four cases:

- If $(f_i^d < p$ or $l_i^d > p+q-1)$ and $(f_j^d < p$ or $l_j^d > p+q-1)$ then $x_i^{l_i^d} = x_i^d$ and $x_j^{l_j^d} = x_j^d$. Thus $[x_i^{l_i^d}, x_i^{l_i^d} + w_i^d] \cap [x_j^{l_j^d}, x_j^{l_j^d} + w_j^d) = \emptyset$.

- If $(f_i^d \ge p, l_i^d \le p+q-1)$ and $(f_j^d < p)$ then $x_j^{l_j^d} + w_j^d \le x_i^d$. By definition of an inner block, we have $l_j^d < p$. Thus, due to Lemma (4), we have:

$$x_j^{l_j^d} + w_j^d = x_j^d + w_j^d \le \sum_{k \in \{1, \dots, f_j^d-1\}} \lambda_k^d + \sum_{k \in \{f_j^d, \dots, l_j^d\}} \lambda_k^d \le \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d \le x_i^{l_i^d}.$$
- If ($f_i^d \ge p$, $l_i^d \le p+q-1$) and ($l_j^d > p+q-1$) then $x_i^d \ge x_i^d + w_i^d$. By definition of an inner block, we have $f_j^d > p+q-1$. Thus, due to Lemma (4), we have:

$$x_j^d = x_j^d \ge \sum_{k \in \{1, \dots, f_j^d - 1\}} \lambda_k^d \ge \sum_{k \in \{1, \dots, p+q-1\}} \lambda_k^d \ge x_i^d + w_i^d.$$

- If ($f_i^d \ge p$, $l_i^d \le p+q-1$) and ($f_j^d \ge p$, $l_j^d \le p+q-1$). We suppose $x_j^d + w_j^d \le x_i^d$, then $l_j^d < f_i^d$. Due to Lemma (4), we have:

$$x_i^d + w_i^d \le \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d + \sum_{k \in \{l_i^d+1, \dots, p+q-1\}} \lambda_k^d + \sum_{k \in \{f_i^d, \dots, l_i^d\}} \lambda_k^d \\ \le \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d + \sum_{k \in \{l_j^d+1, \dots, p+q-1\}} \lambda_k^d \le x_j^d.$$

Therefore, $(x_i^1, \dots, x_i^{l_i^D})_{i \in \mathcal{I}}$ is a feasible packing. From Lemma 1, we get a feasible packing $(x_i^{1'}, \dots, x_i^{l_i^D})_{i \in \mathcal{I}}$ with the touching assumption, such that $x_i^\delta = x_i^{\delta'}$ for all $i \in \mathcal{I}$, whenever $\delta \neq d$. As defined in the proof of Lemma 5, we have an associated strip decomposition $(M^1, \dots, M^{d'}, \dots, M^D)$. The first $p-1$ columns of $M^{d'}$ are identical to $M^d$ (as the coordinates of the first items are identical). By hypothesis, $Q_{p+q-1}^d > Q_p^d$. Let $a$ (resp. $b$) be the smallest item such that $M_{a,p}^d = 1$ and $M_{a,p+q-1}^d = 0$ (resp. $M_{b,p}^d = 0$ and $M_{b,p+q-1}^d = 1$). Due to the definition of inner block, $l_b^d = p+q-1$ and so $x_b^{d'} = \sum_{k \in \{1, \dots, p-1\}} \lambda_k^d = x_a^d$. According to the touching assumption, there is $j \in \mathcal{I}$ such that $x_a^d = x_j^d + w_j^d$. So, $x_b^{d'} = x_j^{d'} + w_j^d$ and thus the item $b$ satisfies touching assumption. Hence $b \in Q_p^{d'}$. Thus, $Q_p^{d'} > Q_p^d$ and $M^{d'} > M_p^d$. $\square$

Hence, due to Lemma 11, we stop the main recursion when there is an inner block which is not minimal (right case in Figure 11).

### 3 The two-dimensional orthogonal knapsack problem

The main benchmarks are devoted to the bi-dimensional orthogonal knapsack problem. Our algorithm only checks if a given set of items admits a feasible packing. Therefore, to run these benchmarks, we used a branch-and-bound algorithm (see subsection 3.1), calling our algorithm to check feasibility.

#### 3.1 Knapsack algorithm

To select a subset of items $\mathcal{I}$ among all items, we use a classical branch-and-bound enumeration of the knapsack problem where the knapsack constraint is that the overall area of the selected items is less or equal than the container's area. For a given selected subset of items, we apply some dual feasible functions in order to try to early detect unfeasibility: a function $f: [0, 1] \to [0, 1]$ is dual feasible (DFF) [17] if for every finite set $S$ of positive real numbers, we have $\sum_{x \in S} x \le 1 \Rightarrow \sum_{x \in S} f(x) \le 1$.

Carlier and Neron introduced discrete dual feasible functions [9], as follows: let $C \in \text{EnsR}^+$, a discrete dual feasible function $f_C$ is a function $f_C: [0, C] \to [0, C']$ (where $C' = f_C(C)$) such that for every finite set $S$ of positive real numbers $\forall S$, $\sum_{x \in S} x \le C \Rightarrow \sum_{x \in S} f_C(x) \le f_C(C) = C'$. They proved the following necessary condition for a subset of items to be feasible.

**Theorem 12** A subset of items $I$ is feasible, only if for every $D$-tuple of discrete feasible function $(f_{W_1}^1, \dots, f_{W_D}^D)$, we have

$$\sum_{i \in I} \left( \prod_{d=1}^{D} f^d(w_i^d) \right) \le \prod_{d=1}^{D} f^d(W^d) \qquad (12)$$

We apply Theorem 12 with the following discrete dual feasible functions ($k=2,3,4$), for every dimension $d$:

$$f_{k,FS,1}^d: [0, W^d] \to [0, kW^d] \qquad f_{k,CCM,1}^d: [0, W^d] \to [0, 2 \lfloor \frac{W^d}{k} \rfloor] \\ x \mapsto \begin{cases} xk, & \text{if } \frac{x(k+1)}{W^d} \in \mathbb{N}, \\ \lfloor \frac{x(k+1)}{W^d} \rfloor, & \text{C, otherwise.} \end{cases} \qquad x \mapsto \begin{cases} 2 \lfloor \frac{W^d}{k} \rfloor - \lfloor \frac{W^d - x}{k} \rfloor, & \text{if } x > \frac{W^d}{2}, \\ \lfloor \frac{W^d}{k} \rfloor, & \text{if } x = \frac{W^d}{2}, \\ \lfloor \frac{x}{k} \rfloor, & \text{if } x < \frac{W^d}{2}. \end{cases}$$
To solve the knapsack problem, we may use a classical solver such as IBM Ilog CPLEX, FICO Xpress or GLPK. This would not improve significantly the computational time as the main issue is to check the feasibility of the packing. Hence we implemented our own knapsack algorithm.

## 3.2 Computational results on standard benchmarks

<table><caption>Table 1: Number of nodes of the knapsack branch-and-bound tree and number of calls to the algorithm checking feasibility</caption><thead><tr><th>Benchmark</th><th>bin size</th><th>nb of items in opt.</th><th>opt. sol.</th><th>JP OKP nodes</th><th>JP OPP calls</th><th>FS OKP nodes</th><th>FS OPP calls</th></tr></thead><tbody><tr><td>ngcut1</td><td>10×10</td><td>5</td><td>164</td><td>23</td><td>13</td><td>19</td><td>1</td></tr><tr><td>ngcut2</td><td>10×10</td><td>5</td><td>230</td><td>74</td><td>19</td><td>5</td><td>0</td></tr><tr><td>ngcut3</td><td>10×10</td><td>7</td><td>247</td><td>29</td><td>19</td><td>25</td><td>6</td></tr><tr><td>ngcut4</td><td>15×10</td><td>6</td><td>268</td><td>7</td><td>6</td><td>1</td><td>0</td></tr><tr><td>ngcut5</td><td>15×10</td><td>6</td><td>358</td><td>8</td><td>7</td><td>1</td><td>0</td></tr><tr><td>ngcut6</td><td>15×10</td><td>7</td><td>289</td><td>38</td><td>26</td><td>15</td><td>5</td></tr><tr><td>ngcut7</td><td>20×20</td><td>8</td><td>430</td><td>8</td><td>8</td><td>0</td><td>0</td></tr><tr><td>ngcut8</td><td>20×20</td><td>8</td><td>834</td><td>67</td><td>62</td><td>53</td><td>23</td></tr><tr><td>ngcut9</td><td>20×20</td><td>11</td><td>924</td><td>21</td><td>18</td><td>3</td><td>0</td></tr><tr><td>ngcut10</td><td>30×30</td><td>6</td><td>1452</td><td>7</td><td>0</td><td>1</td><td>0</td></tr><tr><td>ngcut11</td><td>30×30</td><td>9</td><td>1688</td><td>115</td><td>78</td><td>36</td><td>10</td></tr><tr><td>ngcut12</td><td>30×30</td><td>9</td><td>1865</td><td>210</td><td>46</td><td>48</td><td>14</td></tr><tr><td>gcut1</td><td>250×250</td><td>3</td><td>48368</td><td>69</td><td>18</td><td>33</td><td>0</td></tr><tr><td>gcut2</td><td>250×250</td><td>6</td><td>59798</td><td>2873</td><td>169</td><td>519</td><td>51</td></tr><tr><td>gcut3</td><td>250×250</td><td>6</td><td>61275</td><td>16503</td><td>564</td><td>2234</td><td>235</td></tr><tr><td>gcut4</td><td>250×250</td><td>4</td><td>61380</td><td>310308</td><td>36026</td><td>72159</td><td>18316</td></tr><tr><td>gcut5</td><td>500×500</td><td>5</td><td>195582</td><td>92</td><td>45</td><td>52</td><td>13</td></tr><tr><td>gcut6</td><td>500×500</td><td>4</td><td>236305</td><td>1348</td><td>78</td><td>278</td><td>22</td></tr><tr><td>gcut7</td><td>500×500</td><td>4</td><td>240143</td><td>8471</td><td>207</td><td>852</td><td>124</td></tr><tr><td>gcut8</td><td>500×500</td><td>4</td><td>245758</td><td>313847</td><td>14685</td><td>55485</td><td>9037</td></tr><tr><td>gcut9</td><td>1000×1000</td><td>5</td><td>939600</td><td>75</td><td>10</td><td>12</td><td>2</td></tr><tr><td>gcut10</td><td>1000×1000</td><td>5</td><td>937349</td><td>1176</td><td>88</td><td>335</td><td>31</td></tr><tr><td>gcut11</td><td>1000×1000</td><td>6</td><td>969709</td><td>29446</td><td>1426</td><td>1616</td><td>212</td></tr><tr><td>gcut12</td><td>1000×1000</td><td>5</td><td>979521</td><td>102310</td><td>3096</td><td>8178</td><td>593</td></tr><tr><td>gcut13</td><td>3000×3000</td><td>≥13</td><td>≥8647565</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>cgcut1</td><td>15×10</td><td>8</td><td>244</td><td>44</td><td>11</td><td>14</td><td>1</td></tr><tr><td>cgcut2</td><td>40×70</td><td>12</td><td>2892</td><td>889</td><td>870</td><td>-</td><td>-</td></tr><tr><td>cgcut3</td><td>40×70</td><td>10</td><td>1860</td><td>582</td><td>227</td><td>356</td><td>102</td></tr><tr><td>okp1</td><td>100×100</td><td>11</td><td>27718</td><td>9467</td><td>234</td><td>3244</td><td>661</td></tr><tr><td>okp2</td><td>100×100</td><td>11</td><td>22502</td><td>72855</td><td>27585</td><td>23626</td><td>7310</td></tr><tr><td>okp3</td><td>100×100</td><td>11</td><td>24019</td><td>58161</td><td>8936</td><td>8233</td><td>816</td></tr><tr><td>okp4</td><td>100×100</td><td>10</td><td>32893</td><td>26088</td><td>4227</td><td>1458</td><td>15</td></tr><tr><td>okp5</td><td>100×100</td><td>8</td><td>27923</td><td>-</td><td>-</td><td>5733</td><td>643</td></tr></tbody></table>

The algorithm to check feasibility and the branch-and-bound procedure have been implemented in Java 6 and tested on a PC with a 3GHz Pentium IV processor. Runtimes reported by Fekete & Schepers in [19] were obtained from a similar PC, but their algorithm was developed in C++.

We used classical 2D-OKP benchmarks from [3, 11, 19] and the two dimensional guillotine cutting problems benchmarks from [2, 12]. All these benchmarks are available at

http://www.ibr.cs.tu-bs.de/alg/packlib/instances.shtml

Our binaries and the benchmarks files are also available at

https://wiki.black.inria.fr/realopt/pmwiki.php/Project/SoftwareAlgoKP

In tables 1 and 2, the columns JP (resp. FS, resp BB, resp. A0, A1, A2 and A3) correspond to our algorithm (resp. Fekete & Schepers' algorithm with data reported from [19], resp. Baldacci & Boschetti's algorithm with data reported from [1], resp. Caprara & Monaci's algorithms, as depicted in [8]). Table 1 gives the container sizes, the value of an optimal solution and the number of items of an optimal solution. The number of subset of items to be checked for feasibility (OKP nodes) and the number of effective calls (OPP nodes) to our algorithm to check feasibility (that is after the application of dual feasible functions) are reported.
Table 1 shows that the number of the OKP nodes of our algorithm is bigger than the number of OKP nodes of Fekete and Schepers' algorithm. This is due to the fact that our Branch-and-Bound is less sophisticated than Fekete and Schepers' to select a subset of items to be checked for feasibility. In particular, we do not make use of heuristics to try to guess a solution, in contrary to Fekete & Schepers'.

We report in Table 2 the running times of the algorithms. We also report the number of unsolved benchmarks (within the time limit of 1800 seconds) and the average time (computed on the set of instances *cgcut*, *gcut* and *okp*), with the convention that an unsolved benchmark counts for 1800 seconds. For *ngcut* and *hccut* instances, every algorithm is fast. *cgcut* and *gcut* instances are more difficult to solve, as the size of the container and/or the number of items of an optimal solutions are bigger. On these instances, our algorithm seems to be significantly faster, especially in the case of instances *cgcut2*, *gcut4*, *gcut8* and *gcut12*. This seems to indicate that we handle better symmetry issues due to items of same shape.

Results on the five *okp* instances are less conclusive: Fekete & Schepers' algorithm is faster (with the exception of *okp1*). Notice that on these instances, the number of calls to the algorithm to check feasibility is far much bigger in our case than in Fekete & Schepers'. Hence, as already noticed, Fekete & Scheper's branch-and-bound algorithm to handle the knapsack problem is more efficient. An explanation of this difference is that some symmetry issues are eliminated more efficiently by Fekete and Schepers' algorithm on these instances.

The instance *gcut13* is still open. We were able to provide a feasible solution of value 8647565 (involving 17 items), thus slightly improving Fekete & Schepers's lower bound of value 8622498 [19].

<table><caption>Table 2: Running times (s)</caption><thead><tr><th>Benchmark</th><th>JP</th><th>FS</th><th>BB</th><th>A0</th><th>A1</th><th>A2</th><th>A3</th></tr></thead><tbody><tr><td>ngcut1...ngcut12</td><td>0</td><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>hccut2...hccut4</td><td>0</td><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>cgcut1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>cgcut2</td><td><b>39</b></td><td>>1800</td><td>>1800</td><td>>1800</td><td>>1800</td><td>533</td><td>531</td></tr><tr><td>cgcut3</td><td>0</td><td>0</td><td>95</td><td>23</td><td>23</td><td>4</td><td>4</td></tr><tr><td>gcut1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>gcut2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>25</td><td>0</td></tr><tr><td>gcut3</td><td>0</td><td>4</td><td>2</td><td>>1800</td><td>2</td><td>276</td><td>3</td></tr><tr><td>gcut4</td><td><b>28</b></td><td>195</td><td>46</td><td>>1800</td><td>346</td><td>>1800</td><td>376</td></tr><tr><td>gcut5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>gcut6</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>9</td><td>0</td></tr><tr><td>gcut7</td><td>0</td><td>2</td><td>3</td><td>1</td><td>0</td><td>354</td><td>1</td></tr><tr><td>gcut8</td><td><b>17</b></td><td>255</td><td>186</td><td>1202</td><td>136</td><td>>1800</td><td>108</td></tr><tr><td>gcut9</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>gcut10</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>0</td></tr><tr><td>gcut11</td><td><b>1</b></td><td>8</td><td>3</td><td>16</td><td>14</td><td>>1800</td><td>16</td></tr><tr><td>gcut12</td><td><b>3</b></td><td>109</td><td>12</td><td>63</td><td>16</td><td>>1800</td><td>25</td></tr><tr><td>gcut13</td><td>>1800</td><td>>1800</td><td>>1800</td><td>>1800</td><td>>1800</td><td>>1800</td><td>>1800</td></tr><tr><td>okp1</td><td><b>1</b></td><td>10</td><td>779</td><td>24</td><td>25</td><td>72</td><td>35</td></tr><tr><td>okp2</td><td>477</td><td>20</td><td>288</td><td>>1800</td><td>>1800</td><td>1535</td><td>1559</td></tr><tr><td>okp3</td><td>7</td><td>5</td><td>0</td><td>21</td><td>1</td><td>465</td><td>10</td></tr><tr><td>okp4</td><td>23</td><td>2</td><td>14</td><td>40</td><td>2</td><td>0</td><td>4</td></tr><tr><td>okp5</td><td>>1800</td><td>11</td><td>190</td><td>40</td><td>>1800</td><td>513</td><td>488</td></tr><tr><td># unsolved</td><td>2</td><td>2</td><td>2</td><td>5</td><td>4</td><td>5</td><td>1</td></tr><tr><td>Average time</td><td>200</td><td>200</td><td>248</td><td>496</td><td>369</td><td>609</td><td>239</td></tr></tbody></table>

## 4 Conclusion

In this paper, we gave an exact algorithm to solve the multi-dimensional orthogonal packing problem, which is based upon Fekete & Schepers' characterization of feasible packings by so-called packing classes. This algorithm is used to solve the two-dimensional orthogonal packing problem with two stages: the first stage is a basic branch-and-bound algorithm to select a subset of items and the second stage checks whether this subset of items admits a feasible packing. Our main contribution is for the second stage: to check feasibility, we used consecutive ones matrices as data structures to store feasible packings. In contrary to Fekete & Scheper's approach, by using consecutive ones matrices, we have a partial knowledge of the relative positions of the items and their coordinates. This enabled us to handle some symmetry issues in a close manner to the algorithms of Clautiaux, Moukrim and Carlier [13, 15].

Computer experiments on standard benchmarks show that this new algorithm is competitive. In a companion paper, we investigate the data structure of PQ-trees, as they were designed to store more efficiently the linear consecutive
ordering of the maximal cliques of interval graphs. Another matter of investigation is to derive from this algorithm an efficient mixed integer programming formulation for the multi-dimensional orthogonal knapsack problem. At last, this approach is suitable to solve other problems such as the orthogonal packing problem on a torus, by enumerating circulant consecutive-ones matrices.

References

1. Baldacci R, Boschetti MA (2007) A cutting plane approach for the two-dimensional orthogonal non-guillotine cutting stock problem. European Journal of Operational Research 183(3):1136-1149

2. Beasley JE (1985) Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society 36(4):297-306

3. Beasley JE (1985) An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research 33(1):49-64

4. Beasley JE, Mingozi A (1996) A new formulation for the two-dimensional orthogonal cutting problem. Tech. rep., University of Bologna, Italy

5. Beldiceanu N, Carlsson M (2008) New filtering for the cumulative constraint in the context of non-overlapping rectangles. In: Lecture Notes in Computer Science, CPAIOR08, vol 5015, pp 21-25

6. Beldiceanu N, Carlsson M, Thiel S (2006) Sweep synchronization as a global propagation mechanism. COM 33(10):2835-2851

7. Below G, Scheithauer G (2008) Lower-dimensional bounds and a new model for higher-dimensional orthogonal packing

8. Caprara A, Monaci M (2004) On the two-dimensional knapsack problem. Operations Research Letters 32(1):5-14

9. Carlier J, Néron E (2000) A new lp-based lower bound for the cumulative scheduling problem. European Journal of Operational Research 127:363-382

10. Chen CS, Lee SM, Shen QS (1995) An analytical model for the container loading problem. European Journal of Operational Research 86(1):68-76

11. Christofides N, Hadj constantinou E (1995) An exact algorithm for orthogonal 2-d cutting problems using guillotine cuts. European Journal of Operational Research 83(1):21-38

12. Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Operations Research 25(1):30-44

13. Clautiaux F, Carlier J, Moukrim A (2007) A new exact method for the orthogonal packing problem. European Journal of Operational Research 183(3):1196-1211

14. Clautiaux F, Alves C, de Carvalho JV (2008) A survey of dual-feasible functions and superadditive functions. Annals of Operations Research

15. Clautiaux F, Jouglet A, Carlier J, Moukrim A (2008) A new constraint programming approach for the orthogonal packing problem. Computers and Operations Research 35(3):944-959

16. Dyckhoff H (1990) A typology of cutting and packing problems. European Journal of Operational Research 44(2):145-159

17. Fekete SP, Schepers J (2001) New classes of lower bounds for the bin packing problem. Mathematical Programming 91:11-31

18. Fekete SP, Schepers J (2004) A combinatorial characterization of higher-dimensional orthogonal packing. Mathematics of Operations Research 29(2):353-368

19. Fekete SP, Schepers J, van der Veen J (2007) An exact algorithm for higher-dimensional orthogonal packing. Operations Research 55(3):569-587

20. Ferreira E, Oliveira J (2008) Fekete and Schepers' Graph-based Algorithm for the Two-Dimensional Orthogonal Packing Problem Revisited. Gabler

21. Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of np-completeness

22. Mercier L, v Hentenryck P (2008) Edge finding for cumulative scheduling. IJOC 20(1):143-153

23. Onodera H, Taniguchi Y, Tamaru K (1991) Branch-and-bound placement for building block layout. In: 28th ACM/IEEE design automation conference, pp 433-439

24. Padberg M (2000) Packing small boxes into a big box. Mathematical Methods Operations Research 52(1):1-21

25. Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin packing problem. INFORMS Journal on Computing 19(1):36-51

26. Simonis H, O'Sullivan B (2008) Search strategies for rectangle packing

27. Wäscher G, HauBner H, Schuman H (2007) An improved typology of cutting and packing problems. European Journal of Operational Research 183(3):1109-1130