\section{Combinatorial Optimization Problems \label{chap:comb_opt_modelling}}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

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

\subsection{Optimal Trees}
\frame{\center \Large \thesection .\thesubsection \
	\alert{\insertsubsection}}
%----------------------------------------------------\
\begin{frame}
	\frametitle{Kruskal Algorithm for Finding a Minimum Spanning Tree}
	\begin{block}{For each edge, decide wether it is kept or not}
		\begin{itemize}[<+->]
			\item There are $2^{|E|}$ potential solutions
			\item This is a combinatorial problem
		\end{itemize}
	\end{block}
	\input{./algorithms/kruskal.tex}
	\begin{itemize}[<+->]
		\item This is a \alert{greedy} algorithm
		\item The algorithm is polynomial, so the problem is simple
	\end{itemize}
\end{frame}
%----------------------------------------------------

%----------------------------------------------------
\begin{frame}
	\frametitle{Jarník  Algorithm for Finding a Minimum Spanning Tree}
	\framesubtitle{Known Under Prim or Prim-Dijkstra Algorithm}
	\footnotesize
	\input{./algorithms/prim.tex}
\end{frame}



\subsubsection{Steiner Tree}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{steiner_tree}
		\end{center}
	\end{figure}

	The combinatorial nature of the optional (Steiner) vertices to be introduced makes the problem NP-hard

\end{frame}

\subsection{Optimal Paths}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Shortest Path}
%----------------------------------------------------
\begin{frame}
	\frametitle{Dijkstra Algorithm for Finding a Shortest Path}
	\footnotesize
	\input{./algorithms/dijkstra}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Bellman-Ford Algorithm for the Shortest Path}
	\scriptsize
	\input{./algorithms/bellman_ford}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Operating Differences Between Dijkstra et Bellman Algorithms}
	\begin{block}{Kruskal, Prim et Dijkstra are greedy algorithms}
		\begin{itemize}[<+->]
			\item A choice made at a step is never questioned
			\item The choices to be made may differ from one algorithm to another
			      \begin{itemize}
				      \item Kruskal: one edge is introduced at each step
				      \item Prim: a vertex is introduced at each step
			      \end{itemize}
			\item Prim and Dijkstra can be formulated almost identically
		\end{itemize}
	\end{block}
	\begin{block}{Bellman-Ford works on the principle of local improvements}
		\begin{itemize}[<+->]
			\item We start with a solution that is not necessarily good
			\item At each step, the solution is slightly improved
		\end{itemize}
	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Formulation of the shortest path problem in terms of a linear program}
	\footnotesize
	Primal:
	\begin{align*}
		\textnormal{Minimize }  z  = & \sum_{i,j}{w(i,j) x_{ij}}                                                                    \\
		\textnormal{s.t. }           & \sum_{i = 1}^n{x_{ij}}    -  \sum_{k = 1}^n{x_{jk}}   =  0\qquad \forall j \ne s, j \ne s, t \\
		                             & \sum_{i = 1}^n{x_{it}}    -  \sum_{k = 1}^n{x_{tk}}  =  1                                    \\
		                             & x_{ij}  \geqslant  0\qquad  \forall i, j
	\end{align*}
	Dual:
	\begin{align*}
		\textnormal{Maximize } & \lambda _t                                                    \\
		\textnormal{s.t. }     & \lambda _j - \lambda _i  \leqslant  w(i,j)\qquad \forall i, j \\
		                       & \lambda _s  =  0
	\end{align*}

\end{frame}

\subsubsection{Elementary Shortest Path}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Polynomial Reduction of Travelling Salesman to Elementary Path}
	\begin{block}{Travelling Salesman Problem (TSP)}
		\begin{itemize}[<+->]
			\item Find the shortest Hamiltonian cycle in a weighted network
			\item It has been proved that the search for a Hamiltonian path is NP-complete
			\item From this result, it is easy to prove that the TSP is difficult
		\end{itemize}
	\end{block}

	\begin{figure}[h]
		\begin{center}
			\includepdftex{transfo_tsp_path}
		\end{center}
	\end{figure}

\end{frame}


