%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[frenchb]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\usepackage[english,francais]{babel}
\makeatletter
% Yucky bugware to make hyperref and babel[francais] work together
\def\url#1{{\selectlanguage{english}\hyper@normalise\url@{#1}}}
\def\href#1#2{{\selectlanguage{english}\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}

\usepackage[english,francais]{babel}
\makeatother
\begin{document}

\chapter{Conclusion}


\section{Qu'est-ce qu'un problème d'optimisation discrète ?}

On a un ensemble fini, et on veut minimiser une fonction définie sur
cet ensemble.

Facile, il suffit d'énumérer tous les éléments de l'ensemble!

Sauf que l'ensemble est habituellement très gros \ldots{}


\section{Comment aborder un tel problème ?}

L'essentiel est de trouver un \emph{bon modèle:}

\begin{itemize}
\item Suffisament simple pour être traité (si possible déjà étudié dans
la littérature!)
\item Suffisament expressif pour bien représenter la réalité
\end{itemize}
Un tout petit changement de modèle peut entrainer de gros changements
de complexité!

(Cf. ordonnancement).

Alors, quelles questions se poser ?

\begin{enumerate}
\item Quelles sont les variables ? (comment mesurer une solution au problème)
\item Quelles sont les contraintes ? 

\begin{itemize}
\item Peut-on l'exprimer en fonction des variables ?
\item Quelles contraintes sont essentielles ? 
\item Quelles contraintes peuvent relaxées ?
\end{itemize}
\item Quelle est la fonction à optimiser ?

\begin{itemize}
\item Peut-on l'exprimer simplement en fonction des variables ?
\item Peut-on l'approcher par une fonction plus simple (par ex. linéaire)
?
\end{itemize}
\end{enumerate}
\begin{example*}
Problème du boucher.
\end{example*}

\section{Reconnaître les difficultés}


\subsection{Problèmes de décision}

\begin{example*}
Problème du sac à dos
\end{example*}

\subsection{Problèmes en entiers (discret<-> continu)}

\begin{example*}
Résolution d'équations diophantienne (équations linéaires en entiers)

Une droite contient-elle un point à coordonnées entières ?

Démontrer que $\sqrt{2}$, $e$ ou $\pi$ sont irrationnels n'est
pas trivial.
\end{example*}

\section{Modèles et méthodes polynomiales}


\subsection{Programation linéaire}

Principe: simplifier le problème en le rendant continu.

\begin{example*}
Recherche de couplage max dans un graphe biparti.
\end{example*}
Plusieurs modèles de plus en plus simples:

\begin{enumerate}
\item Programmation linéaire générale

\begin{itemize}
\item Méthode du simplexe
\item Méthode des points intérieurs
\item Méthode de l'ellipsoïde
\item Résolution polynomiale
\item Théorème de dualité
\end{itemize}
\item Problèmes de transport, avec ou sans contraintes 

\begin{itemize}
\item Algorithme du simplexe pour les réseaux
\item Théorème d'intégralité!
\item Beaucoup plus rapide \emph{en pratique}.
\end{itemize}
\item Problèmes de flot

\begin{itemize}
\item Algorithme de Ford-Fulkerson (parcours en profondeur dans un graphe)
\item Beaucoup plus rapide: $O(n^{3})$
\end{itemize}
\end{enumerate}

\subsection{Algorithmes dans les graphes, ...}


\section{Problèmes non-polynomiaux}

La plupart du temps, il n'y a pas d'algorithme polynomial, et on est
obligé de passer à des méthodes énumératives.

Comment gérer l'explosion combinatoire?

En fait la plupart des idées ci-dessous sont parfaitement naturelles:
vous les utilisez déjà intuitivement dans la vie de tous les jours.


\subsection{Méthodes arborescentes}

Organiser la recherche exhaustive, de façon à examiner des solutions
proches les unes des autres, et limiter les recalculs.


\subsection{Restreindre le domaine de recherche}

Rendre faisable une recherche exhaustive en restreignant le domaine
de recherche.


\subsubsection{Minorer et majorer la fonction objectif}

\begin{enumerate}
\item Résolution approchée par des heuristiques -> minoration

\begin{example*}
Utiliser Coffman-Graham pour ordonnancer des tâches unitaires sur
$3$ processeurs ou plus.
\end{example*}
\item Méthodes de relaxation -> majoration


Relâcher certaines contraintes

\begin{example*}
Enlever la contrainte d'intégralité dans un problème de programmation
linéaire général.
\end{example*}
\item Trouver un problème dual -> majoration


Si on a un théorème min-max, c'est encore mieux

\end{enumerate}

\subsubsection{Restreindre le domaine de recherche à un sous-ensemble dominant}

\begin{example*}
Pour l'ordonnancement de tâches unitaires, on peut toujours trouver
un ordonnancement optimal calé à gauche.
\end{example*}
Un tel sous-ensemble de solutions est \emph{dominant.}

On peut restreindre le domaine de recherche à ce sous-ensemble.

\begin{example*}
Pour l'ordonnancement de tâches sans contraintes de resources, cette
approche est suffisante pour donner un algorithme polynomial (méthode
PERT).
\end{example*}

\subsubsection{Programmation dynamique}

Utiliser l'indépendances de certaines décisions pour contracter des
branches similaires dans un arbre de recherche.


\subsection{\emph{«C'est pas parfait, mais ca fera l'affaire}»}

Pour beaucoup de problèmes, il existe des algorithmes polynomiaux
donnant une solution approchée avec garantie de qualité (à moins de
$x$\% de la solution optimale).

C'est très souvent largement suffisant dans les applications.

Voire mieux: une famille d'algorithmes $A_{n}$ de complexité polynomiale
tels que:

\begin{itemize}
\item Le degré de complexité tends vers l'infini avec $n$.
\item La garantie de qualité $x_{n}$ tends vers $0$ avec $n$.
\item L'algorithme limite $A_{\infty}$ est optimal.
\end{itemize}
\begin{example*}
Dans une méthode arborescente, 
\end{example*}
On peut donc complèment choisir, suivant les besoins, un compromis
vitesse / qualité.

\begin{example*}
Algorithme LLL.
\end{example*}

\section{À vous de jouer!}

\begin{thebibliography}{1}
\bibitem{Carlier_Chretienne.PO}\emph{Problèmes d'ordonnancement, Modélisation, Complexité, Algorithmes};
J.~Carlier, P.~Chrétienne, Masson, Études et recherches en informatique,
1988.
\bibitem{Sakarovitch.OC}\emph{Optimisation combinatoire} (2 tomes), Michel Sakarovitch, Hermann\end{thebibliography}

\end{document}
