# Recherche opérationelle

## Cours 12/11

### Introduction

Le prof: doctorant en recherche opé dans une boite de conseil.
Objectif: Introduction à la recherche opé, recherche "transversale"

Le but est de faire de l'aide de décision.
Résoudre des pb de taille très grandes, sans algo impossible d'avoir des sols
de qualité.

Ex google map - partir d'un point A à B - Quel est le meilleur chemin en
minimisant la dist totale parcourue.

Résoudre des problèmes à l'aide de données.
En lien avec l'économie, créer des modèles, minimiser des coûts

Un pb de recherche opé ?
* Données
* Variables

Résoudre un pb de recherche opé
* Opti une fonction objectif (minimiser ou maximiser les variables)
* Respecter un ensemble de contrainte

Ex sac à dos, on veut mettre un max d'objet dedans.
Chaque objet a un poids et une utilité. Contrainte la somme des poids soient inférieur ou égale à la capacité max du sac.

Deux options :
- Résolution exacte, explorations exhaustives (CPLEX, Gurobi, FICO, XPRESS, Artelys Knitro)
- Résolution approchée, utilisation d'heuristiques

L'approche Résolution exacte devient très vite très couteuse avec un grand nombre d'objets
Solver d'optimisation, souvent utilisé en entreprise

Domaines d'application:
Pb de grande taille, réduire cout, distance à parc, opti etc

* Gestion de production: edf quelle quantité d'elec prod pour satisfaire la clientèle?
* Industrie manufacturière ? Cout de production totale, pièce détachées à produire
* Affectation de ressources: VTC quel chauffeur et quel client, trajet d'avions
* Transport de l'énergie: Créer les réseaux electrique, ou mettre les bornes réseaux pour avoir un max de couverture

### La Recherche Opérationnelle chez DecisionBrain

Conseil en optimisation (métier visé ingénieur optimisation)
L'ingénieur optimisation va utiliser des outils (solveurs) sur des problèmes qu'il a lui même modélisé soit pour son entreprise soit pour un besoin client. Il présentera sa solution optimisée qui sera appliquée ou non.

2 dimensions d'optimisation:

* Manufacturing
- Pour les planning de production
- Minimiser les coûts de production, les coûts fixes ou les coûts de stockage
- Respect des demandes

:::info
++Exemple++: Le lot-sizing (100 unités mensuelle)

S1 : 600 unités produits en Janvier et Juillet
S2 : 100 unités produits par mois

Le but ici est de trouver quelles demandes de lot de t-shirt sont les plus rentables pour l'entreprise.
- Faut il privilégier la commande de 600 unités x2 ou celle de 100 unités par mois ?
- Est ce que l'usine est capable de produire les 600 pièces pour Janvier?

Toutes ces questions rentre en compte lorsque qu'on pense optimisation d'où la complexité.
:::

* Work force

L'affection de tâches à des personnes ou des ressources

:::info
++Exemple++: Avec deux individus qui peuvent exécuter des taches communes et des taches spécifiques à chacun. La question était "A qui attribuer les taches communes ?" en fonction de la distance de ces taches avec les taches spécifiques des deux individus
:::

## Cours 16/11

Problème du voyageur du commerce

### Introduction à la théorie des graphes

Rappel sur ce qu'est un graphe :

* Graphe : ensemble de points reliés entre eux par des segments

* Degré d'un sommet : nb d'arêtes rattachées à un sommet

* Chaine : suite finie d'arêtes consécutives

* Chaine simple : si toutes les arêtes sont distinctes, pas de boucles

* Cycle : chaine simple dont les 2 extrémités sont identiques

* Cycle hamiltonien : si le cycle visite tous les sommets du graphe

### Théorie des graphes + TSP (problème du voyageur du commerce)

* Modélisation du problème par un graphe

- Solution optimale du TSP : cycle hamiltonien.
- Chaine fermée : le véhicule doit nécessairement passer par tous les sommets + revenr au point de dépôt.

Modélisation mathématique du problème

* Contraintes :
- Tout sommet doit être visité une et une seule fois
- Le chemin ne doit être constitué que d'un seul cycle de longueur N

### Heuristique (?)

* A partir d'une solution initiale (via heuristique simple) on modifie la solution obtenue pour améliorer **la fonction objective**.
* On définit des **opérations de voisinage**

### Notion de minimum local/global