\subsubsection{Vehicle Routing}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{columns}
		\begin{column}{0.5\textwidth}
			\begin{itemize}[<+->]
				\item Set $V$ of customers requiring quantities $q_i$ of goods ($i = 1, \dots, |V|$)
				\item A vehicle of capacity $Q$
				\item A warehouse $d$
				\item Split $V$ into $V_1, \dots V_m$ such that $\sum_{i \in V_i}{q_i} \leqslant Q$
				\item Solve a TSP for each $V_j \cup \{d\}$
				\item Minimize the total distance performed by the vehicle
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			\begin{center}
				\includepdftex{vrp}
			\end{center}
		\end{column}
	\end{columns}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Variants of Vehicle Routing Problems}
	\begin{itemize}[<+->]
		\item {The number $m$ of tours can be \emph{a priori} set or minimized}
		\item {The maximum length of tours can be limited}
		\item {Customers specify one or more time windows during which they want the vehicle to visit}
		\item {Orders can be split up as required, which means several visits to the same customer}
		\item {A tour combines collection and distribution}
		\item {We have more than one warehouse}
		\item {Depots house a fleet of heterogeneous or non-homogeneous vehicles}
		\item {The position of warehouses can be chosen}
		\item {Etc.}
	\end{itemize}
\end{frame}

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

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection}
	\footnotesize
	\begin{block}{Determine the order in which to perform operations. Many parameters:}
		\begin{description}[<+->]
			\item[Ressource]An operation must take place on a given resource or subset of resources or involve several resources simultaneously
			\item[Duration]It takes a certain amount of time to complete an operation, which may depend on the resource used
			\item[Setup]Before performing an operation, the resource requires a set-up time depending on the previously performed operation
			\item[Interrupt]Once an operation has started, it can be put on hold (or not) before it ends
			\item[Preemption]A resource can interrupt (or not) an operation to perform another one
			\item[Wait] There may or may not be a dead time between two successive operations of the same task
			\item[Release]An operation cannot take place before a certain time
			\item[Deadline]An operation cannot take place after a certain hour
		\end{description}
	\end{block}
\end{frame}

\subsubsection{Permutation Flow Shop Scheduling}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	Application: Assembly line with $m$ machines, each object to undergo $m$ operations, one per machine, without interruption or pre-emption
	\begin{figure}[h]
		\begin{center}
			\includepdftex{flowshop}
		\end{center}
	\end{figure}

\end{frame}

\begin{frame}
	\frametitle{PL formulation of the Permutation Flow Shop Scheduling}
	\begin{align*}
			\textnormal{Minimize } & d_{\omega} \\
			d_{mj} + t_{mj}  &  \leqslant  d_{\omega} \quad (j = 1 \dots n) \\
			d_{ij} + t_{ij}  &  \leqslant  d_{i+1 j}  \quad (i = 1, \dots m-1, j = 1 \dots n) \\
			d_{ij} + t_{ij}  &  \leqslant  d_{ik} + M \cdot (1-y_{jk})  \quad (i = 1, \dots m, j = 1 \dots n, j < k = 2 \dots n) \\
			d_{ik} + t_{ik}  &  \leqslant  d_{ij} + M \cdot y_{jk}  \quad (i = 1, \dots m, j = 1 \dots n, j < k = 2 \dots n) \\
			d_{ij}  &  \geqslant  0  \quad (i = 1, \dots m, j = 1 \dots n) \\
			y_{jk} & \in  \{0, 1\}  \quad  (j = 1 \dots n, j < k = 2 \dots n) 
	\end{align*}
\end{frame}

\subsubsection{Job Shop Scheduling}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\footnotesize
	Example of modelling with 3 machines and 3 objects
	\begin{figure}[h]
		\begin{center}
			\includepdftex{jobshop}
		\end{center}
	\end{figure}
	Problem: Orient the edges of the cliques associated with the operations on each machine to minimize the longest path from $\alpha$ to $\omega$
\end{frame}
\begin{frame}
	\frametitle{PL formulation of the Job Shop Scheduling}
	\begin{align*}
		\textnormal{Minimize } & d_{\omega} \\
		d_i + t_i  &  \leqslant  d_j \quad \forall (i,j) \\
		d_i + t_i  &  \leqslant  d_{\omega}  \quad \forall i \\
		d_i + t_i  &  \leqslant  d_k + M \cdot (1-y_{ik})  \quad \forall i,k \textnormal{ on the same machine} \\
		d_k + t_k  &  \leqslant  d_i + M \cdot y_{ik}  \quad \forall i,k \textnormal{ on the same machine} \\
		d_i  &  \geqslant  0  \quad \forall i \\
		y_{ik} & \in  \{0, 1\}  \quad  \forall i,k \textnormal{ on the same machine} 
	\end{align*}
\end{frame}

