\section{Constructive 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{Systematic Enumeration}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection}
	\footnotesize
	\begin{itemize}[<+->]
		\item$0-1$ knapsack instance with two constraints with $n$ variables: has $2^n$ potential solutions\\
		\begin{equation*}
			\begin{array}{rrll}
				\max        r = & 9x_1 + 5x_2 + 7x_3 + 3x_4 + x_5       &           &    \\
				\mbox{S.t.}     & 4x_1 + 3x_2 + 5x_3 + 2x_4 + x_5       & \leqslant & 10 \\
				                & 4x_1 + 2x_2 + 3x_3 + 2x_4 + x_5       & \leqslant & 7  \\
				                & x_i  \in  \{ 0, 1\} (i = 1, \dots, 5) &           &    \\
			\end{array}
		\end{equation*}
		\item The solution can be enumerated by splitting the problem into two sub-problems \\
		\[ \begin{array}{rrll}
				\max        r = & 0 + 5x_2 + 7x_3 + 3x_4 + x_5         &           &    \\
				\mbox{S.t. }    & 3x_2 + 5x_3 + 2x_4 + x_5             & \leqslant & 10 \\
				                & 2x_2 + 3x_3 + 2x_4 + x_5             & \leqslant & 7  \\
				                & x_i  \in \{ 0, 1\} (i = 2, \dots, 5) &           &    \\
			\end{array}
		\]
		\[ \begin{array}{rrll}
				\max        r = & 9 + 5x_2 + 7x_3 + 3x_4 + x_5          &           &   \\
				\mbox{S.t.}     & 3x_2 + 5x_3 + 2x_4 + x_5              & \leqslant & 6 \\
				                & 2x_2 + 3x_3 + 2x_4 + x_5              & \leqslant & 3 \\
				                & x_i  \in  \{ 0, 1\} (i = 2, \dots, 5) &           &   \\
			\end{array}
		\]
	\end{itemize}
\end{frame}

\subsubsection{Branch and Bound}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\footnotesize
	Before separating, it is assessed whether the problem can potentially be solved by relaxing it\\
	\begin{itemize}[<+->]
		\item Integrity: \begin{equation*}
			      \begin{array}{rrll}
				      \max        S = & 9x_1 + 5x_2 + 7x_3 + 3x_4 + x_5                 &           &    \\
				      \mbox{S.t.}     & 4x_1 + 3x_2 + 5x_3 + 2x_4 + x_5                 & \leqslant & 10 \\
				                      & 4x_1 + 2x_2 + 3x_3 + 2x_4 + x_5                 & \leqslant & 7  \\
				                      & 0 \leqslant x_i  \leqslant 1  (i = 1, \dots, 5) &           &    \\
			      \end{array}
		      \end{equation*}
		\item Aggregation of constraints: \begin{equation*}
			      \begin{array}{rrll}
				      \max        S = & 9x_1 + 5x_2 + 7x_3 + 3x_4 + \phantom{1}x_5 &           &    \\
				      \mbox{S.t.}     & 8x_1 + 5x_2 + 8x_3 + 4x_4 + 2x_5           & \leqslant & 17 \\
				                      & x_i  \in  \{ 0, 1\} (i = 1, \dots, 5)      &           &    \\
			      \end{array}
		      \end{equation*}
		\item Combination of relaxations: \begin{equation*}
			      \begin{array}{rrll}
				      \max        S = & 9x_1 + 5x_2 + 7x_3 + 3x_4 + \phantom{1}x_5      &           &    \\
				      \mbox{S.t.}     & 8x_1 + 5x_2 + 8x_3 + 4x_4 + 2x_5                & \leqslant & 17 \\
				                      & 0 \leqslant x_i  \leqslant 1  (i = 1, \dots, 5) &           &    \\
			      \end{array}
		      \end{equation*}
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Policy Example of a Branch and Bound}
	\footnotesize
	\begin{itemize}[<+->]
		\item $Q$ manage as a stack
		\item Branching according to the order of the indices
		\item Constraint aggregation and variable integrity relaxation
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{branch_bound_knapsack}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{framefont}{\scriptsize}
	\begin{frame}
		\frametitle{Branch and Bound Frame}
		\input{./algorithms/branch_and_bound}
	\end{frame}
\end{framefont}

