\documentclass[a4]{article}

%\usepackage[italian]{babel}
%\usepackage[latin1]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{color}
\usepackage[section]{placeins}
%\usepackage{array}
%\usepackage{tabularx}
%\usepackage{rotating}
\usepackage{algorithm}
\usepackage{algorithmic}


\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\K}{\mathcal{K}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\N}{\mathcal{N}}
\renewcommand{\O}{\mathcal{O}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\R}{\mathcal{R}}
\renewcommand{\S}{\mathcal{S}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\Z}{\mathcal{Z}}

%\title{A bi-dimensional level packing problem arising from the optimization of thermal treatment of heat exchangers}

%\author
%{Giovanni Righini, ??\\
%Dipartimento di Informatica \\
%Universit\`a degli Studi di Milano}

\date{}

\textheight = 24cm
\textwidth = 16cm
\hoffset = -2.5cm
\voffset = -3.0cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\maketitle

%\begin{abstract}
%\end{abstract}

%{\em Keywords}: Rectangle packing, Bi-dimensional bin packing, Column generation.
Questo argomento è adatto come progetto d'esame per Complementi di R.O. e come tesi di laurea magistrale.

\section{A bi-dimensional level packing problem arising from the optimization of thermal treatment of heat exchangers}
%\section{Introduction}
Industrial heat exchangers are huge metallic cylinders subject to high reliability requirements.
One of the critical phases in their production is a thermal treatment that implies to cover the cylinder with rectangular patches.
We investigate the resulting optimization problem, where the objective is to use an optimal subset of patches
taken from a ground set of available patches, while complying with some geometrical constraints.
The resulting mathematical model is a variation of the level rectangle packing problem,
an $NP$-hard generalization of the bin packing problem.\\

%{\em Inserire citazioni}\\

%We address the problem with column generation to compute lower bounds,
%while upper bounds are obtained by fast and simple heuristics.\\

%We report on the results of extensive computational tests on randomly generated instances with different characteristics.

\section{Problem description}\label{sec:problem}
The surface of the heat exchanger to be covered is represented by a rectangle of known size: we indicate its width by $W$ and its height by $H$.
A set $\N$ of $N$ types of rectangular patches is available;
each patch type $i \in \N$ is characterized by its unit cost $c_i$, its width $w_i$ and its height $h_i$ and by a number $M_i$ of available patches.
For operational reasons it is required that patches are arranged into adjacent horizontal stripes (levels); we indicate the set of levels by $\L$.
Patches cannot overlap.
A maximum horizontal gap equal to $\delta^W$ is allowed between patches in the same level.
A maximum vertical gap equal to $\delta_H$ is allowed between patches in adjacent levels.

\paragraph{Variables.}
A binary variable $t_{ij}$ indicates whether patches of type $i \in \N$ are used in level $j \in \L$.
An integer non-negative variable $x_{ij}$ indicates how many patches of type $i \in \N$ are arranged into level $j \in \L$.
The height of each level $j \in \L$ is indicated by a continuous non-negative variable $z_j \geq 0$.
Since the number of levels is not a datum, we also use a binary variable $y_j$ to indicate whether each level $j \in \L$ is actually used or not.

\paragraph{Constraints.}
Variables $x$ and $t$ are related by:
\[ x_{ij} <= M_i t_{ij} \ \ \ \forall i \in \N, j \in \L. \]
The number of patches for each type is limited:
\[ \sum_{j \in \L} x_{ij} \leq M_i\ \ \ \forall i \in \N. \]
The sum of the heights of the levels must be equal to the height of the rectangle:
\[ \sum_{j \in \L} z_j = H. \]
Obviously, levels that are not used have zero height:
\[ z_j \leq H y_j\ \ \forall j \in \L. \]
Patches cannot exceed the height of their level:
\[ h_i t_{ij} \leq z_j\ \ \forall i \in \N\ \ \forall j \in \L. \]
Vertical tolerance:
\[ z_j \leq H - (H - h_i - \delta^H) t_{ij}\ \ \forall j \in \L. \]
Horizontal tolerance:
\[ \sum_{i \in \N} w_i x_{ij} \leq W y_j \leq \sum_{i \in \N} (w_i + \delta^W) x_{ij}\ \ \ \forall j \in \L. \]
With this formulation of the last constraints we allow for a maximum gap of $\frac{\delta^W}{2}$ between the patches and the edge of the rectangle.

\paragraph{Objective.}
The objective is to minimize the cost of the patches used:
\[ \text{minimize  } f = \sum_{i \in \N, j \in \L} c_i x_{ij}. \]

\paragraph{Patches rotation.}
An important variation of the problem allows for rotating the patches.
We deal with this possibility by defining two virtual patch types for each real patch type.
Now $\N$ indicates the set of virtual patch types and all virtual patch types are given in pairs; $\P$ indicates the set of pairs.
For each pair $p=[u,v] \in \P$ with $u \in \N$ and $v \in \N$, we have $w_u=h_v$, $w_v=h_u$, $c_u=c_v$, $M_u=M_v$.
The only constraint that needs to be reformulated is the assignment constraint:
\[ \sum_{j \in \L} (x_{uj} + x_{vj}) \leq M_p\ \ \ \forall p=[u,v] \in \P \]
where $M_p=M_u=M_v$ is the overall number of patches of type $p \in \P$,
and $u \in \N$ and $v \in \N$ are two virtual types corresponding to the same real type $p \in \P$.

\paragraph{Mathematical model.}
The following integer linear programming model is obtained.
\begin{align}
\text{minimize  } f = & \sum_{i \in \N, j \in \L} c_i x_{ij}               &                                     \label{obj}         \\
\text{s.t.  }         & x_{ij} <= M_i t_{ij}                               & \forall i \in \N, j \in \L          \label{rel_xt}      \\
                      & \sum_{j \in \L} (x_{uj} + x_{vj}) \leq M_p         & \forall p=[u,v] \in \P              \label{n_patches}   \\
                      & \sum_{j \in \L} z_j = H                            &                                     \label{total_h}     \\
                      & z_j \leq H y_j                                     & \forall j \in \L                    \label{rel_zy}      \\
                      & h_i t_{ij} \leq z_j                                & \forall i \in \N,\ \forall j \in \L \label{min_z}       \\
                      & z_j \leq H - (H - h_i - \delta^H) t_{ij}           & \forall i \in \N,\ \forall j \in \L \label{max_z}       \\
                      & \sum_{i \in \N} w_i x_{ij} \leq W y_j              & \forall j \in \L                    \label{max_total_w} \\
                      & \sum_{i \in \N} (w_i + \delta^W) x_{ij} \geq W y_j & \forall j \in \L                    \label{min_total_w} \\
                      & x_{ij} \in \Z_+                                    & \forall i \in \N,\ \forall j \in \L \label{int_x}       \\
                      & t_{ij} \in \{0,1\}                                 & \forall i \in \N,\ \forall j \in \L \label{bin_t}       \\
                      & y_j \in \{0,1\}                                    & \forall j \in \L                    \label{bin_y}       \\
                      & z_j \geq 0                                         & \forall j \in \L.                   \label{z_nonneg}
\end{align}

\section{A reformulation}
We present a reformulation of the problem, where each column $k \in \K$ corresponds to a feasible level filled with patches.
\begin{align}
\text{minimize  } f = & \sum_{k \in \K} b_k \lambda_k                   &                    \label{m:obj}       \\
\text{s.t.  }         & \sum_{k \in \K} \alpha_{pk} \lambda_k \leq M_p  & \forall p \in \P   \label{m:n_patches} \\
                      & \sum_{k \in \K} h^{min}_k \lambda_k \leq H      &                    \label{m:min_h}     \\
                      & \sum_{k \in \K} h^{max}_k \lambda_k \geq H      &                    \label{m:max_h}     \\
                      & \lambda_k \in \Z_+                              & \forall k \in \K.  \label{m:int_lambda}
\end{align}
Here $b_k$ represents the total cost of all patches in level $k$;
$\alpha_{pk}$ is the number of patches of real type $p \in \P$ in level $k$;
$h^{min}_k$ and $h^{max}_k$ are the minimum and maximum feasible height for level $k$;
$\lambda_k$ are integer variables, representing the number of times level $k$ is used in the solution.
The set $\K$ has a combinatorial size because it includes all feasible levels (index $k$ has been dropped for convenience):
\begin{align}
\K = & \{(\alpha,h^{min},h^{max}) \in \Z_+^{P} \times \Re_+ \times \Re_+: & \notag            \\
     & a_i <= M_i d_i                              & \forall i \in \N       \label{rel_ad}    \\
     & a_u + a_v = \alpha_p                        & \forall [u,v] \in \P   \label{alpha}     \\
     & \alpha_p \leq M_p                           & \forall p \in \P       \label{max alpha} \\
     & h_i d_i \leq h^{min}                        & \forall i \in \N       \label{min_h}     \\
     & h^{max} \leq H - (H - h_i - \delta^H) d_i   & \forall i \in \N       \label{max_h}     \\
     & \sum_{i \in \N} w_i a_i \leq W              &                        \label{max_w}     \\
     & \sum_{i \in \N} (w_i + \delta^W) a_i \geq W &                        \label{min_w}     \\
     & a_i \in \Z_+^N                              &                        \label{int_a}     \\
     & d_i \in \{0,1\}^{N}                         &                        \label{bin_d}     \\
\}.  & & \notag
\end{align}
The cost of a level is given by
\[ b = \sum_{i \in \N} c_i a_i. \]

The master problem (\ref{m:obj})-(\ref{m:int_lambda}) is an integer knapsack problem, with some additional features.
Its linear relaxation can be solved with column generation by iteratively inserting columns in a restricted linear master problem.
The reduced cost of each column is given by
\[ r = \sum_{i \in \N} c_i a_i - \sum_{p \in \P} \beta_p \alpha_{p} - \mu^{min} h^{min} - \mu^{max} h^{max}, \]
where $\beta_p$ is the non-positive dual variable corresponding to each constraint (\ref{m:n_patches}),
$\mu_{min}$ is the non-positive dual variable corresponding to constraint (\ref{m:min_h}) and
$\mu_{max}$ is the non-negative dual variable corresponding to constraint (\ref{m:max_h}).

It should be noted that constraints (\ref{m:min_h}) are not likely to be active in any optimal solution of the relaxed master problem,
while constraints (\ref{m:max_h}) will be active for the {\em break item},
i.e. the level with a fractional value of $\lambda$ in the optimal solution.

The pricing problem is as follows:
\begin{align}
\text{minimize } r = & \sum_{i \in \N} c_i a_i - \sum_{p \in \P} \beta_p \alpha_{p} - \mu^{min} h^{min} - \mu^{max} h^{max} \hspace{-5.0cm} & \notag\\
\text{s.t.  }        & a_i <= M_i d_i                              & \forall i \in \N       \notag \\
                     & a_u + a_v = \alpha_p                        & \forall [u,v] \in \P   \notag \\
                     & \alpha_p \leq M_p                           & \forall p \in \P       \notag \\
                     & h_i d_i \leq h^{min}                        & \forall i \in \N       \notag \\
                     & h^{max} \leq H - (H - h_i - \delta^H) d_i   & \forall i \in \N       \notag \\
                     & \sum_{i \in \N} w_i a_i \leq W              &                        \notag \\
                     & \sum_{i \in \N} (w_i + \delta^W) a_i \geq W &                        \notag \\
                     & a_i \in \Z_+                                & \forall i \in \N       \notag \\
                     & d_i \in \{0,1\}                             & \forall i \in \N       \notag \\
                     & \alpha_p \in \Z_+                           & \forall p \in \P       \notag \\
                     & h^{min} \geq 0                              &                        \notag \\
                     & h^{max} \geq 0                              &                        \notag
\end{align}
We can reformulate the model, getting rid of variables $\alpha$.
\begin{align}
\text{minimize } r = & \sum_{i \in \N} (c_i - \beta_p(i)) a_i - \mu^{min} h^{min} - \mu^{max} h^{max} \hspace{-5.0cm} & \label{p:obj}\\
\text{s.t.  }        & a_i <= M_i d_i                              & \forall i \in \N       \label{p:rel_ad}    \\
                     & a_u + a_v = \leq M_p                        & \forall p=[u,v] \in \P \label{p:max a}     \\
                     & h_i d_i \leq h^{min}                        & \forall i \in \N       \label{p:min_h}     \\
                     & h^{max} \leq H - (H - h_i - \delta^H) d_i   & \forall i \in \N       \label{p:max_h}     \\
                     & \sum_{i \in \N} w_i a_i \leq W              &                        \label{p:max_w}     \\
                     & \sum_{i \in \N} (w_i + \delta^W) a_i \geq W &                        \label{p:min_w}     \\
                     & a_i \in \Z_+                                & \forall i \in \N       \label{p:int_a}     \\
                     & d_i \in \{0,1\}                             & \forall i \in \N       \label{p:bin_d}     \\
                     & h^{min} \geq 0                              &                        \label{p:hmin}      \\
                     & h^{max} \geq 0                              &                        \label{p:hmax}
\end{align}
By $p(i)$ we indicate the pair $p \in \P$ corresponding to type $i \in \N$.
This pricing problem is a variation of the bounded integer knapsack problem with demand constraints
and with additional penalties depending on the minimum and maximum item size (patch height).

{\bf Observation.} For each given set of patches (i.e. for each feasible choice of $a$),
the optimal values of $h_{min}$ and $h_{max}$ are given by
$h^{min}=\max_{i \in \N: a_i=1}\{h_i\}$ and
$h^{max}=\delta^H+\min_{i \in \N: a_i=1}\{h_i\}$.\\

Hence, we can solve the pricing sub-problem for each choice of the minimum and maximum patch height.
In the remainder we indicate these two values by $\underline{h}$ and $\overline{h}$.
For each instance of the pricing subproblem
all patch types $j \in \N$ such that $h_j$ does not fall in the range $[\underline{h},\overline{h}]$ are disregarded (i.e. $a_j$ is fixed to $0$).
We indicate by $\hat{N} \subseteq \N$ the subset of types that are compatible with the choice of $\underline{h}$ and $\overline{h}$
and we indicate the resulting pricing sub-problem as {\em restricted} pricing sub-problem:
\begin{align}
\text{minimize }r=&\sum_{i \in \hat{N}}(c_i-\beta_p(i))a_i-\mu^{min}\overline{h}-\mu^{max}(\underline{h}+\delta^H) \hspace{-5.0cm} & \label{rp:obj}\\
\text{s.t.  }     & a_u + a_v = \leq M_p                          & \forall p=[u,v] \in \P \label{rp:max a} \\
                  & \sum_{i \in \N_j} w_i a_i \leq W              &                        \label{rp:max_w} \\
                  & \sum_{i \in \N_j} (w_i + \delta^W) a_i \geq W &                        \label{rp:min_w} \\
                  & a_i \in \Z_+                                  & \forall i \in \N       \label{rp:int_a}
\end{align}
This reformulation allows to get rid of binary variables $d$.
The terms $-\mu^{min}\overline{h}-\mu^{max}(\underline{h}+\delta^H)$ do not affect the optimal solution since they are constant.
We indicate them as $\gamma(\mu^{min},\mu^{max},\underline{h},\overline{h})$.
We also indicate by $\overline{c}_i = c_i-\beta_p(i)$ the reduced cost of patch type $i \in \N$.
Hence the objective function can be rewritten as
\[\text{minimize  } r = \sum_{i \in \hat{N}} \overline{c}_i a_i + \gamma(\mu^{min},\mu^{max},\underline{h},\overline{h}). \]
We are left with an integer knapsack problem with items partitioned into types and a limit on the number of available items for each pair of types.

If a solution exists with a negative value of $r$, then a new column can be generated and inserted in the restricted master problem.

%\section{Conclusions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%\begin{thebibliography}{00}
%
%\end{thebibliography}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