\subsection{Flows in networks}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{Search for a maximum flow (1): blocking flow}
	By increasing the flow by one unit on the path $s-1-2-t$, there is no longer a path with a possible direct increase
	\begin{figure}[h]
		\begin{center}
			\includepdftex{flow_0_blocking}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Searching for a Maximum Flow (2): Residual Network}
	Idea: we can increase the flow from 2 to 1 by decreasing the flow from 1 to 2
	\begin{figure}[h]
		\begin{center}
			\includepdftex{residual_network}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Ford-Fulkerson Algorithm}
	\begin{block}{Search for a maximum flow from $s$ to $t$}
		\input{./algorithms/fordfulkerson}
	\end{block}
	\alert{Local Improvement Algorithm}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Searching for a maximum flow (3): proof of optimality}
	We can exhibit a subset $A$ separating $s$ from $t$ such that the sum of the capacities leaving $A$ is equal to the value of the flow found
	\begin{figure}[h]
		\begin{center}
			\includepdftex{optimum_flow}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Busacker-Gowen Algorithm for a Maximum Flow with Minimum Cost}
	\input{./algorithms/busackergowen}
\end{frame}

\subsection{Assignment Problems}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%----------------------------------------------------
\subsubsection{Linear Assignment}

%----------------------------------------------------
\begin{frame}
	\frametitle{Linear Assignment in Terms de Linear Programming}
	\begin{eqnarray*}
		\label{linear_assignment_objective} \textnormal{Minimize}   &   &  \sum_{i = 1}^n{\sum_{u = 1}^n{{c_{iu}x_{iu}}}}     \\
		\nonumber \textnormal{Such that} & &\\
		\label{linear_assignment_constr1} \sum_{i = 1}^n{x_{iu}}    & = &1\quad    u = 1, \dots, n  \\
		\label{linear_assignment_constr2} \sum_{u = 1}^n{x_{iu}}    & = &1\quad   i = 1, \dots, n   \\
		\label{linear_assignment_integrity} x_{iu} \  &\in &\{0, 1\}\quad (i, u = 1, \dots, n)
	\end{eqnarray*}
	\alert{The problem can be polynomially solved with a network flow model}
\end{frame}

\begin{frame}
	\frametitle{Generalized Assignment}
	\begin{eqnarray*}
		\label{generalized_assignment_objective} \textnormal{Minimize}   &   &  \sum_{i = 1}^n{\sum_{u = 1}^m{{c_{iu}x_{iu}}}}     \\
		\nonumber \textnormal{Such that} & &\\
		\label{generalized_assignment_constr1} \sum_{i = 1}^n{w_{iu} x_{iu}}    & \leqslant &t_u\quad    u = 1, \dots, n  \\
		\label{generalized_assignment_constr2} \sum_{u = 1}^m{x_{iu}}    & = &1\quad   i = 1, \dots, n   \\
		\label{generalized_assignment_integrity} x_{iu} \  &\in &\{0, 1\}\quad (i, u = 1, \dots, n)
	\end{eqnarray*}
	\alert{NP-hard}
\end{frame}
%----------------------------------------------------
\subsubsection{Knapsack}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsubsection}
	\begin{itemize}[<+->]
		\item Special case of the generalized assignment
		\item Objects of volume $v_i$ with values $c_i, (i = 1, \dots, n$)
		\item Find the maximum value load of the knapsack
		\item Not exceeding the volume $V$ of the sack
		\item The simplest $NP$-hard problem that can be expressed as a integer linear program:
	\end{itemize}
	\begin{eqnarray*}
		\label{knapsack_objective} \textnormal{Maximize}   &   &  \sum_{i = 1}^n{c_i \cdot x_i}     \\
		\nonumber \textnormal{Such that} & &\\
		\label{knapsack_volume} \sum_{i = 1}^n{v_i \cdot x_i}    & \leqslant &V  \\
		\label{knapsack_integrality} x_{i} \  &\in &\{0, 1\}\quad (i = 1, \dots, n)
	\end{eqnarray*}
\end{frame}

%----------------------------------------------------
\subsubsection{Quadratic Assignment}