* Minimum global : meilleur solution du problème
* Minimum local : solution ne pouvant plus être améliorée à partir de l'opération de voisinage choisie.

EX sur Sac à Dos avec comme voisinage : on remplace un objet du sac par un objet qui n'est pas dans le sac.

Exemple de voisinage sur le TSP
* Echange de sommets
- Echange de position entre 2 sommets

* Méthode 2-opt
- Echange sur les arêtes au lieu des sommets.
- Suppression de 2 des arêtes + reconnecter les tours
- On conserve le changement si la longueur du chemin diminue
- Si graphe orienté, faire attention que l'orientation de toutes les arêtes entre le point j et i + 1 changent de sens. En gros on change les arêtes + l'ordre des points est modifié

## Problème du TSP avec un seul véhicule + la capacité

Pas possible de livrer tous les points de livraisons : véhicule a une capacité + chaque point de livraison a un poids et une utilité.

* Optimisation muli-critère
- Optimisation sur un premier critère puis on optimise sur un deuxième critère.
- Pondération de chacuns des objectifs et évaluation de chaque solution en tenant compte en simultanée des deux critères.

## Cours 19/11

### Rappels sur les problèmes d'optimisation
**Un problème de Recherche Opérationnel est constitué de:**
* Un ensemble de données connues en avance
* Un ensemble de variables dont il faut determiner les valeurs optimales

**Résoudre un problème de Recherche Opérationnel c’est:**
* Optimiser une fonction objectif
* Respecter un ensemble de contraintes

**Un problème d’optimisation sur un ensemble de variables X s’écrit sous la forme:**
* min_f(X) -> fonction objectif
* g(X) <= 0 -> 1ère contrainte
* h(X) = 0 -> 2nd contrainte

### Différents types de problèmes d'optimisation
* linéaire -> fonctions affines (ex: Voyageur de commerce)
* quadratique -> fonctions quadratiques
* Autre (exponentielles, non-continues...)

Le temps de résolution en dépend.

Les problèmes industriels sont rarement linéaires, des aproximations sont donc faites afin de les linéariser.

### Différents types de variables à optimiser
* continues -> dans R
* entières -> dans N
* Booléennes -> dans {0;1}

Les problèmes linéaires sont les plus simples (variables continues) et solvables via des algo tels que l'algo du simplex, la méthode des points intérieurs...

S'il y a des variables entières ou booléenne, la taille des instances pouvant être résolue diminue

**Relaxation continue d'une variable:**
* son domaine de définition passe de N à R (mais même bornes)
* pour un problème de minimisation, résoudre le problème où les variables ont été relachées permet d'obtenir une borne inférieur du problème

Par exemple dans le problème du sac à dos, les variables à optimiser sont booléennes dans {0;1}. Si on relâche ces variables, on optimise le même problème pour ces variables prenant des valeurs dans [0;1].

**Cela revient à accepter de mettre seulement des parties d'objet dans le sac.**

:::info
**Il peut être intéressant de combiner relaxation des variables avec des méthodes de reconstruction.**
++Par exemple:++
* Dans le problème du Voyageur de Commerce: Emprunter un arc que si la valeur de la variable relâchée (entre 0 et 1) dépasse un certain seuil
* Dans le problème du Sac à Dos: Mettre les objets dans le sac selon les valeurs des variables relâchées (entre 0 et 1)

++**Propriété:**++ Résoudre le problème relâché du Sac à Dos puis mettre dans le sac tous les objets dont la variable est de 1 revient à affecter les objets par ordre décroissant du ratio **utilité/poids**. Toutes les variables optimisées auront une valeur optimisée égale à **0 ou 1** sauf **au pire 1 objet** avec une valeur fractionnaire.
:::

La fonction **LinProg** de la librairie SciPy permet de résoudre des problèmes **linéaires avec des variables continues**.

### Introduction au projet final: Vehicle routing problem

* Extension du Problème du voyageur de commerce dans le cas où plusieurs véhicules peuvent partir du dépôt:
- Quel est la meilleure affectation des points de livraisons aux véhicules?
- Quel est le meilleur chemin à parcourir pour chaque véhicule?
* Chaque véhicule a une capacité limitée
* Chaque livraison consomme une certaine partie de la capacité du véhicule auquel elle est affectée
* Chaque livraison a une utilité: certaines livraisons sont plus valorisées

