---
tags: MSE / semestre 2
---

# MSE - Optimization

## 1. Semaine 1

### 1.1. Description générale d'un problème d'optimisation

<img src="https://hackmd.io/_uploads/H1eEa3Egq.png" width="92%">

* $\Omega$ : **ensemble de configurations** (solutions) du problème (*espace de recherche*) ;
* $\text{C}$ : **fonction de coût** (objectif) (*fonction de fitness*).
- $x^{\prime}$ : n'est pas obligatoirement unique.

### 1.2. Exemples

1. Sachant qu'il y une équipe qui travaille 7 heures et l'autre 8 et que les coûts bruts de travail sont plus élevés pour l'équipe 8 que la 7 : optimiser le plan de travail couvrant le besoin en personnel d'une entreprise avec des coûts minimaux.
2. Typiqument coût de disposition de fibre optique entre 12 villages. On va vouloir tous les reliés avec coût minimal (donc simplement MST en fait).
3. Résolution d'un Sudoku de façon optimisée.

### 1.3. Geppetto

Juste faire attention lors de l'établissement **final** des contraintes de départ :

* Pour les contraintes **a** et **b** ce sont bien des heures que l'on est en train de comparer :
* Pour la **a** 2 et 1 sont respectivement le nb d'heures de finissage pour un soldat et un train ;
* Pour la **b** 1 et 1 sont respectivement le nb d'heures de menuiserie pour un soldat et un train.
* Pour la contrainte **c** c'est simplement le nb de production maximale du nombre de soldat ++**ET**++ des contraintes qui n'ont lieu d'être que lors de la phase de développement pure (*Python*).


> **Autrement, exemple plutôt parlant, voir slide 14 à 16.**

### 1.4. Types d'approches

> Pour un problème avec fonction objectif linéaire, s'il n'y a pas de contraintes, alors la solution est infini.

> Pour un problème avec fonction objectif linéaire et contraintes linéaires, alors on peut trouver une solution (ici la quantité maximale).

> Sous certaines conditions, **typiquement des contraintes incompatibles entre-elles**, il est possible que le problème ne possède pas de solution admissible. Par exemple, ici, il n'est pas possible d'avoir une quantité > 40 litres dont le prix < 1000F.

> Si on travail avec des variables entières, le résultat doit évidemment l'être également. Ici, la réponse ne serait donc pas $\frac{10}{3} = 3.3$ mais bien évidemment $\text{floor(}\frac{10}{3}{)} = 3$.

> Pour un problème avec fonction objectif **non-linéaire**, même sans contrainte, une solution finie peut exister. Typiquement, ici, la hauteur maximale est le maxima de la courbe (tangeante horizontale à la courbe où dérivée nulle).

> Pour un problème avec fonction objectif non-linéaire, une solution finie n'est cependant pas garantie. En effet, une tangeante horizontale n'identifie pas **nécessairement** une solution. Là, on voit bien que ce n'est ni un maxima, ni un minima.

> Évidemment impossible, pas de solution. Fonction objectif non-dérivable : n'a pas la même valeur de limite à gauche et à droite en chaque point de la courbe.

> On reste bloqué à gauche dans le premier minima rencontré, alors que le véritable minima du système est en **$X^{*}$**. C'est un problème car on échappe ainsi à la meilleure solution. (Néanmoins, suivant les cas, il est possible qu'on se satisfasse de cette solution).

### 1.6. Types de modèles et de méthodes d'optimisation

1. Confiné/Non-confiné :
* Les problèmes confinés possèdent des restrictions qui limitent l'ensemble de solution admissibles noté $S$ à un sous-ensemble réel de $R^{n}$ ;
* Les restrictions peuvent être de nature fonctionnelle ou non-fonctionnelle.
* Les problèmes confinés sont généralement plus difficiles à résoudre que sans restrictions.

