\section{Local Search}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

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

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsection}
	\begin{block}{General Idea}
		\begin{itemize}[<+->]
			\item Start from a solution obtained with a constructive method
			\item Modify it locally to improve it
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\input{./figures/2opt_improvement.pdf_tex}
		\end{center}
	\end{figure}
	Successive improvements of a TSP solution with a 2-opt local search\\
	Two edges are replaced by two others whose sum of lengths is smaller
\end{frame}

\subsection{Local Search Frame}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\input{./algorithms/improvement_method}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Neighbourhood Definition}
	 For each solution $s \in S$, define
		      \begin{itemize}[<+->]
			      \item $V(s) \subset S$ a subset of \definition{neighbour solutions} of $s$
			      \item Often, $V(s)$ is defined by modifications brought to $s$
			      \item When one moves from a solution $s$ to a solution $s' \in V(s)$, one performs a \definition{move} $m$
		      \end{itemize}
	\begin{block}{Example of Moves for a TSP}
		\begin{itemize}[<+->]
			\item $m$ is specified by a pair $[i, j]$
			\item Consists of replacing the edges $[i, s_i]$ and $[j, s_j]$ by the edges $[i, j]$ and $[s_i, s_j]$
			\item Set of 2-opt moves: $M(s) = \{[i, j], i, j \in s, i \neq j, j \neq s_i, i \neq s_j\}$
			\item Definition of $V(s) = \{s' | s' = s \oplus m, m \in M(s), s \in S\}$
		\end{itemize}
	\end{block}
\end{frame}

\subsubsection{Policy of the first improving move}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\input{./algorithms/first_improvement}
	\begin{block}{Algorithm Complexity}
		\begin{itemize}[<+->]
			\item at most $O(|S|)$ moves
			      \begin{itemize}
				      \item There is a finite number of solutions
				      \item One goes from a solution to a strictly better one
			      \end{itemize}
			\item The algorithm terminates after a time bounded by the number of solutions (in practice: greatly overestimated)
		\end{itemize}
	\end{block}
\end{frame}

\subsubsection{Best Move Policy}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\input{./algorithms/best_improvement}
\end{frame}

\subsubsection{Local, Global Minima, Plateau}
%----------------------------------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{\insertsubsubsection}
		\begin{block}{Solution obtained by local improvement method}
			\begin{itemize}[<+->]
				\item \definition{Local optimum}, not necessarily the best possible solution (\definition{global optimum})
				\item The quality of a local optimum depends on the starting solution and the definition of the neighbourhood
			\end{itemize}
		\end{block}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{optima}
			\end{center}
			Neighbourhood: modify $x$ by one unit
		\end{figure}
	\end{frame}
\end{framefont}

%----------------------------------------------------
\begin{frame}
	\frametitle{Empirical Complexity of 2-opt Neighbourhood}
	Comparison between the best and first improvement
	\begin{figure}[h]
		\begin{center}
			\includepdftex{complexity2opt}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{3-opt Neighbourhood}
	\begin{block}{Remplace 3 edges by 3 others}
		$(i \rightarrow s_i), (j \rightarrow s_j), (k \rightarrow s_k)$ replaced by: $(i \rightarrow s_j), (j \rightarrow s_k), (k \rightarrow s_i)$\\
		Respects the visiting order of the cities on the other arcs, unlike 2-opt
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{3opt_move}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Or-opt Neighbourhood}
	Move sub-sequences of 3, 2 or 1 cities
	\begin{figure}[h]
		\begin{center}
			\includepdftex{or_opt_move}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Neighbourhood Properties}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{description}[<+->]
		\item[Connectivity]Any feasible solution can reach at least one globally optimal solution
		\item[Low Diameter]Not too many steps are needed to connect any 2 solutions
		\item[Low Ruggedness]Fitness function value does not change too much from one solution to its neighbour, few local optima
		\item[Small Size]Not too many neighbour solutions should be evaluated
		\item[Fast Evaluation]Fitness function evaluation of a neighbour solution must be fast
	\end{description}
	\alert{These properties are often antagonistic!}
\end{frame}