**Modalités**
* Lecture/écriture des données
* Modélisation du problème
- mathématiques
- structurelle
* Mise en place de méthode de résolution/démarche expérimentale
* Exploitation des résultats et étude qualitative des résultats obtenus sur un benchmark
- définition d’indicateurs pertinents
- trouver des bornes au problème pour permettre de placer sa solution

## Cours 20/11

### Méthodes de Recherche Locale

* A partir d'une solution initiale, obtenue avec une heuristique simple, l'idée est de modifier localement la solution obtenue pour améliorer la fct objectif
* On définit pour cela des opérations de voisinage

* Notion de minimum local/global
* Minimum global : Meilleure solution au pb (respectant les contraintes)
* Minimum local : Solution ne pouvant plus être améliorée à partir de l'op choisie
- Pour sortir des minimums locaux, on s'autorise des mouvments qui vont dégrader la solution. Dans l'exemple, on dégrade la valeur de 5 au prix d'un meilleur mouvement.

### Recherche Tabou : Principe
A partir du moment ou la dégradation a été faite, pendant un certain nombre d'itérations, on ne s'autorise plus à faire le mouvement inverse pour revenir à l'état initial. L'idée est de conserver une liste 'Tabou' qui contient tous les mouvements interdits. On ne bannit pas le mouvement définitivement : on peut choisir de le bannir pendant un certain nombre d'itérations. Les mouvments sont généralement stockés dans une file (FIFO).
* L'échange se fait entre A et E. Je veux stocker ce mouvement. Je peux le stocker sous forme de couple (A et E) ou alors tous les échanges impliquant A.

Exemple : On considère l'opération de voisinage consistant à
- Echanger un objet du sac contre un objet non contenu dans le sac
- Rajouter dans le sac un obj contenu dans le sac
- Mouvement interdit : Remettre dans le sac un objet qui a été enlevé

### Méthode du recruit simulé : Principe
On affecte à notre solution courante
- une valeur E -> énergie initalement à E0
- une valeur T -> température

Plus on fait d'opérations, plus T descend.

Si les mouvements qu'on fait améliorent la solution, on l'effectue. Si un mouvement la dégrade, on l'effectue quand même (mais avec une probabilité (e^-deltaE/T)).
Si la température commence en étant forte, on s'autorise à effectuer plus d'opérations dégradantes, et plus la dégradation se fait, moins on s'autorise d'opérations dégradantes

