\section{Heuristics Design}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

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

%----------------------------------------------------
%----------------------------------------------------
\subsection{Problem Modelling}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Model Choice}
%----------------------------------------------------
\begin{frame}
	\frametitle{Choose the Right Model}
	\begin{block}{Modeling has a preponderant influence on the difficulty of resolution}
		In some cases, one can go from a difficult problem to a simple one\\
		Example: \alert{de  Bruijn} Graph for the reconstitution of a genetic sequence
			      \begin{itemize}[<+->]
				      \item An edge link the detected $k$-nucleotides that can appear successively in the sequence
				            \begin{itemize} \item Hamiltonian path, NP-complete \end{itemize}
				      \item An edge represents a detected $k$-nucleotides linking two $k-1$-nucleotides \begin{itemize} \item Eulerian path, can be solved in linear time\end{itemize}
			      \end{itemize}
	\end{block}
\end{frame}

\begin{frame}
	\frametitle{Reconstitution of a Genetic Sequence}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{genetic_reconstitution}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Algorithmic Construction}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}
		{Using the divide-and-regard paradigm when dealing with large data}
		\begin{itemize}[<+->]
			\item Data partitioning
			\item Designing a specific local search
			\begin{itemize}
				\item The choice of a good neighbourhood is crucial
				\item The \alert{no free lunch} theorem says that there is no universally better heuristic
				\begin{itemize}
					\item The heuristics must be adapted to the numerical characteristics of the problem
				\end{itemize}
			\end{itemize}
		\end{itemize}
	\end{block}
\end{frame}

\subsubsection{Decomposition into a Series of Sub-problems}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection : Location Routing}
	(a) Create groups of cities with an unsupervised clustering method\\
	(b) Create a tour on each group\\
	(c) Position the depots with a clustering method (grouping of tours)\\
	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.5\textwidth}
			\includepdftex{corsica_sardinia}
		\end{center}
	\end{figure}
\end{frame}


%%----------------------------------------------------
%%----------------------------------------------------
\subsection{Heuristics Tuning}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{itemize}[<+->]
		\item Problem instance choice
		      \begin{itemize}
			      \item Do not bias the results
		      \end{itemize}
		\item Graphical representation of the solutions produced
		      \begin{itemize}
			      \item Allows a better understanding of the (non-)functioning of a heuristic
		      \end{itemize}
		\item Adjustment of settings and options
		      \begin{itemize}
			      \item By far the most time consuming part
			      \item Consider using automated processes to avoid bias
		      \end{itemize}

		\item Measurement criteria
		      \begin{itemize}
			      \item Success rate
			      \item Computational time
			      \item Quality of the solutions produced
		      \end{itemize}

	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Time to Target Plot, Optimal Resolution of a TSP}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{success_rate}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Empirical complexity analysis}
	Allows to see the evolution of the resources needed according to the size of the problem\\
	Highlights algorithmic optimizations to be undertaken\\
	\begin{figure}[h]
		\begin{center}

			\includepdftex{complexity_analysis}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{framefont}{\scriptsize}
	\begin{frame}[shrink]
		\frametitle{STAMP Graph}
		Estimates by bootstrapping the confidence interval of the observed means or medians according to the calculation effort\\
		Double scale of effort measurement: absolute (number of GRASP iterations) or relative (calculation time)\\
		\begin{figure}[h]
			\begin{center}
				\includepdftex{STAMP_Graph}
			\end{center}
		\end{figure}
	\end{frame}
\end{framefont}