\section{Problem Modelling \label{chap:problem_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{Objective Function and Fitness Function}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}
%----------------------------------------------------
\begin{frame}
	\frametitle{Natural objective function for graph colouring}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{feasible_colouring}
		\end{center}
	\end{figure}
	\begin{align*}
		\textnormal{Minimize} : & \quad c  =  f_1(s)                                             \\
		\textnormal{S.t.}:      & \quad 2 \textnormal{ adjacent vertices have different colours} \\
		\textnormal{and}:       & \quad \textnormal{Number of colours used by }s \leqslant    c
	\end{align*}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Less Intuitive Fitness Function: Edge Orientation}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{colouring_path}
		\end{center}
	\end{figure}
	\begin{align*}
		\textnormal{Minimize } :      & \quad  f_2(s) =  \textnormal{Longest Path in } G \textnormal{ oriented} \\
		\nonumber \textnormal{S.t.} : & \quad \textnormal{The edge orientation } G \textnormal{ has no circuit}
	\end{align*}
\end{frame}

\subsubsection{Lagrangian Relaxation}
\begin{frame}{\insertsubsubsection}{Principle}
	\begin{itemize}[<+->]
		\item Introduce one or more constraints into the objective
		      \begin{eqnarray*}
			      \textnormal{Minimize}	&	f(s) \\
			      \textnormal{S.t.} 	&	s \in S		& \textnormal{Easy constraint} \\
			      \textnormal{and}	&	g(s) \leqslant 0		& \textnormal{Makes the problem hard}
		      \end{eqnarray*}

		\item With a penalty $\lambda$
		      \begin{eqnarray*}
			      \textnormal{Minimize}	&	f(s) + \lambda \cdot max(g(s), 0)			&\textnormal{with }	\lambda  \textnormal{, a parameter}\\
			      \textnormal{S.t.}	&		s \in S &
		      \end{eqnarray*}
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Fitness Function Obtained with Lagrangean Relaxation}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{colouring_min_violations}
		\end{center}
	\end{figure}
	\begin{align*}
		\textnormal{Minimize} :       & \quad f_3(s)  =   c + \lambda \cdot \textnormal{ Number of edges with both end with the same colour} \\
		\nonumber \textnormal{S.t.} : & \quad \textnormal{Number of colours used }s \leqslant    c
	\end{align*}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Partial Colouring}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{partial_colouring}
		\end{center}
	\end{figure}
	\begin{align*}
		\textnormal{Minimize } :      & \quad  f_4(s)  =  \textnormal{Number of uncoloured vertices}    \\
		\nonumber \textnormal{S.t.} : & \quad 2 \textnormal{ adjacent vertices have different coulours}
	\end{align*}
\end{frame}


\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{Lagrangian Relaxation for the TSP with 1-tree}
		\begin{itemize}[<+->]
			\item A 1-tree in a graph with vertices numbered from $1$ to $n$ is a tree on vertices $2$ to $n$ with 2 edges added from vertex $1$
			\item TSP modelling in terms of 1-tree
			      \begin{equation*}
				      \begin{array}{rlll}
					      \min        z = & \sum_{(i,j) \in H}{d_{ij}x_{ij}} &   &                           \\
					      \mbox{S.t.}     & \sum_{j = 1}^{n}{x_{ij}}         & = & 2 \quad (i = 1, \dots, n) \\
					      \mbox{et}       & H \mbox{ is a 1-tree}            &   &                           \\
				      \end{array}
			      \end{equation*}
			\item Lagrangian relaxation:
			      \begin{equation*}
				      \begin{array}{rlll}
					      \min        z(\lambda) = & \sum_{(i,j) \in H}{d_{ij}x_{ij}} & + \sum_{i = 1}^{n}{\lambda_i(\sum_{j = 1}^{n}{x_{ij}} - 2) } & \\
					      \mbox{S.t.}              & H \mbox{ is a 1-tree}            &                                                              & \\
				      \end{array}
			      \end{equation*}
			\item The objective can be rewritten with modified distances $d_{ij} + \lambda_i + \lambda_j$
			\item For $\lambda$ known, the problem is to find a minimum 1-tree
			\item $z(\lambda)$ provides a lower bound to the TSP tour
			\item If the 1-tree is not a tour for some $\lambda$, they can be modified
			      \begin{itemize}
				      \item Increase $\lambda_i$ if the degree of vertex $i$ is larger than 2
				      \item Decrease $\lambda_i$ if the degree is 1
			      \end{itemize}
		\end{itemize}
	\end{frame}