\subsection{Random Building}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection}
	Idea
	\begin{itemize}[<+->]
			      \item Draw a solution randomly, uniformly in the space of admissible solutions
		\item Benefit: One of the simplest methods 
		\item Drawbacks
		      \begin{itemize}
			      \item	A uniform construction is not necessarily easy to achieve
			      \item The quality of the solution is poor
		      \end{itemize}
		\item Example:	Draw a random permutation of $n$ elements
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Bad algorithm for constructing a random permutation (1)}
	\input{./algorithms/bad_permutation1}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Bad algorithm for constructing a random permutation (2)}
	\input{./algorithms/bad_permutation2}
\end{frame}

\subsection{Greedy Algorithms}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%-----------------------------------------------
\begin{frame}
	\frametitle{General idea of greedy methods}
	\begin{block}{Imitating what works with Prim and Dijkstra}
		\begin{itemize}[<+->]
			\item Construct a solution, element by element
			\item Add the element that seems most appropriate at each step
			\item Do not question a choice
		\end{itemize}
	\end{block}
	\begin{itemize}[<+->]
		\item Example of elements that can be added to a solution
		      \begin{itemize}[<+->]
			      \item A city for a travelling salesman
			      \item An edge for a travelling salesman or for a Steiner tree
			      \item A vertex with a given colour for graph colouring
			      \item Orientation of an edge for graph colouring
		      \end{itemize}
		\item When adding an element $e$ to a partial solution $s$, an incremental cost $c(s,e)$ is taken into account, and this can lead to restrictions on the elements that remain to be added
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Greedy Algorithm}
	\input{./algorithms/greedy}
\end{frame}

\subsubsection{Greedy Heuristics for the TSP}
%----------------------------------------------------
\begin{frame}
	\frametitle{Greedy on the Edge Weight for the TSP}
	\begin{block}{Same as Kruskal, but without allowing a vertex degree larger than 2}
		\begin{itemize}[<+->]
			\item Element $e$ to be added: an edge
			\item Incremental cost: edge cost $e$
			\item Elements to remove: do not create degree 3 vertices or sub-cycles
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{greedy_edge}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Nearest Neighbour for the TSP}
	\begin{block}{Same as Prim, but the next vertex must be connected to the last one added}
		\begin{itemize}[<+->]
			\item Start from any city
			\item Element $e$ to be added: a city
			\item Incremental cost: edge cost to reach $e$ from the last added city
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{nearest_neighbour}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Cheapest Insertion for the TSP}
	\begin{itemize}[<+->]
		\item Start from a 2-city tour
		\item Element $e$ to be added: a city
		\item Incremental cost: cost of a minimum detour to add $e$ to the partial tour
		\item Choose the city with the lowest incremental cost
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{cheapest_insertion}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Farthest Insertion for the TSP}
	\begin{itemize}[<+->]
		\item Start from a 2-city tour
		\item Element $e$ to be added: a city
		\item Incremental cost: cost of a minimum detour to add $e$ to the partial tour
		\item Choose the city with the largest incremental cost
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{farthest_insertion}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Greedy Heuristics for Graph Colouring}
%----------------------------------------------------
\begin{framefont}{\small}
	\begin{frame}
		\frametitle{DSATUR Heuristics for Graph Colouring}
		Idea: calculate the degree of saturation $DS(v)$ of each vertex $v$ (the number of different colours used by adjacent vertices of $v$)\\

		\input{./algorithms/DSATUR}
	\end{frame}
\end{framefont}

\subsection{Improvement of Greedy Procedures}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Beam Search}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{block}{Identical to an enumeration method, but avoid node number exponential growth}
		\begin{itemize}[<+->]
			\item Select only the $p$ best candidates at each level
			\item Stop $k$ levels below the last added element
			\item Add the element that results in the best partial solution at the last level evaluated
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{beam_search}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Pilot Method}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{block}{Try all possibilities to complete a partial solution with one element, then launch a heuristic method (pilot)}
		\begin{itemize}[<+->]
			\item The pilot heuristic starts with various partial solutions
			\item Run the pilot heuristic until complete solutions are obtained
			\item The element to be added to the partial solution is the one that led to the best complete solution
		\end{itemize}
	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection: Illustration}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{pilot}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Pilot Method Algorithm}
	\input{./algorithms/pilot}
\end{frame}