%----------------------------------------------------
\begin{framefont}{\scriptsize}
	\begin{frame}
		\frametitle{Properties of 2-opt Neighbourhood}
		\begin{itemize}[<+->]
			\item \textbf{Connectivity:}
			      Easy to verify; in exercise
			\item \textbf{Graph Diameter:}
			      $O(n)$
			\item \textbf{Low Ruggedness:}
			      This criterion is not fulfilled for very asymmetric problems \\
			      A significant portion of the tour may be reversed by a 2-opt move
			      \begin{figure}[h]
				      \begin{center}
					      \includepdftex{2opt_move}
				      \end{center}
			      \end{figure}
			\item \textbf{Limited Size}:
			      $O(n^2)$
			\item \textbf{Fast Evaluation:}
			      For symmetrical instances: a neighbour solution can be evaluated in constant time \\
			      Modification of a solution in $O(n)$ (without a special data structure)
		\end{itemize}
	\end{frame}
\end{framefont}

%----------------------------------------------------
\begin{frame}
	\frametitle{Data structure to perform a 2-opt move in $O(1)$}
	A portion of the tour must be reversed in constant time
	\begin{figure}[h]
		\begin{center}
			\includepdftex{2opt_data_structure}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Limiting the Neighbourhood Size}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Candidate List}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\insertsubsection: \insertsubsubsection}
	\begin{block}{Idea: do not consider all neighbour solutions, but only a potentially interesting subset}
		Example for the Euclidean TSP: restrict to the edges contained in a Delaunay triangulation
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{delaunay_tsp225}
		\end{center}
	\end{figure}
\end{frame}



%----------------------------------------------------
%----------------------------------------------------
\subsection{Neighbourhood Extension}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection}
	\begin{itemize}[<+->]
		\item A simple neighbourhood, such as 2-opt for the TSP, has many local optima from which it is difficult to escape
		\item The changes made to the solution only marginally alter its structure
		\item Using a larger neighbourhood (4-opt, 5-opt) the computational effort becomes prohibitive
		\item It is not necessarily obvious how to define more complicated neighbourhoods

		\item How to extend a simple neighbourhood to make more significant changes to the solution
		\item Without increasing the complexity too much?
	\end{itemize}
\end{frame}

\subsubsection{Filter and Fan}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection: \insertsubsubsection}
	\begin{block}{Idea: Beam search adapted to the case of neighbourhood evaluation}
		\begin{itemize}[<+->]
			\item Evaluate the solution set of a simple neighbourhood
			\item Examine neighbours of neighbours, etc. up to a certain depth
			\item Avoid exponential growth in the number of solutions by filtering at each stage
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{filter_fan}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Ejection Chains}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\insertsubsection: \insertsubsubsection}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{lin_kernighan_principle}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{itemize}[<+->]
		\item \textbf{Chain Initialization:} Eject an edge $[a,b]$ to get a path
		\item \textbf{Chain Propagation:} Insert an edge $[b, d]$ to obtain a \definition{reference structure}
		      \begin{itemize}
			      \item The edge $[b, d]$ must not have been previously deleted during the ejection chain
			      \item The weight of the reference structure must be smaller than that of the starting tour
			      \item Ejecting the edge $[c, d]$ (not previously added during the ejection chain) results in the same situation as before
		      \end{itemize}
		\item \textbf{Stop of the Propagation}
		      \begin{itemize}
			      \item There is no longer a suitable $[b,d]$ or $[c,d]$ edges
			      \item The tour obtained by adding the edge $[a, c]$ is shorter than the starting tour
		      \end{itemize}
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Lin-Kernighan Neighbourhood for the TSP}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{lin_kernighan}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{framefont}{\scriptsize}
	\begin{frame}
		\frametitle{Ejection Chain for the TSP}
		\input{./algorithms/ejection_chain_tsp}
	\end{frame}
\end{framefont}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Multi-Objective Local Search}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}%----------------------------------------------------

\begin{framefont}{\scriptsize}
	\subsubsection{Scalarization}
	\begin{frame}
		\frametitle{\insertsubsection: Iterative Scalarizations}
		\input{./algorithms/scalarization}
	\end{frame}
\end{framefont}

%----------------------------------------------------
\begin{frame}
	\frametitle{}
	\begin{columns}
	\begin{column}{0.2\textwidth}
		Three steps of iterative scalarizations
	\end{column}
	\begin{column}{0.7\textwidth}

	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.6\textwidth}
			\includepdftex{tsp2obj_ils}
		\end{center}
	\end{figure}
\end{column}
\end{columns}
\end{frame}

\subsubsection{Pareto Local Search}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\input{./algorithms/pls}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Removal of a Dominated Element and Replacing it in a KD-Tree}
	New element of cost 287 and time 152, dominating element 298/217
	\begin{figure}[h]
		\begin{center}
			\includepdftex{KD_update}
		\end{center}
	\end{figure}
\end{frame}







