\section{Decomposition Methods}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

\begin{frame}{Chapter Content}
	\begin{center}\vfill
		\tableofcontents[sections={\thesection}]
	\end{center}
\end{frame}

\subsection{Consideration on the Problem Size}

%-----------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\renewcommand{\arraystretch}{2}
	\rowcolors{1}{RoyalBlue!20}{mymauve!5}
	\begin{tabular}{ m{0.18\textwidth} m{0.35\textwidth}m{0.35\textwidth}}


		\toprule
		\textbf{Class} & \textbf{Typical Approach} & \textbf{Size}                         \\
		\midrule
		Toy            & Exhaustive Enumeration    & $n \approx 10$                        \\
		Small          & Implicit Enumeration      & $10 \lessapprox n \lessapprox 10^2$   \\
		Standard       & Metaheuristics            & $10^2 \lessapprox n \lessapprox 10^4$ \\
		Large          & Decomposition Methods     & $10^3 \lessapprox n \lessapprox 10^7$ \\
		Huge           & Big data                  & $n > 10^7$ elements                   \\
		\bottomrule
	\end{tabular}
	\renewcommand{\arraystretch}{1}
\end{frame}

%------------------------------------
\subsection{Recursive Algorithms}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{itemize}[<+->]
		\item {Solving the problem directly requires a more than linear computational effort, otherwise a decomposition only makes sense for a parallel calculation}
		\item {The pieces must be able to be processed independently of each other}
		\item {The assembly of the pieces must be of a lower complexity than solving the problem directly}
	\end{itemize}
	Investigate the relevance of a recursive approach with the general recurrence theorem
\end{frame}

%----------------------------------
\subsubsection{Master Theorem for Divide-and-Conquer}
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{block}{Problem of size $n$ split into $b$ parts; among them, $a$ are recursively solved\\
			Find the solution of the fonctional equation $T(n) = a\cdot T(n/b) + f(n)$}
		\begin{itemize}
			\item{If $f(n) = O(n^{log_b(a)-\epsilon})$, then  $T(n) = \Theta(n^{log_b(a)})$}
			\item{If $f(n) = \Theta(n^{log_b(a)})$, then $T(n) = \Theta(n^{log_b(a)}\cdot log\ n)$}
			\item{If $f(n) = \Omega(n^{log_b(a)+\epsilon})$ and if $a \cdot f(n/b) < c \cdot f(n)$ with $c < 1$, constant, then $T(n) = \Theta(f(n))$}
		\end{itemize}
	\end{block}
	Examples
	\begin{description}[<+->]
	     \item [Dichotomous search] $a = 1, b = 2, f(n) = \Theta(n^{log_2(1)}) = \Theta(1) \implies T(n) = \Theta(\log n)$
	     \item [Merge Sort] $a = 2, b = 2, f(n) = \Theta(n) \implies T(n) = \Theta(n \log n)$
	     \item [Query in a 2D-Tree] $a = 2, b = 4, f(n) = O(1) = O(n^{\log_b(a) - \epsilon}) = O(n^{0.5 - 0.5}) \implies T(n) = \Theta(\sqrt n)$
	\end{description}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Low Complexity Constructive Methods}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Proximity Graph Construction}
%----------------------------------------------------
\begin{frame}
	\frametitle{First Decomposition Level}
	\begin{block}{Assumption: not all elements of a problem are related to all others}
		\begin{itemize}[<+->]
			\item Idea: create a subset of the possible relationships between elements
			\item Limit the number of relationships for each element
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.9\textwidth}
			\includepdftex{partition_level1}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Second Decomposition Level}
	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.5\textwidth}
			\includepdftex{partition_level2}
		\end{center}
	\end{figure}
\end{frame}

%---------------------
\begin{frame}
	\frametitle{Clustering for Creating Relationships}

	\begin{itemize}[<+->]
		\item Create $\Theta(\sqrt n)$ groups of approximately the same size (e.g. with a modified and accelerated PAM algorithm; this can be done with empirical complexity $\hat{O}(n^{3/2})$)
		\item Two centres $c_i$ and $c_j$ are related if they are the nearest and second nearest centres of an element
		\item Assuming that a centre is only related to $O(1)$ other centres and that the groups have only $O(n)$ elements, we can construct in $O(n^{3/2})$ proximity relations between the $n$ entities
		\item We can exploit these relations in a greedy constructive method to obtain a solution in $O(n^{3/2})$
	\end{itemize}