%----------------------------------------------------
\begin{frame}
	\frametitle{Standard and optimised mobile phone keyboard}
	\begin{itemize}[<+->]
		\item 1 unit of time to press a key
		\item 2 time units for moving from one key to another
		\item Wait 6 time units to enter a new symbol on the same key
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{standard_optimized_keyboard}
		\end{center}
	\end{figure}
	\begin{itemize}[<+->]
		\item 70 units of time to type ``a ce soir bisous ´´
		\item Only 51 time units with an optimised keyboard
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Quadratic Assignment Problem}
	\footnotesize
	\begin{eqnarray*}
		\label{qap_objective} \textnormal{Minimize}   &   &  \sum_{i = 1}^n{\sum_{j = 1}^n{\sum_{u = 1}^n{\sum_{v = 1}^n{{a_{ij}b_{uv}x_{iu}x_{jv}}}}}}     \\
		\nonumber \textnormal{Such that} & &\\
		\label{qap_constr1} \sum_{i = 1}^n{x_{iu}}    & = &1\quad    u = 1, \dots, n  \\
		\label{qap_constr2} \sum_{u = 1}^n{x_{iu}}    & = &1\quad   i = 1, \dots, n   \\
		\label{qap_constr_int} x_{iu} \  &\in &\{0, 1\}\quad (i, u = 1, \dots, n)
	\end{eqnarray*}
	Other formulation: find a permutation $p$ of $n$ elements minimizing
	$\sum_{i=1}^n{ \sum_{j=1}^n{a_{ij} \cdot b_{p_i p_j}}}$
	\begin{itemize}
		\item $a_{ij}$ Frequency of occurrence of the symbol $j$ after the symbol $i$ in a sample text
		\item $b_{uv}$ Delay between typing a symbol in position $u$ and another in position $v$
	\end{itemize}
\end{frame}


%----------------------------------------------------

\subsection{Stable Set}


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


%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{itemize}[<+->]
		\item Set of elements $E$
		\item Dissimilarity measure $d(i, j) \geqslant 0$ between elements $i$ and $j \in E$
		\item Group similar elements and separate dissimilar elements
	\end{itemize}
	\begin{block}{Homogeneity measure of a cluster $G \subset E$}
		\begin{description}[<+->]
			\item[Diameter]Maximal value $d(i, j)$ for 2 elements $i$ and $j \in G$: $max_{i,j \in G} d(i,j)$
			\item[Radius]Maximal dissimilarity between the most central element and another in $G$: $min_{i \in G} max_{j \in G} d(i,j)$
			\item[Clique]Sum of dissimilarities between all pair of elements of $G$: $\sum_{i \in G}{\sum_{j \in G}{d(i,j)}}$
			\item[Star]Sum of dissimilarities between the most central element of $G$ and the others: $min_i \sum_{j \in G}{d(i,j)}$
		\end{description}
	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Example of a large unsupervised clustering problem: compression by quantization}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{vector_quantization}
		\end{center}
	\end{figure}
	With blocks of 15 pixels, clustering over millions of elements and $2^{14} = 16384$ centres, we can build a decent image with less than one bit per pixel
\end{frame}


%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Position of optimal points according to the dissimilarity measure}
	\framesubtitle{For the points of the Euclidean plane: $(0,1), (3,3), (5,0)$}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{medoid_median_gc_weber}
		\end{center}
	\end{figure}

\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Heterogeneity measures between two clusters $G$ and $H$}
	\begin{description}[<+->]
		\item[Separation]Minimum distance between two elements belonging to different groups: $min_{i \in G, j \in H} d(i,j)$
		\item[Cut]Sum of dissimilarities between elements of two different clusters: $\sum_{i \in G}{\sum_{j \in H}{d(i,j)}}$
		\item[Normalized cut]Average dissimilarity between elements of two different clusters: $\sum_{i \in G}{\sum_{j \in H}{d(i,j)}} / (|G|\cdot |H|)$
	\end{description}
\end{frame}

%--------------------------------------------
\begin{frame}
	\frametitle{Global Clustering Criteria}
	\begin{itemize}[<+->]
		\item{Maximize the smallest separation (or the smallest cut) between elements of 2 different clusters}
		\item{Minimize the largest diameter (or the largest radius, or the largest clique or the largest star) of a cluster}
		\item{Minimize the star sum (or the diameter, radius, clique sum)}
	\end{itemize}
\end{frame}

\subsubsection{$k$-Medoids or $p$-Median}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection: Partition Around Medoids (PAM)}
	\footnotesize
	\begin{block}
		{Minimize the star sum relatively to elements of $E$}
		\input{./algorithms/PAM}
	\end{block}
	\alert{Local Improvement Algorithm}
\end{frame}

\subsubsection{$k$-Means}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{block}
		{Minimize the star sum (square distance) relatively to gravity center of clusters}
		\input{./algorithms/kmeans}
	\end{block}
	\alert{Local Improvement Algorithm}
\end{frame}



\subsection{Graph Colouring Problem}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\footnotesize
	\begin{itemize}[<+->]
		\item Either the vertices or the edges of a graph can be coloured
		\item Edge colouring can be transformed into vertex colouring of the corresponding line graph
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{line_graph}
		\end{center}
	\end{figure}
	\begin{block}{NP-hard problem}
		However, colouring the edges of a bipartite graph is a simple problem
	\end{block}
\end{frame}