% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}

\newcommand{\reff}[1]{(\ref{#1})}


\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{On the Design of the\\Fiber To The Home Networks}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Stefano Gualandi, Federico Malucelli, Domenico L. Sozzi}

\address{Politecnico di Milano,
   Dipartimento di Elettronica e Informazione \\
   Piazza Leonardo da Vinci 32, 20133 Milano, Italy \\
   {\tt \{gualandi,malucell,sozzi\}@elet.polimi.it}}


\begin{keyword}
LP-based Randomized Rounding \sep Local Search \sep Network Design
\end{keyword}

\end{frontmatter}

% main text
\section {Introduction}
Telecommunications network design is the source of many interesting challenges in combinatorial optimization. Among the more recent ones there is the  design of the Next Generation Access Networks completely based on fiber cable technology that, in certain cases,  may reach single users and for this reason are called Fiber To The Home networks (FTTH). 
These networks are organized into two levels. In the first level few {\em central offices} are connected with high capacity fiber cables to {\em splicing cabinets} usually located at street intersections. Cabinets are then connected with users or houses. The fiber technology allows to have very long connection cables thus few central offices suffice to serve many more users with respect to traditional copper based networks.
The new network characteristics and the incumbent deployment, that requires a great extent of investments, motivate the investigations on quantitative optimization models and algorithms for the planning that can help investors to decide which type of fiber network to select and how to operationally implement it. For a review on technical aspects refer to \cite{Kramer2002}.


\section {Problem Statement and Formulation}
Planning a FTTH network can be seen as a particular case of facility location problem where facilities belong to two levels.
Given a set of candidate sites $O$  for central offices, a set of candidate sites $C$ for cabinets and  the set of homes to be served $S$, the problem consists in deciding in which candidates sites install central offices and cabinets, and connect users to central offices passing through a cabinet.
In addition to these decisions the problem considers also the multiplexing capability of cabinets. Depending on the type of device installed in the cabinet, several signals transmitted on fibers to the users can be groomed into a single fiber to the central office thus allowing for a capacity saving in the leg central office-cabinet. The additional decision level is thus the type of multiplexing technology to be installed in each cabinet.
Decisions must consider central office and cabinet installation costs, multiplexing technology costs, and cable deployment costs.

Let $s^1_i$ and $M^1_i$ be the cost and the capacity (in terms of number of fibers) of central office $i$. Let $T$ be the types of technologies that can be installed in cabinets.  Multiplexing technology $t$ in a cabinet allows to send $m_t$ channels on a single fiber towards the central office. 
Let  $s^2_{jt}$ be the installation cost of cabinet $j$ with technology $t$, and $M^2_{j}$ its maximum capacity in terms of number of fibers coming from the users.
With $d_{ij}$ we indicate the known distance (computed on the street graph) between any two sites $i$ and $j$.

A possible formulation of the problem  introduces two sets of binary variables: $y^1_i, i \in O$ whose value is 1 if a central office is activated in site $i$, and $y^2_{jt}, j\in C, t\in T$ if a cabinet with multiplexing technology $t$ is activated in site $j$.
We need another set of binary variables $x^2_{jl}$ whose value is 1 if basement $l$ is assigned to cabinet $j$.
Integer variables $x^1_{ij}$ give the number of fibers connecting central office $i$ with cabinet $j$. The last two sets of variables are defined for all pairs $i,j$ and $j,l$ such that the distance between the corresponding sites is less than or equal to the maximum allowed distance. In order to consider only  pairs of sites within a feasible distance, we introduce a set $E$ of pairs $i,j$ with $i \in O$ and $j\in C$ such that $d_{ij}\leq L^1$, and a set $F$ of pairs $j,l$ with  $j\in C$ and $l \in S$ such that $d_{jl}\leq L^2$.



The Integer Programming model is as follows:
\begin{align}
 \label{m1:obj} \min \quad & \sum_{i \in O} s^1_i y^1_i 
  + \sum_{j \in C} \sum_{t \in T} s^2_{jt} y^2_{jt}
  + \sum_{ij \in E} c^1_{ij} x^1_{ij}
  + \sum_{jl \in F} c^2_{jl} x^2_{jl}\\
\mbox{s.t.} \quad
  \label{m1:ass3} & \sum_{jl \in E} x^2_{jl} = 1,  & \forall l \in S, \\
  \label{m1:cap1} & \sum_{ij \in E} x^1_{ij} \leq M^1_i y^1_i,  & \forall i \in O, \\
  \label{m1:ass2} & \sum_{t \in T} y^2_{jt} \leq 1,  & \forall j \in C, \\
  \label{m1:cap2} & \sum_{jl \in F} x^2_{jl} \leq M^2_j \sum_{t \in T} y^2_{jt},  & \forall j \in C, \\
 % \label{m1:act1} & y^2_{jt} \leq \sum_{ij \in E} x^1_{ij}, & \forall j \in C, \forall t \in T, \\
  \label{m1:num1} & m_t \sum_{ij \in E} x^1_{ij} \geq \sum_{jl \in F} x^2_{jl} - M^2_j (1 - y^2_{jt}), & \forall j \in C, \forall t \in T, \\
  \label{vars} & y^1_i \in \{0,1\}, \forall i \in O,\;\; y^2_{jt} \in \{0,1\}, \forall j \in C, \forall t \in T, \\
  \label{varz} & x^1_{ij} \in \mathbb{Z}_+, \forall ij \in E,\quad x^2_{jl} \in \{0,1\}, \forall jl \in F.
\end{align}
Constraints \reff{m1:ass3} state that each user must be connected to a cabinet.
Constraints \reff{m1:cap1} are twofold: they force the activation of central office $i$ (i.e. it sets variable $y_i$ to 1) if at least one cabinet $j$ is assigned to it, and they limit the number of cabinets assigned to $i$ according to the capacity. 
Constraints \reff{m1:ass2} determine that either a cabinet is not active (when the left hand side is equal to 0) or at most a multiplexing technology is assigned to it. 
While constraints \reff{m1:num1} relate the number of incoming fibers in a cabinet from users with the number of outgoing fibers towards the central office. This number must account for the multiplexing factor installed in the cabinet. 
The objective function \reff{m1:obj} sums up the cost $s^1_i$ of each selected central office, the cost $s^2_{jt}$ for installing the technology $t$ in cabinet $j$  and the connection costs for the fibers between central offices and cabinets and between cabinets and the users.

In order to improve the linear relaxation, we introduce the following constraint:
\begin{equation}
   \label{m1:act1} \sum_{t \in T} y^2_{jt} \leq \sum_{ij \in E} x^1_{ij}, \forall j \in C. 
\end{equation}
that states that if a cabinet is activated it must be connected to a central office. Though the improvement on the lower bound is modest, this constraint does have an impact on our LP-based randomized rounding algorithm.

\section {Solution Approaches and Computational Results}
We have developed two approaches to solve the FTTH problem. The first approach is a LP-based Randomized Rounding (LP-RR) algorithm, the second is a Constraint-Based Local Search (CBLS) algorithm. Both approaches are implemented exploiting features of the {\sc Comet} constraint language \cite{Van2005}. For the lack of space, we just briefly sketch the two approaches. 

Our LP-RR algorithm, motivated by the results in \cite{Barahona2005}, is based on the observation that once we have decided which central offices and which cabinets are opened, that is, the variables $y^1$ and $y^2$ have been fixed to either 1 or 0, the remaining problem is reduced to a generalized minimum cost flow problem on a tripartite graph. So we first randomly round the variables $y^1$ and $y^2$, and only then, the $x^1$ and $x^2$ variables.

The proposed CBLS approach relies on the use of {\it invariants} (see \cite{Van2006}) to incrementally maintain the necessary information to guide the search procedure. 
Once a greedy procedure has computed a feasible solution, we execute
a local search algorithm based on a simple move: select the basement $l$ connected to a cabinet $j$, and select a different open cabinet $j'\neq j$ that is not saturated (it has some capacity left) such that {\it moving} $l$ from $j$ to $j'$ gives, after the propagation of the new assignments, the best improvement in the objective function. 
After this move, we possibly increase the number of fibers outgoing cabinet $j'$. 

Tables \ref{t1:comp} shows a comparison of the two approaches, reporting computational results averaged over 5 runs for each problem instance.
Even if both approaches are interesting, the CBLS outperforms the LP-RR both in quality and computation time. Table \ref{t3:more} reports the results for a set of realistic instances based on the street graph of the city of Rome. Note that CBLS computes near-optimal solution in short time.

\begin{table}
  \renewcommand{\arraystretch}{1.0}
  \renewcommand{\tabcolsep}{1mm}
  \centering
  \caption{LP-based Randomized Rounding (LP-RR) versus Constraint-based Local Search (CBLS). Cost and Time (in seconds). Standard deviations omitted. \label{t1:comp}}
  \begin{tabular}{|rrr|rrr|rrr|}
    \cline{4-9}  \multicolumn{3}{c|}{} & \multicolumn{3}{c|}{LP-RR} & \multicolumn{3}{c|}{CBLS} \\ \hline
    $|O|$ & $|C|$ & $|S|$ & Cost & Time & Best-Cost & Cost & Time & Best-Cost \\ \hline
3 & 10 & 100 & 2383 & 31 & {\bf 2383} & {\bf 2383} & 0.6 & {\bf 2383} \\ 
10 & 35 & 400 & 6979 & 716 & 6966 & 6864 & 1.2 & {\bf 6860} \\
15 & 65 & 841 & 13630 & 1735 & 13599 & 13349 & 44.6 & {\bf 13306} \\
20 & 100 & 1521 & 25499 & 2465 & 25427 & 24850 & 316 & {\bf 24752} \\
25 & 120 & 3025 & 55073 & 4768 & 55052 & 51752 & 330 & {\bf 51646} \\
30 & 140 & 6084 & 121794 & 7705 & 121974 & 118224 & 1105 & {\bf 118135} \\
35 & 150 & 10000 & 239668 & 26915 & 239668 & 229677 & 1817 & {\bf 229244} \\ \hline   
  \end{tabular}
\end{table}

\begin{table}
  \renewcommand{\arraystretch}{1.0}
  \renewcommand{\tabcolsep}{1mm}
  \centering
  \caption{Solving big Rome instances with the CBLS approach: gaps computed with respect to the linear relaxation (P). \label{t3:more}}
  \begin{tabular}{|rrr|rr|rr|r|r|} \hline
$|O|$ & $|C|$ & $|S|$ &  Cost & (stdev) & Time & (stdev) & Best-Cost & LP-Gap \\ \hline
30 & 140 & 5982 & 4561215 & (0.01\%) & 1803.6 & (0.14\%) & 4560780 & 0.9\% \\
30 & 140 & 5995 & 4164941 & (0.01\%) & 2168.7 & (0.69\%) & 4164724 & 1.1\%\\
30 & 140 & 6014 & 3462920 & (0.01\%) & 1426.9 & (0.35\%) & 3462857 & 1.4\%\\
35  & 150 & 10020& 3126763 & (0.02\%) & 2511.8 & (0.44\%)  & 3126385 & 2.4\% \\
35 & 150 & 10040 & 5937585 & (0.01\%) & 3484.7 & (0.55\%) & 5936733 & 1.1\%\\
35 & 150 & 10072 & 6663950 & (0.01\%) & 1183.6 & (0.54\%) & 6663481 & 0.9\% \\ \hline
  \end{tabular}
\end{table}

\begin{thebibliography}{00}

\bibitem{Barahona2005}
Barahona, F., Chudak, F.:
\newblock {Near-optimal solutions to large-scale facility location problems}.
\newblock Discrete Optimization \textbf{2}(1) (2005)  35--50

\bibitem{Kramer2002}
Kramer, G., Pesavento, G.:
\newblock {Ethernet Passive Optical Network (EPON): building a next-generation
  optical access network}.
\newblock IEEE Communications Magazine \textbf{40}(2) (2002)  66--73

\bibitem{Van2005}
Van~Hentenryck, P., Michel, L.:
\newblock {Control abstractions for local search}.
\newblock Constraints \textbf{10}(2) (2005)  137--157

\bibitem{Van2006}
Van~Hentenryck, P., Michel, L.:
\newblock {Differentiable invariants}.
\newblock In: Fr\'ed\'eric Benhamou (Ed.), Proc CP-06
  {LNCS-4204}. Springer, (2006) 604--619

\end{thebibliography}

\end{document}

