presentation.tex 14.5 KB
Newer Older
Aliaume Lopez's avatar
Aliaume Lopez committed
1 2 3 4 5
\documentclass[a4paper,10pt]{beamer}

\usecolortheme{whale}
\usecolortheme{orchid}
\usepackage[french]{babel}
Gaetan D's avatar
Gaetan D committed
6
\usepackage[utf8]{inputenc}
Aliaume Lopez's avatar
Aliaume Lopez committed
7
\usepackage{amsmath,amssymb}%for \mod, \bmod, ..
Gaetan D's avatar
r  
Gaetan D committed
8
\usepackage{amsthm,amsfonts,mathrsfs,bbold}
Aliaume Lopez's avatar
Aliaume Lopez committed
9 10 11 12
\usepackage[full,small]{complexity}
\usepackage{ stmaryrd }
\usepackage{ marvosym }

Aliaume Lopez's avatar
Aliaume Lopez committed
13 14
\usepackage[caption=false]{subfig}

Aliaume Lopez's avatar
Aliaume Lopez committed
15 16 17 18 19 20 21 22 23 24 25
%pour le tableau récapitualif 
\usepackage{hyperref}

\usepackage{enumerate,multicol}

\usepackage{tikz}
\usetikzlibrary{arrows,positioning,automata,shadows}

\newcommand{\Nat}{{\mathbb{N}}}
\newcommand{\eqv}{\Leftrightarrow}
\newcommand{\ds}{\vspace{0.5\baselineskip}}
Gaetan D's avatar
Gaetan D committed
26
\newcommand{\es}{\vspace{1\baselineskip}}
Aliaume Lopez's avatar
Aliaume Lopez committed
27 28

% Plan des sections et numéros des sections
Gaetan D's avatar
Gaetan D committed
29 30 31 32
\AtBeginSection[]{
  \frame{ 
    \frametitle{Plan}   
    \tableofcontents[currentsection]  }}
Aliaume Lopez's avatar
Aliaume Lopez committed
33 34 35
\setbeamertemplate{section in toc}[sections numbered]

% Titre
Aliaume Lopez's avatar
Aliaume Lopez committed
36
\title{\textbf{Optimisation Combinatoire \& Convexe} \\ Le problème du voyageur de commerce}
Aliaume Lopez's avatar
Aliaume Lopez committed
37 38 39 40 41 42
\author{Lopez Aliaume \and Douéneau Gaëtan}

\begin{document}

\maketitle 

Aliaume Lopez's avatar
Aliaume Lopez committed
43
\begin{frame}
Gaetan D's avatar
Gaetan D committed
44 45 46 47
    \frametitle{Problème du voyageur de commerce (TSP)}
    \begin{block}{Définition : TSP}
        Soit $G = \langle V, E \rangle$ un graphe (complet) 
        et $w : V \rightarrow R_+ \cup\{+ \infty\}$ une fonction de coût des arêtes. On cherche à calculer~:
Aliaume Lopez's avatar
Aliaume Lopez committed
48 49 50 51 52

        \[
            \min \{ w(C) ~|~ C \textrm{ cycle hamiltonien de } G \}
        \]
    \end{block}
Gaetan D's avatar
Gaetan D committed
53 54 55 56
    
    \es
    
    On considèrera $G$ non-orienté (problème symétrique).
Aliaume Lopez's avatar
Aliaume Lopez committed
57 58 59 60
\end{frame}

\begin{frame}
    \frametitle{Propriétés générales du problème}
Gaetan D's avatar
Gaetan D committed
61 62 63 64 65 66 67 68 69 70
    
        \begin{block}{Complexité}
        Problème de décision associé \NP-complet.
    \end{block}
       \begin{alertblock}{Approximabilité}
    Inapproximable à ratio constant, sauf si \P = \NP.
    
        \end{alertblock}
    
    
Aliaume Lopez's avatar
Aliaume Lopez committed
71 72 73 74 75
\end{frame}


\begin{frame}
    \frametitle{Dans le cas euclidien ou métrique}
Gaetan D's avatar
Gaetan D committed
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
    
           \begin{alertblock}{Restricition}
    On ne considère que des instances où la fonction de coût vérifie l'inégalité triangulaire.
    
        \end{alertblock}
        
                   \begin{exampleblock}{Exemple}
    Cas de la distance euclidienne dans le plan. Facilement représentable.
    
    Mais le problème de décision associé reste \NP-complet.
    
        \end{exampleblock}
        
        \ds