2. Globale/Locale :
* Globale consiste à trouver la solution optimale globale à un problème d'optimisation (donc de toutes les solutions possibles, on prend vraiment la meilleure meilleure), ou de constater qu'une telle solution n'existe pas.
* Locale consiste à trouver la solution optimale locale (donc d'un certain espace arbitraire de solutions).
* Selon certains cas (les classes de problèmes d'optimisation), globale et locale peuvent revenir exactement aux mêmes.
* Cependant, souvent, les approches méthodologiques pour trouver des optimas globaux ou locaux sont de nature fondamentalement différente.

3. Différentiable/Non-différentiable :
* Les modèles d'optimisation différentiable supposent généralement qu'il existe une spécification fonctionnelle : les fonctions utilisées étant **au moins deux fois** continûment différentiables.
* Sinon, on parle de modèle non-différentiables.
* (La plupart des méthodes d'optimisation pour les modèles non linéaires et différentiables sont basées d'une manière ou d'une autre sur une approximation de la fonction par la série de Taylor.)

4. Discrète/Continue :
* Très souvent l'optimisation discrète considère des modèles dont les variables de décision doivent être entières.
* On considère l'optimisation continue si aucune variable de décision n'est limitée à des valeurs discrètes.
* L'optimisation discrète est très important car un grand nombre de problèmes de l'économie et de l'industrie peuvent être formulés et résolus sous forme de problèmes d'optimisation **discrète**.
* Les approches méthodologiques entre optimisation discrète et optimisation continue sont si différentes que les deux catégories constituent deux domaines de recherche **plus ou moins autonomes** en recherche opérationnelle.

5. Convexe/Non-convexe :
* L'optimisation convexe est basée sur la minimisation ou maximisation d'une fonction objectif convexe ou concave.
* Joue un rôle prépondérant dans la théorie de l'optimisation, car la recherche d'un optimum globale se réduit à la recherche d'un optimum local.

6. Linéaire/Non-linéaire :
* Se situe à l'origine de la recherche opérationnelle.
* L'optimisation linéaire (ou programmation linéaire) se focalise sur l'optimisation d'une fonction cible linéaire, **en tenant compte** d'un certain nombre de contraintes linéaires (inégalités ou équations).
* Les modèles de programmation linéaire où les variables de décision sont limitées à des **valeurs entières** (donc discrètes), sont d'une importance **capitale** dans la pratique.

### 1.7. Types de méthodes d'optimisation

1. Exacte/Heuristique :
* Méthodes exactes fournissent : Soit une solution optimale, soit la démonstration qu'une solution optimale n'existe pas.
* Méthodes heuristiques tentent de trouver la meilleure solution possible **sans garantir son optimalité**. Genre comme on avait déjà fait avec le Taquin et le voyageur du commerce avec Ghorbeille.
* En principe, toute méthode fournissant une solution quelconque à un problème d'optimisation **est** une heuristique (peu importe de bonne ou de mauvaise qualité tho).
* Les heuristiques sont typiquement utilisées pour des problèmes où il n'existe pas de méthodes exactes ou que celles-ci ne sont pas applicables, par exemple dans un temps de calcul **raisonnable**.

2. Générale/Spécifique :
* Générale peuvent être appliqués à une grande classe de problèmes d'optimisation.
* Spécifique, bah c'est spécifique à un type de problème très limité et souvent développé au cas par cas.

3. Types d'heuristiques :
* Constructive : Construivent une solution étape-par-étape en commençant par une solution "vide". Puis on ajoute à chaque étape un élément de la solution (ex: la valeur d'une variable de décision) à la solution **partielle** existante, jusqu'à ce que celle-ci forme une solution complète.
* Heuristique d'amélioration : Partent d'une solution admissible et tentent d'améliorer progressivement cette solution par de petites modifications. Également appelées méthodes de recherche locale et globale et sont regroupées sous le terme générique de "méta-heuristiques".
* Méta-heuristique : Jouent également un rôle important dans la recherche d'optimums globaux (ou optimums approchés) en optimisation non-convexe.

## 2. Semaine 2

### 2.1. Exemple avec résolution graphique


> * Chacune des droites (grasses) représente une des contraintes qui ont été posées au préalable.
> * Le polyèdre rouge représente l'ensemble des **solutions admissibles** du système (qui respectent les contraintes pré établies).
> * Dans ce polyèdre, il faut maintenant trouver la meilleur solution :
> 1. On tire les droites de la fonction objectif (thins) et on essait de maximiser la solution obtenue.
> 2. On voit bien que c'est au point vert que l'on va trouver la plus grande valeur : puisque c'est le point en lequel les valeurs x et **sont les plus grandes**.
> 3. Suivant les cas, il peut y'en avoir plusieurs (dans le cas d'une ligne par exemple).

### 2.2. Algorithme du simplexe (linéaire)

*L'algorithme simple souhaite énumérer **l'intégralité** des sommets du polyèdre. Cela n'est pas nécessaire et prend un temps affreux à réaliser. L'algorithme du simplex est aussi basé sur les sommets, mais on va très rapidement pouvoir "convergé" car on ne s'intéresse pas (énumère pas) les sommets dont on n'a pas besoin.*

> * En partant d'un sommet du polyèdre (avec critère pour choisir lequel), on visite son sommet voisin qui est le plus **"haut"**. On continue progressivement jusqu'à atteindre le sommet qui est maximum.
> * Lorsqu'on a atteind le sommet maximum (ici le 5), on le sait, car peu importe le voisin chez qui on va, on va obtenir valeur plus petite (comme pour le 5 ici).

### 2.3. Exemple de résolution simplexe

1. 
> * La fonction objectif à maximiser.
> * Les contraintes à respecter pour la maximisation.

2. 
> * Introduction d'une variable d'écart $e_{i}$ permettant de déployer l'algorithme du simplexe. Permet la mise en place de la **forme augmentée**.

3. Après on applique la résolution qu'il vaut mieux voir en PDF (beaucoup de bonnes explications dessus).
> * Voir également **absolument** l'exercice de résolution avec l'algorithme du simplexe :
> * L'exercide a été fait sur papier d'une "certaine façon".
> * Une correction a également été mise à disposition par l'enseignant dans *"02_PL_exercice.pdf"* et est réalisé un poil différemment.

## 3. Semaine 3

### 3.1. Solution non-bornée


> * $x_{3}$ est la variable de $z$ avec le plus fort accroissement.
> * $x_{3}$ entre donc dans la base.

> * Si on augmente $x_{3}$ cela ne va jamais violer les contraintes : donc c'est **non-bornée** !

> En gros, un peu comme on peut le voir ici : $z$ augmente. Il n'y a donc pas de solution optimale dans un cas non-bornée.

### 3.2. Itération dégénérée

++**Possibilité 1 (temporaire)**++

> ***Voir : OneNote "Itération dégénérée" (aled j'arrive pas tho)***.

En gros c'est un cas dans lequel on va tomber plusieurs fois sur la même solution (itération après itération) avant de finalement tomber sur une solution différente qui est la solution optimale.

Véritablement, le seul objectif de son exemple c'était de montrer qu'il est possible de faire du surplace (de "stagner" sur le même sommet) avant de tomber sur la solution optimale.

À savoir : Borne infinie = C'est pas une borne (division par 0).

++**Possibilité 2 (cycle)**++

On peut également se retrouver dans une situation où on stagne indéfiniment.

++Solution 1 :++

La règle de Band est quelque chose qui permet d'éviter de tomber dans des cycles infinis ! En effet, plutôt que de prendre la variable de $z$ la plus grande, on va prendre la valeur de plus petit indice et qui >= 0.

De cette façon, on ne va jamais tomber dans des cycles. **Cependant** choisir les variables de plus petit indice rend l'algorithme et sa résolution beaucoup beaucoup plus longue. Donc il faut choisir intelligemment selon nos besoins.

++Solution 2 :++

Y aussi la méthode des perturbations mais j'ai rien compris, donc nique sa mère.

> ***Voir slide 15 (pdf: prog linéaire partie 2).***

### 3.3. Problème du démarrage pas bien

Dans certain cas, l'algorithme comme on l'a vu jusqu'à présent ne peut pas être démarrer correctement car l'origine ne fait pas partie des solutions admissibles.

Hors, c'est bien depuis l'origine que l'algorithme démarrait, c'est donc un problème.


++**Solution :**++

Il faut donc que l'on construise nous-mêmes une solution admissibles afin de démarrer l'algorithme (comme on le faisait précédemment) depuis cette dernière.

> ***Exemple à partir slide 21.***

1. **1ère étape** : $x_{0}$ va rentrer dans la base et une autre variable en sortir.
2. **Étape générale** : Itérations normales du simplexe (tout simplement).
3. **Terminaison** :
* Si $x_{0}$ n'est pas dans la base et que $w = 0$ => problème résolu !
* Si $x_{0}$ est dans la base et que $w \neq 0$ => problème insoluble !

> ***Résumé de la suite d'étapes slide 28.***

### 3.4. Simplexe à deux phases

1. Donc en gros on applique peut-être d'abord la résolution du problème auxiliaire (donc la résolution du problème pas bien).
2. Ensuite on applique la résolution normale de base avec l'algorithme du simplexe sur le dictionnaire obtenue à l'issue du point 1 (si nécessaire).
3. À l'issue de l'algorithme, plusieurs cas possibles :
* infaisable = polyèdre vide.
* non-borné = polytope ouvert. *(voir image solution non-bornée)*
* résoluble = polyèdre non-vide (et pas ouvert j'imagine).

> ***Voir slide 29.***

### 3.5. Post-Scriptum

* ***Depuis Slide 16*** *(partie 1)* : Exemple du simplexe avec **forme standard** désormais sympatiquement commenté dans les slides bien comme il faut.
* ***Depuis Slide 32*** *(partie 1)* : Exemple du simplexe avec **tableau** désormais sympatiquement commenté dans les slides également.

- ***Slide 4*** *(partie 2)* : Explication de ce qu'est une **solution non-bornée** désormais sympatiquement commenté dans les slides.
- ***Slide 20*** *(partie 2)* : Explication du "petit problème démarrage pas bien" désormais sympatiquement commenté.
- ***Depuis Slide 21*** *(partie 2)* : Explication du comment gérer le "petit problème démarrage pas bien" (problème auxiliaire) désormais sympathiquement commenté.

## 4. Semaine 4

### 4.1. Dualité

La dualité a pour objectif de ré-exprimer un problème de base d'une façon différente. De cette façon, il est possible de pouvoir éventuellement le résoudre plus facilement.

> * Même problème exprimé de 2 façons différentes (primal et dual).
> * On peut résoudre l'un ou l'autre, et on arrivera à la même solution optimale.
> * Néanmoins, il est possible qu'il soit plus facile de résoudre l'un ou l'autre, à donc faire de façon intelligente.

> **Pour le déploiement même de cette logique, voir exemple depuis Slide 30 (partie 3).**

### 4.2. PL / PLNE


++**Pogrammation Linéaire**++

* Ce sont les exercices que l'on a réalisé jusqu'a maintenant. On applique l'algorithme du simplexe, on résout des problèmes afin d'obtenir la meilleure solution optimale admissible.
* On ne se pose pas plus de questions sur la nature de la réponse obtenue : La solution (ou plutôt les indices x1,x2 qui y amène) peut être réelle, donc c'est du pur **lessssgong**.

++**Programmation Linéaire en Nombre Entiers**++

* La différence fondamentale se trouve tout simplement dans le nom. Il est question ici de résoudre un problème afin d'obtenir la meilleure solution optimale admissible **ET** que cette dernière (ou plutôt x1,x2) soit entière.
* On verra durant le cours qu'il y a différente façon de résoudre "en Nombre Entiers". Il est cependant d'ores et déjà possible d'affirmer qu'arrondir les indices x1,x2 n'est **pas la façon de faire**. Il y a des risques de :
* Ne pas obtenir une soution inadmissible;
* Ou de simplement de ne pas obtenir la bonne solution (pas optimale);
* > Voir les Slides **7, 8, 9** (et 10) de *03_PLNE_part1*.

### 4.3. Branch-and-Bound


La logique de la méthode du *Branch-and-Bound* est justement une des façons de résoudre un problème "en Nombre Entiers". Ce dernier est d'une complexité enfantine :

1. On résout le problème à l'aide de l'algorithme du simplexe ou autre (ex: visuellement lol, de tête lmao, ...) **sans égart** au fait que x1,x2 soient des nombres entiers (osef).
2. Si x1,x2 sont des nombres entiers on stop, sinon on continue en posant :
* $x1 \leq \text{borne inférieure}$;
* $x1 \geq \text{borne supérieure}$.
3. En résolvant ces deux cas séparement, on évite les solutions entre les bornes dont, on le sait, aucune n'est entière. Voir sur l'exemple comment on passe du cas **(1)** à **(2) et (5)**.
4. Après résolution de **(2)** c'est au tour de $x_{2}$ d'être séparé en deux résolutions distinctes.

++**Chose importante à noter**++

Il ne faut pas oublier l'objectif finale qui est, comme toujours, d'obtenir la solution optimale. On va donc vouloir maximiser $z$, ce qui nous permet d'établir la règle suivante :

***"Il n'est pas forcément nécessaire de tous développer et de calculer tous les branchements."***

1. En **(7)** on trouvé une solution en Nombre Entiers qui est déjà $z=15$.
2. En **(8)** la solution n'est pas entière est $z=14$.
3. Même si un branchement permettait d'obtenir une solution en Nombre Entiers, cette dernière serait **de toutes façons** $z < 14$ et donc plus petite que la solution de **(7)**. Il est donc totalement inutile de développer le **(8)**.

> Pour répète de l'examen, **voir ABSOLUEMENT** le pdf ***"mse_optim_PLNE_exo_B_B_graph"***, dans lequel se trouve un exemple entier détaillé de la résolution d'un problème par ***Branch-and-Bound***.

> Pour répète de l'examen, il est **PRIMORDIAL** d'être capable de résoudre les étapes du ***Branch-and-Bound*** sans avoir besoin de développer l'intégralité de l'algorithme du simplexe (cela prendrait beaucoup trop de temps). Vraiment important de pouvoir résoudre à la main (comme le dit le pdf d'exemple).

> Pour répète de l'examen, tenter également de piger le passage entre **Slide 12** et **Slide 13**.

## 5. Semaine 5

### 5.1. Méthode du sac à dos

> * ***Voir Slides 12 à 18 : Les slides sont commentées et tout est compréhensible.***
> - ***Voir fichier Excel : Un exemple quasi-entier commenté et très compréhensible.***

### 5.2. Méthodes de coupe

> Bien voir Slides 19 à 22. Le concept en soit est vraiment basique et facile à comprendre. Donc être sûr de le comprendre complétement.

> Par contre, la développer sur un exemple est **vraiment wtf**, donc bien voir le développement du prof Slides 23 à 27 et comprendre comment ça marche. Éventuellement utiliser ça, mais bof : [**Librairie Python : PuLP**](https://coin-or.github.io/pulp/CaseStudies/a_blending_problem.html).

> Après, essayer de faire l'exemple Slide 28 et voir si le prof met des solutions/notes à disposition et bien bien bien ***++BIEN++*** relire.

> Ouais bon lol, bonne chance pour les répètes d'exa, j'espère que ça ira. Je comprends rien et je vais pas envie d'y passer encore des heures. **++!!! GLHF !!!++**

## 6. Semaine 6

### 6.1. Branch-and-Cut

Revoir, absolument rien pigé.

### 6.2. Cut-and-Branch

La même ptdr sa mère la tchoin.

### 6.3. Graphes (généralités, représentations, parcours)

Ok c'est bon.

## 7. Semaine 7

### 7.1. Plus courts chemins (Graphes)

#### 7.1.1. Dijkstra (source unique)

**++Logique de base++**

En gros, pour un sommet donné (ici le sommet 1) dans un graphe, on cherche à connaître chacun des chemins permettant d'accéder à **TOUS** les autres sommets du graphe.

Cela signifie que **pour le sommet donné** on trouve, après déroulement de l'algorithme, un arbre valide "uniquement pour ce dernier".


> * Comme mentionné plus haut, cet arbre n'est pas un **MST**. Il ne réduit pas "globalement" le coût de l'intégralité de l'arbre, mais uniquement le coût pour **un seul sommet donné** pour accéder à tous les autres sommets.

**++Exemple plus poussé++**

La représentation ci-dessus est correcte mais "uniquement visuelle". Dans le cas du développement de l'algorithme, c'est la logique ci-dessous que l'on devrait appliquer.

En gros, on visite progressivement tous les sommets et ne garde à chaque fois que les chemins de plus petit coût. Pour se faire :
1. On visite le sommet donné et on note les sommets qu'on peut atteindre, leur coût et leur prédécesseur;
2. Ensuite on visite le sommet dont le chemin est le plus court (ici ***d***), on regarde les sommets qu'on peut atteindre et on met à jour la table selon les critères suivants :
* Si le sommet ne figure pas encore dans la table, on l'ajoute simplement (comme le ***e***) ;
* Si le sommet figure déjà dans la table et que le chemin est **plus court** que celui enregistré, on le remplace (comme le ***b***) ;
* Sinon, si le sommet figure déjà mais que le chemin est **plus long** que celui enregistré, on ne fait rien.
3. On réalise l'étape 2 sur le prochain sommet qui est le plus court (ici ***e***).
4. On fait ceci autant de fois qu'on a de sommets, et on fini par obtenir l'arbre des chemins les plus courts pour le sommet donné.


> * Bien faire attention de développer l'algorithme dans l'ordre du "prochain sommet qui a le chemin le plus court" dans la table.

> * Pour réconstituer l'arbre (qui n'est **pas** un MST), on va le faire progressivement **GRÂCE AUX PRÉCÉDENCES** qui ont été enregistrées dans la table. Exemples :
> 1. Pour accéder à S_d, on doit aller à S_d pour un coût de 5 (simple).
> ***"S_a -> S_d"***
> 2. Pour accéder à S_c, on doit d'abord aller à S_b (précédence).
> ***"S_a -> ... -> S_b -> S_c"***
> Pour accéder à S_b, on doit d'abord aller à S_d (précédence).
> ***"S_a -> S_d -> S_b -> S_c"***
> Ca y'est, on a atteind le sommet S_c pour un coût total de 7.

#### 7.1.2. Floyd-Warshall (pour toute paire de sommets)

En gros, l'objectif est ici de pouvoir obtenir un arbre tel qu'avec Dijkstra ++**mais**++ pour TOUS les graphes du graphe. Cela reviendrait donc à réaliser l'algoritme de Dijkstra autant de fois qu'il y a de sommet dans le graphe !
Mais l'algorithme de Dijkstra n'est pas en mesure de gérer des poids négatifs sur les arrêtes. C'est pourquoi il y a Floyd Warshall (enfin je crois).

**++Table des coûts++**

**À gauche** se trouve le graphe avec 5 sommets et les relations qui les relient.

**À droite** se trouve le tableau initial représentant **tel quel** toutes les relations que chacun des sommets possède avec les autres sommets. Le tableau se lit : ligne -> colonne. Exemple :
* Le sommet S_1 accéde à S_2 pour *2*, S_3 pour *4*, ne peut *pas* accéder à S_4 et accède à S_5 pour *3*.
* ... .

<img src="https://hackmd.io/_uploads/SyHTeqpm9.png" width="50%">
<img src="https://hackmd.io/_uploads/ByDjJcaX5.png" width="50%">

\
**Ci-dessous** se trouve le résultat de la première itération à partir du tableau initial : Pour toutes les relations représentées dans le tableau, on s'est posé la question ***"Est-ce si on passe d'abord par le sommet 1, le coût d'accès est moins cher ?"***. Si c'est le cas, on remplace par le nouveau coût moins cher qui a été trouvé. Exemples :

* **(Regarder ligne 2)** Initialement, le sommet S_2 va au sommet S_3 pour un coût de 8 ! Or :
* Il peut d'abord se rendre au sommet S_1 pour un coût de 2;
* Puis depuis le sommet S_1, se rendre au sommet S_3 pour un coût de 4;
* Ainsi le coût total est de 2 + 4 = 6 < que le coût de 8 initiale : On met ainsi à jour la table avec le nouveau "meilleur" coût !

- **(Regarder ligne 4)** Initialement, le sommet S_4 ne peut même pas atteindre le sommet S_2 car il n'a pas de chemin direct lui permettant de s'y rendre ! Or :
* Il peut d'abord se rendre au sommet S_1 pour un coût de 1;
* Puis depuis le sommet S_1 se rendre au sommet S_2 pour un coût de 2;
* Ainsi le coût total est de 1 + 2 = 3 < que l'$\infty$ initial : On met ainsi à jour la table avec le nouveau "meilleur" coût !

<img src="https://hackmd.io/_uploads/H1pJl9pQ9.png" width="60%">

> **PUIS** on va progressivement continuer de dérouler l'algorithme en se posant la même question que précédemment, **MAIS** pour les sommets suivant !

> Cela signifie que l'on aura **AUTANT** d'étapes que l'on a de sommets dans le graphe.

> ***Voir Slides 66 à 67 du pdf "04_graphs_part1" pour le reste du déroulement (c'est simple, vraiment).***

**++Table des précédences++**

En l'état actuel, après avoir déroulé l'algorithme, nous n'avons connaissance uniquement que de "quel est le **meilleur coût** possible pour le sommet X pour pouvoir atteindre le sommet Y". Cela signifie que nous ne sommes **pas** en mesure de recréer le chemin qui correspond **justement** à ce meilleur coup. C'est un problème !

C'est pour cette raison que l'on doit tenir, en parallèle de la table des coûts, une table des précédences. Il est important de la tenir correctement à jour, où le chemin est "perdu".

**Ci-dessous** se trouve la table des coûts initiales ainsi que la table des précédences initiale qui lui est associée. On voit que, très logiquement, les précédences pour un sommet S_x sont soit :
* S_x lui-même (car il peut accéder directement aux autres),
* "vide" car il ne peut y accéder;
* "vide" car c'est lui-même.
\
<img src="https://hackmd.io/_uploads/SyHTeqpm9.png" width="40%">

\
**Ci-dessous** se trouve le résultat après la première itération de la table des précédences. On voit, par exemple, que :

* Lorsqu'on a décidé de faire passer le sommet S_2 par S_1 afin d'aller jusqu'à S_3, on a mis à jour la table des dépendances en fonction :
* Puisque pour aller à S_3, le sommet S_2 doit désormais passé par S_1, l'accès ne se fait plus "en direct" : donc le prédécesseur pour l'accès à S_3 n'est plus S_2, mais S_1 !
- Lorsqu'on a décidé de faire passer le sommet S_4 par S_1 afin d'aller jusqu'à S_2, on a mis à jour la table des dépendences en fonction :
* Puisque pour aller à S_2, le sommet S_4 doit désormais passé par S_1, l'accès ne se fait plus "en direct" : donc le prédeccesseur pour l'accès à S_2 n'est plus S_4, mais S_1 !


**++Fin de l'algorithme++**

**Ci-dessous** se trouvent les tables finales de coûts et de précédences ainsi que le graphe correspondant à cet exemple, afin de pouvoir suivre plus facilement les explications qui suivent.

<img src="https://hackmd.io/_uploads/SyHTeqpm9.png" width="40%">

Il est important de bien comprendre que, dans la table des précédences, on conserve le sommet qui est JUSTE avant le sommet à atteindre. Ainsi, pour retrouver le chemin à suivre pour atteindre un sommet, on doit reconstruire progressivement le chemin en arrière :

* Exemple de S_5 à S_1 (à partir de P(5) et D(5)) :

* Pour aller de S_5 à S_2, il faut passer par S_1 pour un coût total de 4.
"***S_5 -> ? -> S_1 -> S_2***"
* Pour aller de S_5 à S_1, il faut passer par S_4 pour un coût de 2.
"***S_5 -> ? -> S_4 -> S_1 -> S_2***"
* Pour aller de S_5 à S_4, le sommet est directement accessible pour un coût de 1.
"***S_5 -> S_4 -> S_1 -> S_2***" <= coût total : 4.

> Donc en fait, la reconstruction est exactement similaire à celle à réaliser avec Dijkstra.

> ***Voir Slides 70 à 72 + ++EXTRA++ du pdf "04_graphs_part1" pour l'intégralité du déroulement (c'est simple, vraiment).***

## 8. Semaine 8

> ***PDF : "mse_optimiz_graphs_flots_slides".***

### 8.1. Arbres couvrants (Graphes)

Franchement ok. Au pire revoir le pdf en cas de problème durant les répètes.

### 8.2. Flot maximal (Graphes)

#### 8.2.1. Généralités / Ford-Fulkerson

> **Généralités** : Pour examen, juste revoir jusqu'à Slide 15. **Facilement compréhensible**.

> **Ford-Fulkerson** : Pour examen, juste revoir Slide 16 à Slide 31. **Tout est commenté** et **facilement compréhensible**.

#### 8.2.2. Coupes (Edmonds-Karp) / Problème du couplage

> **Pour examen** : À partir de la Slide 32, j'ai de la peine à comprendre de quoi ça parle et où son cours veut vraiment en venir. En gros ça parle de : généralités sur les coupes dans le cas des flots, des coupes pour améliorer Ford-Fulkerson (qui devient alors Edmonds-Karp) et du problème de coupage.

> * J'ai l'impression que c'est juste des infos générales sur la façon dont les coupes intéragissent/fonctionnent sur un graphes de flots.
> * Ensuite y a l'information que grâce aux coupes on peut arrêter l'algorithme de Ford-Fulkerson un peu plus tôt (et améliorer donc la complexité). Et en gros, cette amélioration est connue sous le nom de Edmonds-Karp.
> * Et aussi le problème du couplage est un "concept" très spécifique qui ne semble en théorie pas si compliquée. Par contre, je n'ai vraiment pas l'impression que son exemple soit super pertinent et adapté à ce "concept".

## 9. Semaine 9

### 9.1. La méthode de dichotomie

**++Fonctionnement++**

C'est une méthode permettant de trouver une racine d'une fonction donnée $f$, dans un intervalle (ensemble de solution) défini. Cette méthode consiste en la division successive de l'intervalle jusqu'à converger sur une solution. Le milieu est défini par : $m=(a+b)/2$ :

* Si on trouve une racine d'une fonction dérivée $f^{'}$, il est *possible* que cette racine correponde à un minimum dans la fonction $f$.
* En effet, pour avoir un minimum de $f$ il faut que, en ce point, la dérivée gauche soit négative et la dérivé droite soit positive (et inversément pour un maximum).

**++Vitesse++**

À chaque itération l'erreur est divisée par 2. L'erreur absolue est au plus bas $(b-a)/2^{n}$. La vitesse de convergence est donc linéaire.

### 9.2. La méthode de Newton (à 1 itération)


> * Le racine $r$ que nous devons trouver.
> * La fonction (eu bleue) est notée $f(x)$.
> * La pente de la tangeante $L$ (en rose) est, par définition, équivalente à $f^{'}(x_{1})$.

++**Première itération**++

L'idée de base est que la tangeante $L$ est proche de la courbe et que son ordonnée à l'origine $x_{2}$ est **proche** de l'*ordonnée à l'origine* de la courbe, **c'est-à-dire la racine $r$** : Et puisque la tangeante $L$ est une droite, on peut facilement trouvé son ordonnée à l'origine à elle.

* On cherche et trouve alors une formule pour $x_{2}$ en fonction de $x_{1}$, en utilisant le fait que la "pente de la tangeante $L$" = $f^{'}(x_{1})$. L'équation est alors (corrigé par le prof durant le cours) :

$$
L(x) - f(x_{1}) = f^{'}(x_{1})(x-x_{1})
$$

* Donc plus spécifiquement pour $x=x_{2}$, et sachant que $L(x_{2})$ se trouve en 0, on obtient :

$$
0 - f(x_{1}) = f^{'}(x_{1})(x_{2}-x_{1})
$$

* Il est alors possible de résoudre cette équation pour $x_{2}$ :

$$
x_{2} = x_{1} - \frac{f(x_{1})}{f^{'}(x_{1})}
$$

* On peut donc utiliser $x_{2}$ comme nouvelle approximation de la racine $r$.

++**Suite**++


* On répète ensuite cette procédure avec $x_{2}$ à la place de $x_{1}$, ainsi qu'avec la nouvelle ligne tangeante $L$ en $(x_{2}, f(x_{2}))$. On trouve ainsi la troisième nouvelle approximation par :

$$
x_{3} = x_{2} - \frac{f(x_{2})}{f^{'}(x_{2})}
$$

* Enfin, on continue d'itérer aussi longtemps qu'on le souhaite (selon la précision que l'on souhaite obtenir).

**++Variante (la méthode la Sécante)++**

La méthode de Newton nécessite de calculer la dérivée de la fonction $f$. Cette dernière peut-être difficile à calculer. Ex: $f^{'}(x) = ?$ sachant que $f(x)=x^{2}*3^{x}*cos(2x)$.

On va alors modifier la méthode de Newton de façon à ce que la dérivée n'apparaisse plus :

$$
f^{'}(x_{n})\approx=\frac{f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}
$$

**++Défaillance de la méthode++**

La méthode de Newton implique une division par $f^{'}(x_{n})$. Cela signifie que la méthode échouera si la dérivée est nulle pour tout $x_{n}$ de la séquence. On peut généralement, néanmoins, résoudre ce problème en choisissant une autre valeur de $x_{1}$.

### 9.3. La méthode du Gradient

<img src="https://hackmd.io/_uploads/rJ0mtAvBc.png" width="85%">

<img src="https://hackmd.io/_uploads/Hk44FCPHc.png" width="55%">

<img src="https://hackmd.io/_uploads/B1wHKCDS5.png" width="85%">

## 10. Semaine 10

### 10.1. La méthode de Newton (à n dimensions)

Il y a une consistence entre l'équation de la méthode à 1 dimension, et l'équation de la méthode à n dimensions. Cette méthode consiste véritablement à appliquer la même méthode, mais sur plusieurs dimensions.
> Pas compris plus, mais en gros les premières slides ont vraiment pour but de faire le rapprochement entre les deux méthodes de Newton.

Mais en gros, la méthode de Newton à n dimensions, dans sa version définitive devient :

<img src="https://hackmd.io/_uploads/BJf1peZUq.png" width="55%">

**++Exemple vite-ef++**

<img src="https://hackmd.io/_uploads/B1lscxZ8c.png" width="80%">

> Juste le départ de l'exemple réalisé. Ce dernier peut être trouver à partir de la Slide 46 dans le PDF ***"09-OptNonLin_a.pdf"***.


> On remarque sur l'image de droite que, comme indiquer sur la méthode définitive ci-dessus, le $H$ change à chaque itération. Ici son calcul a été montré pour la l'itération $0$, mais après il n'est plus montré. Donc vraiment, ça prend sa mère beaucoup de temps à résoudre cette algorithme.

**++Conclusion++**

<img src="https://hackmd.io/_uploads/r1yLteb8q.png" width="85%">

### 10.2. Apprentissage supervisé

* Principe
* Fonction d'activation
* Perceptron
* Séparabilité/Non-séparabilité linéaire
* Théorème du Perceptron
* Algorithme d'apprentissage du Perceptron
* Erreur quadratique
* Convergence
* Réseau multi-couches
* Fonction sigmoïde
* Descente de gradient

Autant de termes, mots et concepts que je ne comprends et ne métrise pas !
GL HF pour les examens ! ^^

## 11. Semaine 11

### 11.1. Recuit simulé

#### 11.1.1. Origine

Les premières slides sont là pour poser l'histoire du recuit simulé : en gros cette technique est basé sur la façon d'atteindre l'état solide ***cristallin*** ou l'état solide ***amorphe*** d'un métal, respectivement l'équivalent du ***minimum global*** et d'un ***minimum local*** dans un problème d'optimization. Puis, s'en suit une suite d'anologies entre le système physique (métal) et le problème d'optimisation.

#### 11.1.2. Algorithme

**++Logique de base++**

<img src="https://hackmd.io/_uploads/BkD7SVcLq.png" width="85%">

**++Organigramme++**

<img src="https://hackmd.io/_uploads/ry-jSNcU5.png" width="88%">/

**++Pseudo-code (version Metropolis)++**

<img src="https://hackmd.io/_uploads/HJ3eU49Lc.png" width="85%">/

**++Probabilité d’acceptation des sauts positifs++**


> Donc en gros :
>
> * La température fait varier l'énergie !
> * La probabilité d'acceptation dépend de l'énergie !
> * Puisqu'on a une Exponentielle, plus la variation d'énergie va vers 0, plus la probabilité va vers 1 !
>
> - Et nous, dans l'algorithme, ce qu'on veut faire varier progressivement, c'est justement la température. C'est notre "argument" dans cet algorithme.

**++Conclusion++**

<img src="https://hackmd.io/_uploads/ryTLKVc8q.png" width="85%">

### 11.2. L'affectation quadratique

> ***Voir Slides 20 à 27 du PDF "11_recuitSimEtRT" pour plus d'explications.
> Très compréhensibles + commentées.***

**++Logique de base++**

En gros le but c'est typiquement de pouvoir *optimizer* les **emplacements** (physique) de plusieurs **objets** en fonction de "combien" chacun d'entre-eux a **besoin** d'être proches des autres objets (typiquement pour communiquer). Forcément on va vouloir :

* Placer les objets qui doivent communiquer beaucoup ensemble a des emplacements qui sont proches l'un l'autre (et ainsi optimizer la vitesse des communications du système);
* Ne pas tenir compte de l'emplacement d'un objet en fonction d'autres objets avec lesquels ils ne communiquent pas ou quasi pas.

**++Exemple de cas d'utilisation++**

<img src="https://hackmd.io/_uploads/rJgGpNqI9.png" width="85%">

### 11.3. Recherche avec Tabou

> * ***Voir Slide 28 à 47 du PDF "11_recuitSimEtRT".***
> - ***C'est pas commenté du tout, mais c'est honnêtement pas difficile et relativement compréhensible.***
> * ***Pour les répèts ça devrait le faire, tkt ça va bien sepasser.***

## 12. Semaine 12

> * ***Voir le PDF "12-satContraintes" :***
> * ***Les choses vraiment importantes sont commentées et vraiment compréhensibles.***
> * ***Ce qui n'est pas commenté est vraiment compréhensible (et pas le plus important).***

## 13. Semaine 13

> * ***Franchement, les algos génétiques on connaît maintenant.***
> * ***Voir le rapport qu'avait été écrit pour le projet d'algo génétique avec les labyrinthes durant le cours de Bachelor (voir regarder le cours de Ghorbel si vraiment besoin).***

> * ***Mais je pense que de manière générale, vraiment ça va.***

## 14. Semaine 14

> * ***Juste l'algo des fourmis. En tout cas de "théorie"/"logique" et d'un point de vue biologique on connaît tout ça.***
> * ***Je dirais juste de s'informer sur cet algo d'un point de vue de l'implémentation.***

> * ***Juste regarder le cours du prof bien comme il faut, et sûrement bien regarder aussi d'autres sources d'informations.***

# Par profs

* Les exemples et les exercices du cours sont représentatifs des questions d'examens.

## Chapitre: Programmation linéaire

* Expression d'un problème sous forme de problème de programmation linéaire (aussi en nombres entiers) : :heavy_check_mark: **!**
* Résolution graphique : :wavy_dash: **!**
* Algorithme du simplexe avec la méthode
* des dictionnaires (méthode par substitution) : :wavy_dash: **!**
* des tableaux : :heavy_check_mark: **!**
* Simplexe à 2 phases avec résolution du problème auxiliaire : :wavy_dash: **!**
* Conversion d'un problème primal en dual et correspondances : :wavy_dash: **!**

## Chapitre: Programmation linéaire en nombres entiers

* Résolution graphique : :wavy_dash: **!**
* Algorithme du Branch-and-Bound : :heavy_check_mark: **!**
* Résolution du problème du sac à dos : :x: (mais facile) **!**
* Méthode des coupes : :x: (et dur af) **!**

## Chapitre: Graphes et réseaux

* Structures de données pour représenter un graphe : :x: (ez, mais revoir) **!**
* Algorithmes (avec les structures de données nécessaires) : :x: (ez, mais revoir) **!**
* Parcours en largeur et en profondeur.
* Dijkstra et Floyd de plus courts chemins.
* Prim et Kruskal d'arbre couvrant minimal.
* Algorithme de Ford-Fulkerson : :heavy_check_mark: **!**
* Critères de maximalité d'un flot : :question:**!**
* Conversion d'un problème de couplage en un problème de flot : :question:**!**

## Chapitre : Optimisation non linéaire

* Optimisation locale/globale convexité : :x: **!**
* Méthode de dichotomie, méthode de Newton, méthode du gradient : :heavy_check_mark: **!**
* La fonction de coût du Perceptron et la méthode du gradient pour l'apprentissage : :x: **!**

## Chapitre : Recuit simulé et recherche tabou

* L'algorithme du recuit simulé, l'algorithme de recherche tabou : :wavy_dash: **!**
* Problème de l'affectation quadratique et son codage : :question:**!**

## Chapitre : Problèmes à satisfaction de contraintes : :x: **!**

* Codage de problèmes (n-reines, coloration de cartes), graphe de contraintes.
* Résolution de problèmes par un algorithme de backtracking et forward checking.
* Heuristiques pour la sélection de variables et la sélection de valeurs .

## Chapitre : Algorithmes génétiques : :x: **!**

* Représentation des problèmes.
* Eléments de base : sélection, opérateurs d'évolution et remplacement.
* La programmation génétique.

## Chapitre : Algorithmes de fourmis : :x: **!**

* Description générale de la méthode.
* Régle de déplacement des fourmis pour le problème du voyageur de commerce.

# Répète perso

* Les exemples et les exercices du cours sont représentatifs des questions d'examens.

## Chapitre: Programmation linéaire

* Expression d'un problème sous forme de problème de programmation linéaire (aussi en nombres entiers) : :heavy_check_mark: **!**
* Résolution graphique : :heavy_check_mark: **!**
* Algorithme du simplexe avec la méthode
* des dictionnaires (méthode par substitution) : :heavy_check_mark: **!**
* des tableaux : :heavy_check_mark: **!**
* Simplexe à 2 phases avec résolution du problème auxiliaire : :heavy_check_mark: **!**
* Conversion d'un problème primal en dual et correspondances : :heavy_check_mark: **!**

## Chapitre: Programmation linéaire en nombres entiers

* Résolution graphique : :heavy_check_mark: **!**
* Algorithme du Branch-and-Bound : :heavy_check_mark: **!**
* Résolution du problème du sac à dos : :heavy_check_mark: (mais facile) **!**
* Méthode des coupes : :x: (et dur af) **!**

## Chapitre: Graphes et réseaux

* Structures de données pour représenter un graphe : :heavy_check_mark: (ez, mais revoir) **!**
* Algorithmes (avec les structures de données nécessaires) : :heavy_check_mark: (ez, mais revoir) **!**
* Parcours en largeur et en profondeur.
* Dijkstra et Floyd de plus courts chemins.
* Prim et Kruskal d'arbre couvrant minimal.
* Algorithme de Ford-Fulkerson : :heavy_check_mark: **!**
* Critères de maximalité d'un flot : :heavy_check_mark: **!**
* Conversion d'un problème de couplage en un problème de flot : :heavy_check_mark: **!**

## Chapitre : Optimisation non linéaire

* Optimisation locale/globale convexité : :heavy_check_mark: **!**
* Méthode de dichotomie, méthode de Newton, méthode du gradient : :heavy_check_mark: **!**
* La fonction de coût du Perceptron et la méthode du gradient pour l'apprentissage : :heavy_check_mark: **!**

## Chapitre : Recuit simulé et recherche tabou

* L'algorithme du recuit simulé, l'algorithme de recherche tabou : :heavy_check_mark: **!**
* Problème de l'affectation quadratique et son codage : :heavy_check_mark: **!**

## Chapitre : Problèmes à satisfaction de contraintes : :x: **!**

* Codage de problèmes (n-reines, coloration de cartes), graphe de contraintes.
* Résolution de problèmes par un algorithme de backtracking et forward checking.
* Heuristiques pour la sélection de variables et la sélection de valeurs .

## Chapitre : Algorithmes génétiques : :heavy_check_mark: **!**

* Représentation des problèmes.
* Eléments de base : sélection, opérateurs d'évolution et remplacement.
* La programmation génétique.

## Chapitre : Algorithmes de fourmis : :heavy_check_mark: **!**

* Description générale de la méthode.
* Régle de déplacement des fourmis pour le problème du voyageur de commerce.