**Caractéristiques**
- Methode simple a implementer
- L'algo dépend énormément des paramètres qu'on met
- La loi de décroissance de la température A
- la température T0
- La température finale (ou le nb d'itérations)
- Plus la solution est grande, plus le résultat va être affecté par les paramètres.
- Comment définir le niveau d'energie d'un système ?
- Dans quelles mesures la température va évoluer ?
- Utilisations de probabilités, donc perte de robustesse de la qualité des solutions

Cela dit, il existe de nombreux cas dans lesquels appliquer des méthodes autorisant des dégradations améliore le résultat. (Ex : Cours 4 slide 17)

### Autres heuristiques de résolution

**Algorithme de colonies de fourmis : Principe**
- Un certain nombre de fourmis vont chacune parcourir un chemin différent à chaque itrératiuon
- Chaque fois qu'une fourmi parcourt un arc elle dépose des phéromones dont la quantité dépend de la longueur du chemin

=> Les chemins les plus courts auront plus de phéromones

- A chaque itération une fraction des phéromones s'évapore
- Les fourmis effectuent leurs chemins au hasard, mais auront plus tendance à emprunter un arc avec bcp de phéromones
- A la fin il ne reste que le chemin le plus court

Au bout d'un certain nb d'itérations, on fait décroitre plus vite le nb de phéromones, mais comme plein de fourmis empruntent le même chemin, le taux de phéromones augmente quand même, ce qui laisse apparaitre à la fin des itérations le chemin le plus court.

**Algorithme génétique : Principe**
Ou Systeme de reprodution / mutation

On part d'une population de base et on la fait évoluer, pour que les descendants soient de meilleurs descendants

- On **sélectionne** les élements les plus prometteurs de la liste cycle hamiltonien
- **Reprodution** : On génère de nouveaux cycles en "mélangeant" les éléments de la pop initiale
- **Mutation** : On modifie légèrement certains des cycles
- **Evaluation** : On évalue chacun des nouveaux cycles

=> En effectuant suffisamment de cycles de reprodution/mutation et en ne gardant que les meilleurs éléments, l'idée est de converger vers une très bonne solution.

## Cours 04/12

Pour le livrable : rendre un rapport et le code
Description
en plus de l'envoie du code, un fichier de sortie avec en première ligne le fichier d'instance puis le véhicule et enfin la route

Cours d’ajourd’hui : comment évaluer une solution
Dans le monde industriel , on ne va jamais connaitre la solution optimale à cause de la grandeur des instance.
On ne sait que rarement quelle est la valeur optimale.
Ce qui serait intéressant serait d’utiliser les points dans le rapport

4 points :
- Est-ce qu’il y a une borne inférieure de la solution optimale ?
- De la même manière il faut définir une borne supérieure ? Si on est très au-dessus de la borne, c’est qu’un a une grosse marge de progression.
- Peut –on définir des indicateurs pertinents ? Dans le cas où nous avons plusieurs objectifs. Toujours être capable de transférer le résultat obtenu dans un cadre compréhensible.

**L’obtention d’une borne inférieure**
Si elle est bien évaluer,elle est plutôt proche de la borne optimale. Par définition, c’est quelque chose qui va borner la solution. Donc ce n’est pas normal si on va en-dessous.
La plus utilisée et la plus simple : si l’on dispose d’une modélisation MIP du problème, la valeur optimale du problème relaché correspond à une borne inférieure pouvant être facilement trouvée. Sur le problème du sac à dos, ça a donné des bons résultats.
Une autre solution est d’enlevée des contraintes pour avoir plus de facilité. Si une solution minimise les contraintes on aura une solution inférieure pour le problème général.

Notion d’arbre couvrant :
Arbre : graphe non orienté, acyclique et connexe (passe par tous les points)
Arbre couvrant : arbre contenant tous les sommets d’un graphe
Trouver l’arbre couvrant de plus petite longueur permet d’avoir une borne inférieure de la longueur de la plus petite tournée car son poids est plus petit que celui du chemin hamiltonien de poids minimal.

Algorithme de Kruskal :
Principe : on trie les arrêtes par ordres de longueur croissant et on les ajoute une par une en respectant certaines règles
- On ajoute |V| arrêtes
- L’ajout d’une arrête ne doit pas former un cycle
o Une des manières de s’en assurer consiste à garder à chaque étape l’ensemble des points accessibles depuis chaque sommet (dénommé par clique)

**L’obtention d’une borne supérieure**
Toute solution réalisable d’un problème fournie une borne supérieure. L’obtention d’une solution réalisable est plus simple en général que d’obtenir la solution optimale.
Ce qui est intéressant de définir l’écart relatif entre la borne inférieure et la borne supérieure.
Créer une solution en ajoutant à chaque étape le point le plus proche visité
Créer une solution en ajoutant à chaque étape le point le plus proche non visité et en l’insérant à la meilleur solution possible
Reconstruire une solution à partir de l’arbre couvrant de poids minimal

Avec ces 2 bornes on peut définir des gaps.

**Définir des indicateurs**
KPI : Key Performance Indicator
Très important en pratique, ce sont eux qui permettent d’évaluer la qualité de la solution
- Optimiser sur une fonction objectif ajoute un niveau d’abstraction
- Simplification des données de sorties qui peuvent parfois être complexes
Problème de lot sizing avec capacité et production mensuelle
Les contraintes sont :
- Lancer une production tous les mois peut couter cher
- Produire en avance et stocker pour satisfaire de futures demandes
- Cout d’inventaires qui peuvent être élevés
- Capacité mensuelle limitée
- Lost sales : on ne peut pas tout produire

Exemple d’indicateurs
- Taux moyen de satisfaction de la demande
- Taux d’occupation moyen de la machine
- Durée moyenne entre 2 productions successives pour chaque produit
- Niveau d’inventaire moyen par période pour chaque produit

Apparition d’un front de Pareto
- Il y a une infinité de solutions
- Essayer d’optimiser deux indicateurs devient impossible

**Vehicle Routing Problem + ordonnancement (bonus)**

On attribue à chaque point de livraison un intervalle [tmin ;tmax]
- C’est l’intervalle de temps durant lequel le point de livraison peut être livré
Le problème est que maintenant tous les points de livraison ne peuvent pas être parcourus dans n’importe quel ordre.