Gaetan D's avatar
pl  
Gaetan D committed
91
   Bonne nouvelle : le problème métrique est approximable à ratio constant.
Aliaume Lopez's avatar
Aliaume Lopez committed
92
\end{frame}
Aliaume Lopez's avatar
Aliaume Lopez committed
93

Aliaume Lopez's avatar
Aliaume Lopez committed
94 95 96 97

\begin{frame}
    \frametitle{TSPLIB}

Aliaume Lopez's avatar
Aliaume Lopez committed
98
    \begin{block}{TSPLIB95}
Gaetan D's avatar
pl  
Gaetan D committed
99
        TSPLIB une librairie d'instances de TSP de valeurs optimales connues (ou tight encadrement).
Aliaume Lopez's avatar
Aliaume Lopez committed
100 101
    \end{block}

Gaetan D's avatar
pl  
Gaetan D committed
102 103 104 105 106 107 108 109 110 111 112
    \begin{exampleblock}{Différentes instances}
    
    \begin{itemize}
    
    \item taille variable, entre 10 et 10000 sommets
\item différentes fonctions de coût (distance euclidienne, géodésique\dots).

\item parfois empruntés à la vie réélle (circuits électroniques, cartes\dots)


\end{itemize}
Aliaume Lopez's avatar
Aliaume Lopez committed
113
    \end{exampleblock}
Aliaume Lopez's avatar
Aliaume Lopez committed
114 115 116 117
\end{frame}



Aliaume Lopez's avatar
Aliaume Lopez committed
118
\section{Approximation}
Aliaume Lopez's avatar
Aliaume Lopez committed
119