\end{frame}

\subsubsection{Linearithmic Heuristics for the TSP}
%----------------------------------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{Recursive Construction for the TSP}\label{sec:recursive_tsp_building}
		\begin{itemize}[<+->]
			\item Create a tour on a sample of $r$ cities
			\item Insert the remaining cities in any order after the nearest sample city
			\item If the path between 2 cities in the sample contains too many cities, decompose it recursively
			\item Otherwise, optimize it with a good quality method
		\end{itemize}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{reorder_path}
			\end{center}
		\end{figure}
	\end{frame}
\end{framefont}
%----------------------------------------------------
%----------------------------------------------------
\subsection{Local Search for Large Instances}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Large Neighbourhood Search}
%----------------------------------------------------
\begin{frame}{\insertsubsubsection (LNS)}
	\begin{block}{General Idea}
		\begin{itemize}[<+->]
			\item Destroy part of the solution
			\item Rebuild it by trying to do better
		\end{itemize}
	\end{block}
	Illustration for a vehicle routing problem
	\begin{figure}[h]
		\begin{center}
			\includepdftex{lns_vrp}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection Frame}
	\input{./algorithms/lns}
	\begin{itemize}[<+->]
		\item Example of adaptation: $d(\cdot)$ consists in choosing a small subset of variables
		\item $r(\cdot)$ finds a local (or global) optimum by changing only the variables chosen by $d(\cdot)$
		\item $a(s, s'): f(s') < f(s)$
	\end{itemize}
\end{frame}

\subsubsection{POPMUSIC}
%---------------------
\begin{frame}
	\frametitle{Local Improvements for a Centroid Clustering Problem}
	\begin{columns}
		\begin{column}{0.4\textwidth}
			\begin{itemize}[<+->]
				\item Optimizing 2 very distant groups independently cannot bring benefits
				\item Choose a seed centre and a number of centres that are closest to it
				\item Optimize the position of these centres by considering the entities attached to them as an independent sub-problem
				\item Repeat with other seed-centres
			\end{itemize}
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{figure}
				\begin{center}
					\includepdftex{popmusic_cluster}
				\end{center}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}




%----------------------------------------------------
\begin{frame}
	\frametitle{POPMUSIC Frame}
	\input{./algorithms/popmusic}
\end{frame}

%-----------------
\begin{frame}
	\frametitle{Illustration of POPMUSIC for the VRP}
	\begin{columns}
		\begin{column}{0.35 \textwidth}
			\begin{itemize}[<+->]
				\item The clients of a tour define a part
				\item The proximity of the parts is measured by the distance of their centre of gravity
			\end{itemize}
		\end{column}
		\begin{column}{0.65 \textwidth}
			\begin{figure}
				\begin{center}
					\def\svgwidth{0.55\textwidth}
					\includepdftex{popmusic_vrp}
				\end{center}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}


%-----------------
\begin{frame}
	\frametitle{POPMUSIC for Map Labelling}
	\begin{columns}
		\begin{column}{0.3 \textwidth}
			\begin{itemize}[<+->]
				\item A part is an object to be labelled (here: 4 possible positions for the label of each object)
				\item Two objects are at a distance of 1 if their labels can overlap
			\end{itemize}
		\end{column}
		\begin{column}{0.7 \textwidth}
			\begin{figure}
				\begin{center}
					\includepdftex{spb_map_labelling}
				\end{center}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{POPMUSIC for the TSP}
	\begin{itemize}[<+->]
		\item Decompose the tour into sub-paths with approximately $r$ cities
		\item Optimize each sub-path with a good method
		\item Repeat, shifting the sub-paths by $r/2$ cities
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{fast_pop_2scans}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Empirical Complexity of POPMUSIC}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{time_tsp}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Solution Quality for the TSP with Toroidal Distances}
	Fluctuations are due to the number of recursion levels\\
	The sub-path optimization method provides solutions about 4\% above the optimum\\
	\begin{figure}[h]
		\begin{center}
			\includepdftex{quality_tsp}
		\end{center}
	\end{figure}
\end{frame}