\end{framefont}

\begin{frame}
	\frametitle{Applying the 1-tree relaxation on the TSP}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{one_tree}
		\end{center}
	\end{figure}
	\begin{itemize}
		\item Left: 1-tree on the TSP instance \emph{tsp225} obtained with all $\lambda$ values set to 0
		\item Top right: the 1-tree obtained with the first modification of the $\lambda$
		\item Bottom right: the 1-tree obtained after iterating the process
	\end{itemize}
\end{frame}

\subsection{Multi-Objectives Optimization}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%--------------------------------------------
\begin{frame}
	\frametitle{Multi-Objectives Models}
	\begin{block}{$K$ objectives}
		\begin{itemize}
			\item $f_1(s), f_2(s), \dots f_K(s)$
			\item The objectives are partially antagonist (price/time/durability)
		\end{itemize}
	\end{block}
	\begin{align*}
		\textnormal{``Minimize''} : & \quad  \vec f(s)  =  (f_1(s), \dots, f_K(s)) \\
		\nonumber \textnormal{S.t.} & \quad s \in S
	\end{align*}
	\begin{itemize}[<+->]
		\item A solution $s_1$ \alert{dominate} a solution $s_2$ if $s_1$ is better than $s_2$ on one objective at least (it can be worse than $s_2$ on the other objectives)
		\item A non-dominated solution is \alert{Pareto-optimal} or \alert{efficient}
		\item A solution on the convex hull of the Pareto set is \alert{supported}
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Example: Cheap and Short Path}
	\begin{itemize}
		\item Cost of the path
		\item Duration of the path
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{multiobjective_trip}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Pareto Set}
%----------------------------------------------------
\begin{frame}
	\frametitle{Representation of the solutions in a cost/time diagram}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{multiobjective}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Scalarizing}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	Reduce to a single-objective problem by assigning weights $w_1, \dots, w_K$ for each objective\\
	\begin{align}
		\nonumber \textnormal{Minimize }: & \quad \sum_{i = 1}^K{w_i \cdot f_i(s)} \\
		\nonumber \textnormal{S.t.}       & \quad s \in S
	\end{align}
	Shortcoming: Unsupported effective solutions are not achievable
\end{frame}

\subsubsection{Sub-goals to Reach}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{align}
		\nonumber  \textnormal{Minimize}: & \quad \vec f(s)  =  (f_2(s), \dots, f_K(s)) \\
		\nonumber \textnormal{S.t.}       & \quad f_1(s) \leqslant v_1                  \\
		\nonumber \textnormal{with}       & \quad s \in S
	\end{align}
\end{frame}

\subsection{Practical Applications Modelled as Classical Problems}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\begin{frame}{Industrial TSP Application: 3D-Printing}
	\begin{center}
		\includegraphics{lvnf.jpg}
	\end{center}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{3D-Printing}
	\begin{block}{Improductive moves of the extrusion head}
		Solution obtained with \emph{PrusaSlicer} and possible improvement by solving a TSP
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{lvnf252_257}
		\end{center}
	\end{figure}

\end{frame}

%----------------------------------------------------
\begin{framefont}{\scriptsize}
	\begin{frame}
		\frametitle{Minimising unproductive moves in 3D printing}
		\begin{block}
			{Representation of the printing of 2 segments with ends $a-c$ and $e-g$}
			\begin{itemize}[<+->]
				\item Force the head to print the segment by introducing an intermediate node reasonably accessible only from the ends of the segment
				\item Pay a penalty (e.g. $p = M/10$) if we change the layer
				\item A Hamiltonian path (passing through all vertices) of minimum cost corresponds to the printing of all segments; all segments of a layer are printed before moving to another layer; unproductive moves is minimized
			\end{itemize}
		\end{block}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{TSP3Dprint}
			\end{center}
		\end{figure}

	\end{frame}
\end{framefont}

\subsubsection{Linear Assignment Modelled by Minimum Cost Flow}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	What is the maximum number of pairs that can be formed between girls and boys? \\
	A compatible pair is represented by an edge in a bipartite graph \\
	\begin{figure}[h]
		\begin{center}
			\includepdftex{matching_flow}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Map Labelling Modelled by Stable Set}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{itemize}[<+->]
		\item Create as many vertices as there are possible positions for each object to label
		\item Connect 2 incompatible vertices with an edge
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{map_labelling}
		\end{center}
	\end{figure}
	
\end{frame}