Aliaume Lopez's avatar
Aliaume Lopez committed
120
\begin{frame}
Gaetan D's avatar
Gaetan D committed
121
    \frametitle{L'algorithme 2-OPT}
Aliaume Lopez's avatar
Aliaume Lopez committed
122

Gaetan D's avatar
Gaetan D committed
123
    \begin{block}{Algorithme pour optimiser un tour}
Aliaume Lopez's avatar
Aliaume Lopez committed
124 125 126 127 128
        Tant qu'on peut trouver deux arêtes 
        du tour $(v_1,v_2)$ et $(v_1', v_2')$ telles que 
        le tour en les remplaçant par $(v_1, v_2')$ et $(v_1',v_2)$
        a une valeur inférieure, on effectue cette opération.
    \end{block}
Gaetan D's avatar
Gaetan D committed
129 130
    
    DESSIN
Aliaume Lopez's avatar
Aliaume Lopez committed
131

Aliaume Lopez's avatar
Aliaume Lopez committed
132 133

    \begin{alertblock}{Temps}
Gaetan D's avatar
Gaetan D committed
134 135 136
        La complexité en temps dans le pire des cas est un problème ouvert.
        
        Cependant elle est raisonnable en pratique.
Aliaume Lopez's avatar
Aliaume Lopez committed
137
    \end{alertblock}
Aliaume Lopez's avatar
Aliaume Lopez committed
138 139
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
140

Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
141
\begin{frame}
Gaetan D's avatar
Gaetan D committed
142 143 144 145 146 147 148 149

\frametitle{Garantie d'approximation}
    
    \begin{block}{2-approximation}
    Basée sur un arbre couvrant de poids minimal. Complexité quadratique.
    
    \end{block}

Gaetan D's avatar
pl  
Gaetan D committed
150 151
    \begin{block}{1.5-approximation \cite{christofides1976}}
    Algorithme de Christofides : arbre couvrant de poids min + couplage de poids minimum.
Gaetan D's avatar
Gaetan D committed
152 153
    \end{block}
    \ds 
Gaetan D's avatar
pl  
Gaetan D committed
154
    C'est toujours le meilleur ratio connu \cite{karpinski2015}.
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
155 156 157 158 159
\end{frame}

\begin{frame}
    \frametitle{Combinaison des deux approches}

Gaetan D's avatar
Gaetan D committed
160
    \begin{exampleblock}{Exemple~: eil101 (valeur optimale : 629)}
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
161 162
        \begin{figure}
            \centering
Gaetan D's avatar
Gaetan D committed
163
            \subfloat[2-approximation seule (878)]{ 
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
164 165 166 167 168 169 170 171 172
                \includegraphics[width=4cm]{../images/00_APPROX_eil101_approx2.png}
            }
            \subfloat[Suivie de 2OPT (679)]{ 
                \includegraphics[width=4cm]{../images/00_APPROX_eil101_approx2_2opt.png}
            }
            \caption{Évolution de la solution}
        \end{figure}
    \end{exampleblock}
\end{frame}
Aliaume Lopez's avatar
Aliaume Lopez committed
173 174


Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
175
\begin{frame}
Gaetan D's avatar
Gaetan D committed
176
    \frametitle{Un algorithme glouton générique}
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
177

Gaetan D's avatar
Gaetan D committed
178 179
    \begin{block}{Glouton générique}
        On se donne un ordre sur les arêtes, et les ajoute de manière gloutonne jusqu'à obtenir un tour.
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
180 181
    \end{block}

Gaetan D's avatar
Gaetan D committed
182 183 184 185 186 187
    \begin{exampleblock}{Exemples}
        \begin{itemize}
        \item choix naturel : trier les arêtes en fonction de leur coût
                
        \item on verra plus loin qu'on peut les trier en fonction de la solution d'un autre problème.
        \end{itemize}
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
188 189 190 191
    \end{exampleblock}

\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
192

Aliaume Lopez's avatar
Aliaume Lopez committed
193
\begin{frame}
Gaetan D's avatar
Gaetan D committed
194 195
    \frametitle{Un algorithme glouton générique}
    \begin{block}{Exécution de l'algorithme}
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
196 197
        \begin{figure}
            \centering
Gaetan D's avatar
Gaetan D committed
198
            \subfloat[Ajout d'arêtes formant des chemins]{
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
199 200
                \includegraphics[width=5cm]{../images/00154_APPROX_kroA100_glouton.png}
            }
Gaetan D's avatar
Gaetan D committed
201
            \subfloat[Résultat final : tour ]{ 
Aliaume Lopez's avatar
Coucou  
Aliaume Lopez committed
202 203 204 205
                \includegraphics[width=5cm]{../images/00_APPROX_kroA100_glouton.png}
            }
            \caption{Algorithme glouton en utilisant les distances}
        \end{figure}
Aliaume Lopez's avatar
Aliaume Lopez committed
206 207 208
    \end{block}
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
209

Aliaume Lopez's avatar
Biiiiim  
Aliaume Lopez committed
210

Aliaume Lopez's avatar
Aliaume Lopez committed
211
\begin{frame}
Gaetan D's avatar
Gaetan D committed
212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244
\frametitle{Comparaison des méthodes}
    \begin{exampleblock}{Exemple~: berlin52 (52 points, valeur optimale à 7542)}
    
    \begin{multicols}{2}
    
    \raggedcolumns
     \begin{center}
   \includegraphics[width=4cm]{../images/00_APPROX_berlin52_approx2.png}
  
   2-approximation (10114)
   
   \ds
                

    \includegraphics[width=4cm]{../images/00_APPROX_berlin52_glouton.png}
    
     glouton (9951)
     
     \end{center}
     
     \columnbreak
 \begin{center}
\includegraphics[width=4cm]{../images/00_APPROX_berlin52_approx2_2opt.png}
                
2-approx + 2-OPT (7755)

\ds

 \includegraphics[width=4cm]{../images/00_APPROX_berlin52_glouton_2opt.png}
                
           glouton + 2-OPT(7657)
            \end{center}
        \end{multicols}
Aliaume Lopez's avatar
Aliaume Lopez committed
245
    \end{exampleblock}
Aliaume Lopez's avatar
Aliaume Lopez committed
246 247
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
248

Gaetan D's avatar
pl  
Gaetan D committed
249 250 251 252 253 254 255







Gaetan D's avatar
Gaetan D committed
256
\section{Problème linéaire et bornes inférieures}
Aliaume Lopez's avatar
Aliaume Lopez committed
257

Aliaume Lopez's avatar
Aliaume Lopez committed
258

Aliaume Lopez's avatar
Aliaume Lopez committed
259
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
260
    \frametitle{Programme linéaire en nombres entiers}
Aliaume Lopez's avatar
Aliaume Lopez committed
261

Gaetan D's avatar
pl  
Gaetan D committed
262
    \begin{block}{PLNE associé}
Aliaume Lopez's avatar
Aliaume Lopez committed
263 264 265
        \begin{equation} \label{eqn:primal:ilp}
            \boxed{
            \begin{array}{rlc}
Gaetan D's avatar
pl  
Gaetan D committed
266 267 268 269 270
                \textrm{Minimiser} & \displaystyle \sum_{uv \in E} c_{uv} x_{uv} & \\
                            \textrm{Avec}     & \displaystyle \forall u \in V, &\displaystyle  \sum_{uv \in E} x_{uv} = 2 \\
                             & \onslide<2->\displaystyle \forall \varnothing \subsetneq S \subsetneq E, &\displaystyle  \sum_{uv \in \delta(S)} x_{uv} \geq 2 \\
                             \onslide<1->
                             & \displaystyle \forall uv \in E, & x_{uv} \in \{0,1\} 
Aliaume Lopez's avatar
Aliaume Lopez committed
271 272 273 274 275
            \end{array}
            }
        \end{equation}

    \end{block}
Gaetan D's avatar
pl  
Gaetan D committed
276 277
    
    \onslide<3->
Aliaume Lopez's avatar
Aliaume Lopez committed
278 279

    \begin{exampleblock}{Relaxation linéaire}
Gaetan D's avatar
pl  
Gaetan D committed
280
        Remplacer la dernière contrainte par $0 \leq x_{uv} \leq 1$, donne une \emph{borne inférieure} au TSP.
Aliaume Lopez's avatar
Aliaume Lopez committed
281 282 283 284
    \end{exampleblock}

\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
285
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
286
    \frametitle{Le problème n'est pas entier}
Aliaume Lopez's avatar
Aliaume Lopez committed
287

Gaetan D's avatar
pl  
Gaetan D committed
288
    \begin{exampleblock}{Contre-exemple~: ts225 (optimum à 126643)}
Aliaume Lopez's avatar
Aliaume Lopez committed
289 290
        \begin{figure}
            \centering
Gaetan D's avatar
pl  
Gaetan D committed
291 292
            \subfloat[Optimum du PL($115605$)]{
                \includegraphics[width=5cm]{../images/0CVX_ts225_separationfinie.png}
Aliaume Lopez's avatar
Aliaume Lopez committed
293
            }
Gaetan D's avatar
pl  
Gaetan D committed
294
            \subfloat[Une approximation à $138954$]{ 
Gaetan D's avatar
pl  
Gaetan D committed
295
                \includegraphics[width=5cm]{../images/0CVX_ts225_approxPL.png}
Aliaume Lopez's avatar
Aliaume Lopez committed
296 297 298 299 300 301 302 303
            }
            \caption{Programme linéaire sur ts225}
        \end{figure}

    \end{exampleblock}

\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
304
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
305 306 307 308
    \frametitle{Oracle de séparation}
    \begin{alertblock}{Problème}
    
        Nombre exponentiel de contraintes\dots
Aliaume Lopez's avatar
Aliaume Lopez committed
309 310
    \end{alertblock}

Gaetan D's avatar
pl  
Gaetan D committed
311 312 313 314
    \begin{block}{Solution}
        N'ajouter les contraintes de sous-tour que quand elles sont violées.
        
        Idée : trouver un oracle de séparation.
Aliaume Lopez's avatar
Aliaume Lopez committed
315
    \end{block}
Gaetan D's avatar
pl  
Gaetan D committed
316 317 318
    
    \onslide<2->
    
Aliaume Lopez's avatar
Aliaume Lopez committed
319 320
    \begin{block}{Algorithme de séparation}
        \[
Gaetan D's avatar
pl  
Gaetan D committed
321
            v_1 \leq v_2 \leq \dots \leq v^* \leq \text{OPT\_TSP}
Aliaume Lopez's avatar
Aliaume Lopez committed
322
        \]
Aliaume Lopez's avatar
Aliaume Lopez committed
323 324 325
    \end{block}
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
326
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
327
    \frametitle{Oracle de séparation}
Aliaume Lopez's avatar
Aliaume Lopez committed
328

Gaetan D's avatar
pl  
Gaetan D committed
329
    \begin{block}{Coupe minimale et séparation}
Aliaume Lopez's avatar
Aliaume Lopez committed
330
        \begin{center}
Gaetan D's avatar
pl  
Gaetan D committed
331
            Contrainte violée $\iff$ MinCut $< 2$
Aliaume Lopez's avatar
Aliaume Lopez committed
332 333 334 335 336
        \end{center}
    \end{block}

    \begin{block}{Calculs}
        \begin{itemize}
Gaetan D's avatar
pl  
Gaetan D committed
337
            \item Calcul de la coupe minimale (en temps polynomial)
Aliaume Lopez's avatar
Aliaume Lopez committed
338
            \item Calcul de la contrainte violée à partir 
Gaetan D's avatar
pl  
Gaetan D committed
339
                de la coupe minimale (linéaire)
Aliaume Lopez's avatar
Aliaume Lopez committed
340 341 342 343 344
        \end{itemize}
    \end{block}

\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
345
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
346
    \frametitle{Oracle de séparation}
Aliaume Lopez's avatar
Aliaume Lopez committed
347 348 349
    \begin{exampleblock}{Exemple~:}
        \begin{figure}
            \centering
Aliaume Lopez's avatar
Boom  
Aliaume Lopez committed
350 351
            \subfloat[Itération 1 (7337)]{
                \includegraphics[width=2cm]{../images/0CVX_rd100_simple_1.png}
Aliaume Lopez's avatar
Aliaume Lopez committed
352
            }
Aliaume Lopez's avatar
Boom  
Aliaume Lopez committed
353 354 355 356 357
            \subfloat[Itération 11 (7578)]{
                \includegraphics[width=2cm]{../images/0CVX_rd100_simple_11.png}
            }
            \subfloat[Itération 21 (7867)]{
                \includegraphics[width=2cm]{../images/0CVX_rd100_simple_21.png}
Aliaume Lopez's avatar
Aliaume Lopez committed
358
            }
Aliaume Lopez's avatar
Boom  
Aliaume Lopez committed
359 360
            \subfloat[Itération 46 et fin (7899)]{ 
                \includegraphics[width=2cm]{../images/0CVX_rd100_separationfinie.png}
Aliaume Lopez's avatar
Aliaume Lopez committed
361
            }
Gaetan D's avatar
pl  
Gaetan D committed
362
            \caption{Programme linéaire sur rd100 (7910)}
Aliaume Lopez's avatar
Aliaume Lopez committed
363 364 365
        \end{figure}
    \end{exampleblock}
\end{frame}
Gaetan D's avatar
pl  
Gaetan D committed
366

Aliaume Lopez's avatar
Aliaume Lopez committed
367

Aliaume Lopez's avatar
Aliaume Lopez committed
368

Gaetan D's avatar
pl  
Gaetan D committed
369 370 371 372 373 374 375 376 377 378 379 380
\begin{frame}
    \frametitle{Un encadrement de la solution}
    \begin{block}{Borne inférieure}
       Permet d'obtenir des bornes inférieures, mais pas de tour approché ! Pourtant on a une information "précieuse".
    \end{block}
    
        \begin{alertblock}{Approximation}
       Utiliser le glouton sur les résultats du PL.
    \end{alertblock}
    \ds
    Combiné avec 2-OPT, donne de bons résultats.
\end{frame}
381

Aliaume Lopez's avatar
Aliaume Lopez committed
382
\section{Outils associés}
Aliaume Lopez's avatar
Aliaume Lopez committed
383

Gaetan D's avatar
pl  
Gaetan D committed
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
\begin{frame}
\frametitle{Parsing de TSPLIB}

\es

    \begin{exampleblock}{Différentes données à parser}
        \begin{itemize}
            \item matrice explicite des coûts
            \item coordonnées des sommets dans le plan (distance euclidienne)
            \item distance géodésique
        \end{itemize}
    \end{exampleblock}
    
    \ds
    
      \begin{alertblock}{Représentation}
        Distance euclidienne dans le plan : dessin sur Pygame.
    \end{alertblock}
    
    
\end{frame}
Gaetan D's avatar
pl  
Gaetan D committed
405

Aliaume Lopez's avatar
Aliaume Lopez committed
406 407

\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
408 409
\frametitle{Algèbre linéaire}

Aliaume Lopez's avatar
Aliaume Lopez committed
410

Gaetan D's avatar
pl  
Gaetan D committed
411 412
    \begin{block}{Inversion de matrice}
        Implémentation du pivot de Gauss.
Aliaume Lopez's avatar
Aliaume Lopez committed
413
    \end{block}
Gaetan D's avatar
pl  
Gaetan D committed
414 415 416
    
    \ds
    
Gaetan D's avatar
pl  
Gaetan D committed
417 418 419 420 421 422 423 424 425 426 427
  
    Sans surprise, de très mauvaises performances : $140$s pour inverser 100 matrices aléatoires (dimension $100 \times 100$).
    
    \es
    
        \begin{block}{Numpy}
        \texttt{numpy.linalg.inv}
    \end{block}
    
    \ds 
        $0.9$s pour inverser les 100 matrices\dots
Aliaume Lopez's avatar
Aliaume Lopez committed
428 429 430 431 432
\end{frame}



\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
433 434

\frametitle{Simplexe}
Gaetan D's avatar
trucs  
Gaetan D committed
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453

\begin{block}{Implémentation}

\begin{itemize}

\item PL sous forme standard : Maximiser $c^Tx$ avec $Ax = b$, $x \ge 0$

\item règle de Bland pour le pivotage

\item résoudre un problème de Phase 1, et un autre en Phase 2

\end{itemize}

\end{block}

\ds

Mais des performances immondes.

Aliaume Lopez's avatar
Aliaume Lopez committed
454 455 456
\end{frame}

\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
457 458 459 460

\frametitle{Simplexe}
    \begin{block}{\texttt{scipy.optimize.linopt}}
        Implémentation en Python de l'algorithme du simplexe.
Aliaume Lopez's avatar
Aliaume Lopez committed
461
    \end{block}
Gaetan D's avatar
pl  
Gaetan D committed
462 463 464 465 466 467
    
    \ds
    
    Ce n'est pas très efficace. Ni très précis.
    
    \ds
Aliaume Lopez's avatar
Aliaume Lopez committed
468 469

    \begin{block}{\texttt{CVXPy}}
Gaetan D's avatar
pl  
Gaetan D committed
470
        Interface élégante de \texttt{CVXopt} associée à Python. Très efficace.
Aliaume Lopez's avatar
Aliaume Lopez committed
471 472 473
    \end{block}
\end{frame}

Aliaume Lopez's avatar
Stoer  
Aliaume Lopez committed
474
\begin{frame}
Gaetan D's avatar
pl  
Gaetan D committed
475

Gaetan D's avatar
pl  
Gaetan D committed
476
\frametitle{Coupe minimale}
Gaetan D's avatar
trucs  
Gaetan D committed
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503

\begin{block}{Implémentation "naïve"}

Recherche des coupes minimales entre tous les couples de sommets.

O($|V|^3|E|^2$) (avec Edmonds-Karp)

\end{block}

\ds

Des performances suffisantes pour un "mauvais" simplexe.

\es

\begin{block}{Stoer-Wagner}

Tout faire en même temps.
\ds


Complexité : O($|V|(|E| + |V| \log|V|)$).
\end{block}
\ds

Implémenté dans NetworkX.

Aliaume Lopez's avatar
Stoer  
Aliaume Lopez committed
504 505
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
506
\section{Résultats obtenus}
Aliaume Lopez's avatar
Aliaume Lopez committed
507

Aliaume Lopez's avatar
Biiiiim  
Aliaume Lopez committed
508
\begin{frame}
Aliaume Lopez's avatar
Aliaume Lopez committed
509

Gaetan D's avatar
pl  
Gaetan D committed
510 511
\frametitle{Bornes inférieures précises sur de grosses instances}

Aliaume Lopez's avatar
Aliaume Lopez committed
512
    \begin{exampleblock}{Sur un problème avec 657 points}
Aliaume Lopez's avatar
Aliaume Lopez committed
513 514
        \begin{figure}
            \centering
Aliaume Lopez's avatar
Aliaume Lopez committed
515
            \subfloat[Solution ($48452$)]{ 
Aliaume Lopez's avatar
Aliaume Lopez committed
516 517
                \includegraphics[width=5cm]{../images/0CVX_d657_separationfinie.png}
            }
Aliaume Lopez's avatar
Aliaume Lopez committed
518
            \subfloat[Tour associé ($51181$)]{ 
Aliaume Lopez's avatar
Aliaume Lopez committed
519 520 521 522 523
                \includegraphics[width=5cm]{../images/0CVX_d657_approxPL.png}
            }
            \caption{Le problème d657 de valeur optimale $48912$}
            \label{fig:pl:d657}
        \end{figure}
Aliaume Lopez's avatar
Aliaume Lopez committed
524 525
    \end{exampleblock}

Gaetan D's avatar
hop  
Gaetan D committed
526

Aliaume Lopez's avatar
Aliaume Lopez committed
527

Aliaume Lopez's avatar
Biiiiim  
Aliaume Lopez committed
528 529
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
530 531
\begin{frame}
    plus de résultats 
Aliaume Lopez's avatar
Biiiiim  
Aliaume Lopez committed
532 533
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
534
\section{Dualité}
Aliaume Lopez's avatar
Aliaume Lopez committed
535

Aliaume Lopez's avatar
Aliaume Lopez committed
536 537 538 539 540
\begin{frame}

\begin{equation} \label{eqn:dual}
    \boxed{
    \begin{array}{rll}
Gaetan D's avatar
trucs  
Gaetan D committed
541 542
        \textrm{Maximiser} &  \displaystyle- \sum_{uv \in E'} \lambda_{1,uv} x_{uv} - 2 \sum_{u \in V} \nu_u + 2 \sum_{S \in W} \lambda_{3,S} \\
                  \textrm{Avec}     & \lambda_1 \geq 0 \\
Aliaume Lopez's avatar
Aliaume Lopez committed
543 544 545 546 547 548 549 550 551 552 553 554 555 556 557
                     & \lambda_2 \geq 0 \\
                     & \lambda_3 \geq 0 \\
                     & c_{E'} - \lambda_1 + \lambda_2 + {}^t D_{E'} \nu - {}^t G_{E'} \lambda_3 = 0
    \end{array}
    }
\end{equation}

Avec $D_{E'}$ la matirce d'incidence du graphe restreint à $E'$, et $G_{E'}$ la matrice qui vérifie~:


\begin{equation*}
    (G_{E'})_{S,uv} = \begin{cases} 1 & \textrm{ si } uv \in \delta(S) \\ 0 & \textrm{ sinon } \end{cases}
\end{equation*}
\end{frame}

Aliaume Lopez's avatar
Aliaume Lopez committed
558 559 560 561 562 563 564 565 566 567 568 569 570
\begin{frame}
    \frametitle{Borne inférieure avec le dual}

    \begin{block}{Algorithme}
        Tant qu'une arête viole une contrainte du dual, on ajoute 
        l'arête et les contraintes associées. 
    \end{block}

    En pratique~: on ajoute toutes les arêtes.


\end{frame}

Gaetan D's avatar
trucs  
Gaetan D committed
571 572 573 574 575 576 577 578
\section*{Conclusion}
\begin{frame}
    \frametitle{Conclusion}

    \begin{block}{Contraintes supplémentaires}
        Copier ici ce qu'on lira de la présentation de Nathanaël 
    \end{block}
\end{frame}
Aliaume Lopez's avatar
Aliaume Lopez committed
579 580


Aliaume Lopez's avatar
Aliaume Lopez committed
581
\section*{Bibliographie}
Aliaume Lopez's avatar
Aliaume Lopez committed
582

Gaetan D's avatar
pl  
Gaetan D committed
583 584


Aliaume Lopez's avatar
Aliaume Lopez committed
585
\begin{frame}[allowframebreaks]
Aliaume Lopez's avatar
Aliaume Lopez committed
586

Gaetan D's avatar
pl  
Gaetan D committed
587 588
\frametitle{Bibliographie}

Aliaume Lopez's avatar
Aliaume Lopez committed
589
\bibliographystyle{apalike}
Gaetan D's avatar
pl  
Gaetan D committed
590
\bibliography{presentation}
Aliaume Lopez's avatar
Aliaume Lopez committed
591

Aliaume Lopez's avatar
Aliaume Lopez committed
592
\end{frame}
Aliaume Lopez's avatar
Aliaume Lopez committed
593

Gaetan D's avatar
pl  
Gaetan D committed
594 595 596



Aliaume Lopez's avatar
Aliaume Lopez committed
597
\end{document}