Outils d’Aide à la Décisionduhamel/OAD/2014_OAD.pdf · Temps de calcul ... Outils de profilage, de tests (unitaires, ... HAMILTONIEN(G,o,d) : existe-t-il un chemin hamiltonien

Outils d’Aide à la Décision

Christophe Duhamel & Philippe Lacomme

ZZ2 F2/F3 - 2014

Complexité algorithmique

Conception d'algorithmes

Problèmes combinatoires

Problèmes d'ordonnancement

Problèmes de transport

Plan du cours

cours thème TP F2 TP F3 thème

S38 16/09 ordo

S39 23/09 ordo 26/09 22/09 graphe

S40 30/10 ordo 03/10 29/09 graphe

S41 07/10 complexité 10/10 06/10 ordo

S42 14/10 heuristiques 17/10 13/10 ordo

S43 21/10 transport 24/10 20/10 ordo

S44 Toussaint

S45 04/11 transport 07/11 03/11 transport

S46 14/11 10/11 transport

S47 21/11 17/11 transport

Complexité : 1 cours

Ordonnancement : 4 cours, 4 TP

Transport : 4 cours, 4 TP

Planning du cours

1. Complexité algorithmique

Motivations

Définitions

Principales classes de complexité

Calcul de complexité

Concevoir un algorithme, c'est bien

Connaître les limites de l'algorithme, c'est mieux !

Limites

Préconditions

Postconditions

Temps de calcul

Taille mémoire

Communications

1.1 Motivations

Efficacité d'un algorithme

Les performances sont importantes lorsque l'algorithme

constitue un goulot d'étranglement du système

Volumétrie importante (grande taille de données)

Nombre élevé d'appels (algorithme utilisé souvent)

Contraintes sur le temps de réponse

Contextes typiques

Systèmes embarqués, temps-réel

Logiciels de calcul

Fouille de données

1.1 Motivations

1.1 Motivations

Comparaison d'algorithmes

Plusieurs algorithmes pour résoudre le même problème

Lequel est le meilleur ?

Selon quel critère ?

Dans quel contexte ?

Sur quel type de données ?

1.1 Motivations

Analyse a priori

Formulation mathématique pour le critère

+ meilleure compréhension de l'algorithme

- obtention parfois complexe

Analyse a postériori

Outils de profilage, de tests (unitaires, couverture...)

+ utilisation simple

- algorithme = boîte noire, délai d'obtention

Ici, analyse a priori

1.1 Motivations

Trouver des critères d'analyse pertinents

Indépendants de la plateforme, du langage

Discriminants

Permettant une analyse rigoureuse

Possibilité d'analyse multicritères

Dominance

Front de Pareto

Agrégation de critères...

1.1 Motivations

Critères d'analyse

Temps de calcul → nombre d'opérations effectuées

Taille mémoire → quantité de mémoire consommée

Communications → nombre d'octets émis/reçus

Typiquement : temps de calcul

Dans ce cours : complexité temporelle des algorithmes

1.2 Définitions

Analyse du temps de calcul : complexité temps

Nombre d'opérations élémentaires effectuées en fonction des

données du problème

Nécessite de définir

Une opération élémentaire

La taille du problème

1.2 Définitions

Opération élémentaire

Opération caractéristique de l'algorithme étudié

Exemples

Recherche dans un tableau (ZZ1) : accès, comparaison

Tri d'un tableau (ZZ1) : comparaison, déplacement

Produit scalaire : multiplication

Minimisation : évaluation d'un point, calcul du gradient

Calcul du PGCD : division, modulo

Enveloppe convexe : test d'un point

1.2 Définitions

Taille du problème

Grandeur caractéristique utilisée par l'algorithme

Exemples

Recherche dans un tableau (ZZ1) : taille du tableau

Tri d'un tableau (ZZ1) : taille du tableau

Produit scalaire : dimension

Minimisation : -

Calcul du PGCD : taille des nombres

Enveloppe convexe : dimension, nombre de points

1.2 Définitions

Trois types de complexité

Dans le pire des cas

Instance pathologique pour l'algorithme

Utilisé le plus souvent car donne une borne supérieure

Dans le meilleur des cas

Instance ”parfaite” pour l'algorithme

En moyenne

Pas d'hypothèses sur l'instance

Plus compliquée à calculer

Donne une idée plus proche du comportement réel

Aussi, complexité amortie…

1.2 Définitions

La complexité est fonction de la taille du problème

Elle peut être compliquée

Exemple : 𝑓 𝑛,𝑚 = 3𝑛 +𝑚2 − 2 log 𝑛 + 3 +𝑚5 𝑛

Précis mais peu pratique

Ordre de grandeur

Expression simplifiée indiquant l'évolution

Même comportement limite que la formule

Simplifie les comparaisons et analyses

1.3 Classes de complexité

Ordre de grandeur

Notation 𝑜 : 𝑓 𝑥 = 𝑜 𝑔 𝑥 si lim𝑥→∞

𝑓 𝑥

𝑔 𝑥= 0

𝑓 croît plus lentement que 𝑔

Exemples

sin 𝑥 = 𝑜 𝑥 17𝑥2 + 3𝑥 − 4 = 𝑜 𝑥4

Notation 𝑂 : 𝑓 𝑥 = 𝑂 𝑔 𝑥 si ∃𝑘|∀𝑥 > 𝑥0, 𝑓 𝑥 < 𝑘𝑔 𝑥

𝑓 dominée par 𝑔 à partir d'un certain point 𝑥0

Exemples

sin 𝑥 = 𝑂 𝑥 sin 𝑥 = 𝑂 1

𝑂 moins précis et plus simple à obtenir que 𝑜

𝑂 suffisant en général


Notations

Notation ~ : 𝑓 𝑥 ~𝑔 𝑥 si lim𝑥→∞

𝑓 𝑥

𝑔 𝑥= 1

𝑓 et 𝑔 sont globalement similaires

Exemples

17𝑥2 + 3𝑥 − 4~17𝑥2

on se concentre sur le terme dominant

ne fonctionne pas pour les fonctions trigonométriques (Taylor !)

Autres notations

Notation Θ

Notation Ω


On va rester sur 𝑂

On va chercher la fonction 𝑔 la plus ”approchante”

∃𝑘|∀𝑥 > 𝑥0, 𝑓 𝑥 < 𝑘𝑔 𝑥 et lim𝑥→∞

𝑓 𝑥

𝑔 𝑥= 𝑘

on se concentre sur le terme dominant dans 𝑓

on essaie de l'approcher au mieux

Exemples

17𝑥2 + 3𝑥 − 4 = 𝑂 𝑥2

sin 𝑥 = 𝑜 1


Principales classes de complexité

𝑂 1 constante

𝑂 log 𝑛 superlinéaire (logarithmique, etc.)

𝑂 𝑛 linéaire

𝑂 𝑛 log 𝑛 n-log-n

𝑂 𝑛2 quadratique

𝑂 𝑛3 cubique

𝑂 2𝑛 exponentielle

𝑂 𝑛! factorielle


Évolution de la quantité de calculs

𝒏 log 𝑛 𝒏 𝒏 log𝒏 𝒏𝟐 𝒏𝟑 𝟐𝒏 𝒏!

10 3,3 10 3,3 × 10 102 103 103 3,6 × 106

102 6,6 102 6,6 × 102 104 106 1,3 × 1030 9,3 × 1057

103 10 103 1,0 × 104 106 109

104 13 104 1,3 × 105 108 1012

105 17 105 1,7 × 106 1010 1015

106 20 106 2,0 × 107 1012 1018


Évolution du temps de calcul

Une instance de taille 𝑛

Un ordinateur d’une puissance de 109 flops (gigaflop)

𝒏 102 103 106

𝑶 𝒏 < 1 s < 1 s < 1 s

𝑶 𝒏𝟑 < 1 s 1 s 32 ans

𝑶 𝒏𝟓 10 s 11 jours 3 × 1013 ans

𝑶 2𝒏 3 × 1014 ans 10281 siècles 103×105 siècles


Remarques

Pour des problèmes de petite taille, les termes constants ne

doivent pas être négligés

Exemple

0,00001𝑛3 vs. 𝑛2

On compare souvent sur l'asymptotique...

Conséquence

Rechercher l'algorithme offrant la meilleure complexité

Techniques pour réduire la complexité

1.4 Calcul de complexité

Calcul de la complexité

Évaluer le nombre d'opérations élémentaires

Considérer chaque étape de l'algorithme

Faire la somme des appels

Déduire l'ordre de grandeur

Nécessite de connaître quelques formules

Sommations

Récurrences

Limites


Rappels sur les séries


Rappels sur les relations de récurrence


Rappels sur les limites


Exercices

Addition, multiplication matricielle

Recherche linéaire, dichotomique, interpolation

Tri insertion, sélection, rapide, histogramme

2. Conception d’algorithmes

3. Problèmes NP-complets

Complexité d'un problème

Souvent plusieurs algorithmes possibles

Complexité du meilleur algorithme associé

Exemples

Recherche dans un tableau de taille 𝑛

𝑂 𝑛 s’il n’est pas trié

𝑂 log𝑛 s’il est trié

Tri dans un tableau de taille 𝑛

𝑂 𝑛 log 𝑛

Résolution de systèmes linéaires de taille 𝑛 × n

𝑂 𝑛2


Complexité d'un problème

Permet de connaître la classe d'un problème

Prouver qu'on ne peut faire mieux est complexe

Beaucoup de problèmes ouverts

Multiplication matricielle

Test de primalité

Problèmes combinatoires...


Au final, 2 catégories de problèmes

Les problèmes ”faciles”

faible complexité : 𝑂 1 → 𝑂 𝑛𝑘

existence d'algorithmes efficaces (pour 𝑘 petit !)

Les problèmes ”difficiles”

forte complexité : 𝑂 2𝑛 , 𝑂 𝑛!

absence d'algorithmes efficaces

contiennent souvent une structure combinatoire


Problèmes de décision

Leur réponse est oui / non

Utilisés pour la définition des classes P et NP

Exemples

PREMIER(a) : le nombre a est-il un premier ?

CONNEXE(G) : G est-il connexe ?

PCC(G,p) : le chemin p est-il le plus court ?

Problèmes d'optimisation traités ”par la bande”


Classe P (polynômial)

Problèmes de décision qui peuvent être résolus par un

algorithme fortement polynômial

Fortement polynômial

indépendant de la grandeur des données

Exemples

CONNEXE(G) : algo de parcours BFS

CHEMIN(G,o,d) : algo de parcours BFS

PREMIER(a) : algo de Aggarwal et al.


Classe NP (polynômial non-déterministe)

Problèmes de décision qui peuvent être résolus par un

algorithme non-déterministe fortement polynômial

Définition plus compliquée que pour P

À chaque étape, l'algorithme a plusieurs choix

Réponse ”oui” : il existe une séquence de branchements tels

que l'algorithme trouve

Réponse ”non” : quelque soit la séquence de branchements,

l'algorithme ne trouve pas


Classe NP

Exemples

HAMILTONIEN(G,o,d) : existe-t-il un chemin hamiltonien de o à d

dans G ?

COLORATION(G,k) : G peut-il être colorié avec k couleurs ?

SAT(f,x) : existe-t-il un vecteur x satisfaisant f ?

De petites modifications peuvent changer la classe

3-SAT est de classe NP, 2-SAT est de classe P

HAMILTONIEN(G,o,d) est de classe NP, EULERIEN(G,o,d) est de

classe P


Relation P ↔ NP

Trivialement P dans NP

”qui peut le plus, peut le moins”

Question ouverte : P = NP ?

sans réponse depuis 30 ans

un des 7 problèmes du Millennium Prize

à vous de répondre !


Classe Indécidable

Problèmes pour lesquels on ne connait pas d'algorithme qui

réponde en un nombre fini d'étapes

Exemple

HALT(P) : le programme P se termine-t-il ?

DIOPHANTE(E) : l'équation diophantienne E a-t-elle une solution ?


Classe Co-NP

Étant donné un problème, son complémentaire consiste à

échanger les réponses

Exemple

COMPOSE(a) : le nombre a est-il composé ?

PREMIER(a) : le nombre a est-il premier ?

change radicalement la nature de la question (il existe / quelque soit)

Un problème est dans Co-NP si le complémentaire est dans

NP


Réduction

Deux problèmes A et B

Une transformation f : A → B

un algorithme pour B résoud les instances de A

Si f est polynômiale

réduction polynômiale

si B est dans P alors A est dans P

Classe NP-difficile

Si tout problème NP peut se réduire polynomialement à A


Classe NP-complet

Problème NP-difficile qui est dans NP

Intérêt

un algo pour un problème NP-complet peut, de fait, résoudre

tous les problèmes NP

s'il existe un algo polynômial pour un problème NP-complet,

alors P = NP

Théorème de Cook (1971) : SAT est NP-complet

Karp (1972) : 21 problèmes NP-complets


Classe NP-complet

Karp (1972) : 21 problèmes NP-complets

Garey & Johnson (1979) : livre-référence


SAT(f)

Une formule booléenne est une expression (à base de AND,

OR, NOT et ()) de variables booléennes

Forme Normale Conjonctive

conjonction de clauses (disjonctions de litéraux)

ex :

𝑓 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 = ¬𝑎 ∨ 𝑏 ∨ 𝑐 ∨ ¬𝑑 ∧ ¬𝑏 ∨ 𝑒 ∧ ¬𝑐 ∨ 𝑑 ∨ ¬𝑒

Existe-t-il un vecteur satisfaisant la formule ?

ex : 𝐹 𝐹 𝐹 𝑉 𝑉

Problème fondamental de la classe NP-complet

Applications pratiques (logique, électronique...)


3-SAT(f)

Idem à SAT avec des clauses d'au plus 3 litéraux

Exemple :

𝑓 𝑎, 𝑏, 𝑐 = ¬𝑎 ∨ 𝑏 ∨ 𝑐 ∧ ¬𝑏 ∨ 𝑐 ∧ 𝑎 ∨ 𝑏 ∨ ¬𝑐

Existe-t-il un vecteur satisfaisant la formule ?

Exemple : 𝐹 𝐹 𝐹

Par contre 2-SAT est dans la classe P


CLIQUE(G,k)

On considère un graphe non orienté G=(V,E)

Sous-graphe complet

Existe-t-il une clique de cardinalité 𝑘 ?

Par la suite, trouver une clique de cardinalité maximum


STABLE(G,k)


Ensemble de sommets 2 à 2 non adjacents

Existe-t-il un stable de cardinalité 𝑘 ?

Aussi, trouver un stable de cardinalité maximum

Le stable et la clique sont complémentaires


COLORATION(G,k)


Affecter une couleur à chaque sommet

deux sommets adjacents ont une couleur ≠

Existe-t-il une coloration avec 𝑘 couleurs ?

Aussi, trouver le nombre minimal de couleurs

Note : 4 couleurs suffisent pour un graphe planaire


PLNE 0-1

On considère un PL avec des variables de décision

𝑥𝑖 = 0 → on ne prend pas la décision 𝑖

𝑥𝑖 = 1 → on prend la décision 𝑖

Le système admet-il une solution ?

Par la suite, trouver une solution optimale

PL est P, PLNE 0-1 est NP-complet


SUBSET-SUM

On a un ensemble de 𝑛 entiers 𝐸 = 𝑒1, … , 𝑒𝑛

On a un entier 𝑆

Existe-t-il une partie de 𝐸 de somme 𝑆 ?

Exemple : 𝐸 = −3,−1,2,6

pour 𝑆 = 0, pas de solution

pour 𝑆 = 1, 𝐸′ = −1,2

pour 𝑆 = 2, 𝐸′ = 2 ou 𝐸′ = −3,−1,6


SAC-A-DOS(c,p,P)

On considère 𝑛 objets d'intérêt 𝑐𝑖 et de poids 𝑝𝑖 On a une limite de poids total 𝑃

Existe-t-il une combinaison d'objets de poids 𝑃 ?

Aussi, trouver un ensemble viable d'intérêt max

Exemple : 𝑂 = 1,2 8,10 7,3 4,1

𝑃 = 12, 𝑂′ = 1,2 7,3 4,1 , intérêt = 12, poids = 6


Liens entre SUBSET-SUM et SAC-A-DOS

SAC-A-DOS peut résoudre SUBSET-SUM

On garde la contrainte de capacité

L'intérêt d'un entier est sa valeur

Si la solution de SAC-A-DOS sature la contrainte alors c'est une

solution de SUBSET-SUM

Sinon SUBSET-SUM n'a pas de solution

SUBSET-SUM est un problème d'existence

SAC-A-DOS est un problème d'optimisation

3.1 Méthodes exactes

Méthodes d'énumération

Forte complexité

Limitées à certains problèmes et à certaines tailles

Programmation Linéaire en Nombres Entiers

Reprend le formalisme de la PL

Considère des variables entières, modélisant

des quantités entières

des décisions


Variables de décision 𝑥𝑖 ∈ 0,1

Ne peuvent prendre que deux valeurs : 0 ou 1

𝑥𝑖 = 1 on prend la décision 𝑖

𝑥𝑖 = 0 on ne prend pas la décision 𝑖

Modélise ”simplement” des situations booléennes

Toute variable entière peut s'exprimer en décision

𝑥 ∈ ℕ → 𝑥 = 2𝑖𝑦𝑖𝑖=1…𝑘 avec 𝑦𝑖 ∈ 0,1


Résolution d'un PLNE

Branch & Bound (séparation / évaluation)

On relâche les contraintes d'intégrité du problème

On résoud le problème relâché

Si la solution est fractionnaire

il existe au moins une variable fractionnaire

on effectue un branchement dessus

stratégie récursive


Stratégies évoluées

Branch & Cut (génération de coupes)

Branch & Price (génération de colonnes)

Relaxation lagrangienne

Méthodes de décomposition

Dantzig-Wolfe

Benders

décomposition lagrangienne, ...

Programmation dynamique, ...

3.2 Méthodes approchées

Lorsque les problèmes sont de classe NP

Temps de calcul explose sur les grosses instances

Se tourner vers des méthodes approchées

on ne garantit plus l'optimalité de la solution

on réduit fortement les temps de calcul

compromis entre le temps et la qualité

3 grandes catégories

heuristiques

métaheuristiques

algorithmes d'approximation


Heuristiques

Principe général

les bonnes solutions ont certaines propriétés

contruire des solutions favorisant ces propriétés

La contruction doit rester polynômiale

souvent un algorithme glouton

à chaque itération de l'algorithme, on ne remet pas en cause les

choix précédents


Algorithmes gloutons

Algorithme itératif, choix irréversibles

le choix fixe une (des) variable(s) du problème

on réitère sur le reste du problème

équivaut à une descente dans l'arbre des choix

ne garantit pas l'optimalité (ni même la réalisabilité)

sauf si le choix est optimal

Si le choix à chaque itération est optimal

Alors c’est une méthode exacte (et itérative)

Exemples

recherche séquentielle/dichotomique, tri sélection

algorithmes de Prim, Kruskal, Dijkstra


Heuristiques

Deux types d'heuristiques

Contructives

on part de rien

on construit progressivement une solution

on itère jusqu'à la solution complète

d'amélioration

on part d'une solution

à chaque itération on la modifie (un peu)

on itère jusqu'à ne plus pouvoir améliorer

3.2 méthodes heuristiques

Heuristiques de construction

On part de la solution vide

À chaque itération

on a une liste d'éléments possibles à ajouter

on prend le meilleur (critère de sélection)

Jusqu'à obtention d'une solution

Critère de sélection polynômial (linéaire si possible)

Nombre d'itérations polynômial

Complexité polynômiale


Mise en application : SAC-A-DOS(c,p,P)

on trie les objets selon le ratio 𝑐𝑖 𝑝𝑖 décroissant

dans cet ordre

on prend l'objet si la capacité n'est pas violée

on passe au suivant

équivalent à une descente dans l'arbre des choix possibles

1 niveau par objet

pour chaque noeud, 2 branches (prend ou pas)

1 feuille = solution


Mise en application : SAC-A-DOS(c,p,8)

ordre = 2 1 6 4 5 3

itération 1 : on prend 2, capacité résiduelle 7


itération 3 : on ne prend pas 6




Solution = 1,2,5 , intérêt = 12, poids = 6

objet 1 2 3 4 5 6

intérêt 7 4 2 10 1 9

poids 3 1 5 7 2 5


Mise en application : SAC-A-DOS(c,p,8)

ordre = 2 1 6 4 5 3

solution obtenue = 1 2 5 , intérêt = 12, poids = 6

solution optimale = 1 6 , intérêt = 16, poids = 8

objet 1 2 3 4 5 6

intérêt 7 4 2 10 1 9

poids 3 1 5 7 2 5


Mise en application : MAX_STABLE(G)


on prend le sommet libre le moins connecté

on le supprime ainsi que ses voisins

Exemple

2

3

4

8

9

7 10 5

6

1


Mise en application : MAX_STABLE(G)

Exemple

itération 1 : sommet 1





2

3

4

8

9

7 10 5

6

1

2

3

4

8

9

7 10 5

6

1


Mise en application : MIN_COLORATION(G)


on cherche un stable max sur les sommets non colorés

on lui affecte une nouvelle couleur

réutilisation de l'heuristique précédente

Exemple

2

3

4

8

9

7 10 5

6

1


Mise en application : MIN_COLORATION(G)

Exemple

itération 1 : stable {1, 4, 6, 7, 10}

itération 2 : stable {2, 9, 5}

itération 3 : stable {3, 8}

2

3

4

8

9

7 10 5

6

1

2

3

4

8

9

7 10 5

6

1


Heuristiques d'amélioration : principe

On part d'une solution réalisable


on a une liste de modifications améliorantes

on en applique une (critère de sélection)

Jusqu'à ne plus pouvoir améliorer

Critère de sélection polynômial (linéaire si possible)

Nombre d'itérations pseudo-polynômial (valeur)

Complexité souvent pseudo-polynômiale


Heuristiques d'amélioration : voisinage

Repose sur la notion de mouvement

Notion fondamentale pour les recherches locales

𝑆 : espace des solutions

solution courante 𝑠0 ∈ 𝑆

un type de modification 𝑡

voisinage 𝑉𝑡 𝑠𝑜 : ensemble des solutions obtenues en appliquant 𝑡 sur 𝑠0 de toutes les manières possibles


Exemples de voisinage

Stable

supprimer/ajouter/échanger des sommets

Coloration

changer la couleur d'un sommet (stable)

Sac-à-dos

supprimer/ajouter/échanger des objets


Heuristiques d'amélioration : voisinage

Gestion du voisinage

Exploration

complète : on visite tous les voisins

partielle : on ne visite qu'une partie du voisinage

premier réalisable

𝑘 voisins

Sélection

Meilleur voisin

premier voisin améliorant

un voisin au hasard


Heuristiques d'amélioration : distance

Soit 𝑡 un type de modification

Distance 𝑑𝑡 𝑠1, 𝑠2 entre deux solutions 𝑠1 et 𝑠2

nombre minimal de mouvements de type 𝑡 pour aller de 𝑠1 à 𝑠2

conditions pour définir une métrique

non-négative : 𝑑𝑡 𝑠1, 𝑠2 ≥ 0

élément nul : 𝑑𝑡 𝑠1, 𝑠2 = 0 ⇔ 𝑠1 = 𝑠2

symétrie : 𝑑𝑡 𝑠1, 𝑠2 = 𝑑𝑡 𝑠2, 𝑠1

inégalité triangulaire : 𝑑𝑡 𝑠1, 𝑠2 ≤ 𝑑𝑡 𝑠1, 𝑠3 + 𝑑𝑡 𝑠3, 𝑠2


Heuristiques d'amélioration : optimum

Soit 𝑡 un type de modification

𝑠0 est un optimum local si

𝑓 𝑠0 ≤ 𝑓 𝑠 , ∀𝑠 ∈ 𝑉𝑡 𝑠0

𝑠0 est un optimum global si

𝑓 𝑠0 ≤ 𝑓 𝑠 , ∀𝑠 ∈ 𝑆

𝑓 𝑠0 ≤ 𝑓 𝑠 , ∀𝑡 ∀𝑠 ∈ 𝑉𝑡 𝑠0

les deux critères sont aussi compliqués à vérifier


Heuristiques d'amélioration: SAC-A-DOS(c,p,P)

Voisinage 1

ajout d'un objet

fonctionne sur des solutions quelconques

mais pas sur les solutions de l'heuristique vue précédemment

(pourquoi ?)

complexité = 𝑂 𝑛

Voisinage 2

suppression d'un objet + ajout d'un autre

complexité = 𝑂 𝑛2


Heuristiques d'amélioration : MAX_STABLE(G)

Voisinage 1

ajout d'un sommet

fonctionne sur des solutions quelconques

mais pas sur les solutions de l'heuristique vue précédemment

(pourquoi ?)

complexité = 𝑂 𝑛

Voisinage 2

suppression d'un sommet + ajout d'un autre

complexité = 𝑂 𝑛2


Heuristiques d'amélioration : MIN_COLORATION(G)

Voisinage 1

changement de la couleur d'un sommet

complexité = 𝑂 𝑘𝑛2

Voisinage 2

extraire 𝑘 sommets

les réinsérer en les coloriant

Voisinage 3

extraire 𝑘 sommets indépendants

créer une nouvelle couleur pour eux


Recherche Locale

Regroupe plusieurs stratégies pour l'amélioration

méthode de descente (hill climbing)

une structure de voisinage (type de modification)

appliquée sur la solution courante tant qu'on peut

méthode à voisinages variables (VND)

𝐾 structures de voisinage, triées (complexité)

on commence par la plus simple (𝑘 ← 1)

si on améliore, on valide et on réinitialise (𝑘 ← 1)

sinon, on passe à la suivante (𝑘 ← 𝑘 + 1)

on stoppe lorsque 𝑘 = 𝐾

N1

N2

N4

N5

N3


Métaheuristiques

Stratégies d'exploration de l'espace des solutions

Pallier les limites des recherches locales

blocage sur le premier optimum local

vision myope de l'espace des solutions

Deux grandes catégories

évolution de population : algorithme génétique, colonies de

fourmis, scatter search...

monosolution : recuit simulé, recherche tabou, GRASP, VNS...

Hybridations : combinaisons de métaheuristiques


Recuit simulé

Années 80 : Kirkpatrick, Gelatt & Vecci

Analogie avec la sidérurgie

gérer le refroidissement d'un alliage

si trop rapide → cristallisation

si apparition de cristaux → réchauffe

un paramètre : la température 𝑇

température initiale 𝑇0, paliers : 𝑇 ← 𝛼𝑇 toutes les 𝜏 itérations

choix d'un mouvement au hasard 𝑠 ∈ 𝑉 𝑠𝑜

si Δ = 𝑓 𝑠 − 𝑓 𝑠0 ≥ 0, proba d'accepter 𝑒−Δ 𝑇


Recherche Tabou

Années 80 : Glover, Hansen

Autoriser les voisins non améliorants

Mais risque de cyclage (revenir sur des solutions déjà visitées)

Introduction d'une liste tabou

stocke les 𝜏 dernières solutions visitées

on s’interdit de revenir dessus

mise à jour à chaque itération

Extensions : aspiration, intensification/diversification


GRASP

Années 90 : Feo & Resende

Rafinement de la technique du multistart

Multistart

on génère aléatoirement une solution (construction)

puis on l'améliore (recherche locale)

on fait ça 𝑘 fois

on garde la meilleure solution

GRASP

la génération est randomisée (glouton+aléatoire)

Extensions : path relinking, hybridations


VNS

Années 90 : Hansen & Mladenovic

Utilisation de plusieurs voisinages

Raisonnement géométrique

𝑘 structures de voisinages, triées (complexité)

on commence par la plus simple (𝑘 ← 1)

on prend un voisin dans le voisinage

on lui applique une recherche locale

si on améliore, on valide et 𝑘 ← 1

sinon, 𝑘 ← 𝑘 + 1 (stoppe lorsque 𝑘 = 𝐾)

Utilisation conjointe de VNS et VND


Algorithme génétique

Années 70 : Holland

Analogie avec la sélection naturelle

une population d'individus

un individu = un chromosome

encodage d'une solution (évaluation = fitness)

création de nouveaux individus

croisement, mutation

sélection de la nouvelle population

Clés : gestion de la diversité, hybridation (algorithmes

mémétiques)


Colonies de fourmis

Années 2000 : Dorigo

Analogie avec les fourmis

recherche coopérative de la nourriture

chaque fourmi construit une solution

utilise information locale (gloutonne)

utilise information globale (phéromone)

phéromone = support de communication

mise à jour de la phéromone en fonction des résultats

biais vers les bons éléments

4. Problèmes d'ordonnancement

Partie de Philippe Lacomme !

5. Problèmes de transport

Transport de biens / personnes

Composante essentielle de la société moderne

Charbon puis pétrole : essor du transport moderne

plus rapide : réduction des délais de transport

plus loin : accès à de nouveaux marchés, délocalisation

plus sûr : maîtrise des aléas

davantage : augmentation des quantités transportées

Massification des transports


Environnement fortement concurrentiel

Mécanisme de bourse au transport

Répondre aux offres de transport

Offrir les meilleures prestations de transport

délais, coûts

Savoir rapidement si une offre est intéressante

augmentation du bénéfice

respect de la nouvelle demande

respect des demandes existantes


Trois entités en jeu

Client : quantité, origine, destination, dates...

Véhicule : capacité, vitesse...

Réseau : urbain / routier, distances

Dimensions

Nombre de demandes, de véhicules

Prétraitement

Calcul du chemin entre chaque point

Réduction au sous-graphe des points


Exemples de problématiques

Organiser des tournées de transport (ex : la Poste)

collecte, livraison, collecte + livraison

gestion de la flotte de véhicules

satisfaire tous les clients

Organiser des lignes régulières (ex : bus, train)

point d'arrêt, fréquence

gestion de la flotte de véhicules

satisfaire le plus de clients possible


Problèmes de transport en Aide à la Décision

Des problèmes simples

Plus court chemin

Problème de transport

Flot maximal, flot de coût minimal

Aux problèmes difficiles

Voyageur de commerce

Tournées de véhicules

Transport à la demande


Problème de Plus Court Chemin (PCC)

soit un graphe 𝐺 = 𝑆, 𝐴 muni de coût sur les arcs, trouver

le plus court chemin d'un sommet origine 𝑜 à un sommet

destination 𝑑

coût positifs : Dijsktra, Bellman

coût négatifs (sans cycle) : Bellman

problème polynômial

sous-problème de nombreux problèmes de transport


PCC : Dijsktra

2 ensembles de sommets

𝑆1 : sommets validés

𝑆2 : sommets non traités

labels de distance : 𝜋

1. // initialisation

2. 𝑆1 ← ∅

3. 𝑆2 ← 𝑆

4. 𝜋𝑠 ← 0

5. 𝜋𝑖 ← ∞,∀𝑖 ≠ 𝑠

6.

7. // boucle d’expansion

8. tant que 𝑺𝟐 ≠ ∅

9. 𝑖 ← 𝑎𝑟𝑔𝑚𝑖𝑛𝑗∈𝑆2 𝜋𝑗

10. 𝑆1 ← 𝑆1 ∪ 𝑖

11. 𝑆2 ← 𝑆2 ∖ 𝑖

12. ∀ 𝑖, 𝑗 ∈ 𝐴

13. si 𝜋𝑗 > 𝜋𝑖 + 𝑐𝑖𝑗 alors

14. 𝜋𝑗 ← 𝜋𝑖 + 𝑐𝑖𝑗

on peut ajouter une structure pour stocker le sommet qui connecte chaque sommet dans l’arbre des PCC


PCC : Bellman

𝐿 liste des sommets modifiés

propage le label aux voisins

labels de distance : 𝜋

on peut ajouter une structure pour stocker le sommet qui connecte chaque sommet dans l’arbre des PCC

1. // initialisation

2. 𝜋𝑠 ← 0

3. 𝜋𝑖 ← ∞,∀𝑖 ≠ 𝑠

4. 𝐿 ← 𝑠

5.

6. // boucle de correction

7. tant que 𝑳 ≠ ∅

8. Choisir 𝑖 ∈ 𝐿

9. ∀ 𝑖, 𝑗 ∈ 𝐴

10. si 𝜋𝑗 > 𝜋𝑖 + 𝑐𝑖𝑗 alors

11. 𝜋𝑗 ← 𝜋𝑖 + 𝑐𝑖𝑗

12. si 𝒋 ∉ 𝑳 alors

13. 𝐿 ← 𝐿 ∪ 𝑗


Présence de cycle négatif : pas d'optimalité

rechercher un PCC élémentaire

NP-difficile

Méthodes exactes

Programme linéaires en nombres entiers

Programmation dynamique


Problème de Transport

soit un graphe biparti 𝐺 = 𝑆1, 𝑆2, 𝐴 muni de quantités sur

les sommets et de coûts unitaires sur les arcs, trouver le flot

de coût minimal permettant de router les entités de 𝑆1 (producteurs) vers 𝑆2 (consommateurs)

stocks = demandes, sinon on ajoute un élément fictif (p/c)

problème polynomial

solutions initiales : coin nord-ouest, Balas-Hammer

optimisation : stepping stone ou programmation linéaire


Problème de Flot Maximal

soit un graphe 𝐺 = 𝑆, 𝐴 muni de capacités sur les arcs,

trouver le flot maximal d'un sommet origine 𝑜 à un sommet

destination 𝑑


algorithme de Ford-Fulkerson

algorithme de push-relabel


Problème de Flot de Coût Minimal

soit un graphe 𝐺 = 𝑆, 𝐴 muni de capacités et de coûts

unitaires sur les arcs, trouver le flot de coût minimal routant

𝑞 unités d'un sommet origine 𝑜 à un sommet destination 𝑑


algorithme de suppression de cycle négatif

algorithme de plus courts chemins successifs


Problème du Voyageur de Commerce (TSP)

soit un graphe 𝐺 = 𝑆, 𝐴 muni de coûts sur les arcs, trouver

un cycle hamiltonien de coût minimal

problème NP-complet

méthodes exactes

programmation linéaire en nombres entiers, coupes

méthodes approchées

heuristiques, métaheuristiques

Un des problèmes phares de la RO

Presque toutes les méthodes exactes et approchées ont été

testées dessus

Permet donc de connaître le potentiel d'une nouvelle

méthodes

Intérêt multiple

industriel : au coeur de presque toutes les problèmatiques de

transport

académique : un des problèmes complexes les plus simples

ludique : simple à comprendre / visualiser


Exemple

Concours dans les années 50 : trouver le plus court cycle

passant par la capitale des 48 états + Washington (hors Alaska

et Hawai)

Solution fournie en 1954 par Dantzig, Fulkerson et Johnson

Modèle linéaire, relaxation, coupes, branch&bound


Présence de nombreuses variantes

sur les distances

euclidiennes ou non

normes 𝐿1, 𝐿2, 𝐿∞

symétrique, asymétrique

complet ou non

sur les contraintes

interdiction de certains virages

précédence entre certains noeuds



Problème de Tournées de Véhicules (VRP)

Soit un graphe 𝐺 = 𝑆, 𝐴 muni de coûts sur les arcs, où le

sommet 0 représente le dépôt et les sommets 1. . 𝑛 les clients.

Chaque client possède une demande 𝑞𝑖 > 0 à traiter par une

flotte de véhicules identiques de capacité 𝑄. On souhaite

desservir les clients en minimisant le nombre de véhicules et, de

manière secondaire, le coût.

Problème NP-difficile

Généralisation du TSP


De (très) nombreuses variantes

Problème central en logistique

Fenêtres de temps (date d’ouverture / fermeture)

Livraison / collecte

Gestion explicite de l’espace de stockage

Possibilité de livrer un client par plusieurs véhicules

Flotte hétérogène

Multi-dépôts

Livraison sélective


Problème de Transport à la Demande (PDP)

Soit un graphe 𝐺 = 𝑆, 𝐴 muni de coûts sur les arcs, où le

sommet 0 représente le dépôt et les sommets 1. . 𝑛 les clients.

Un ensemble 𝑜𝑖 , 𝑑𝑖 , 𝑞𝑖 , 𝑖 = 1…𝑟 de requêtes de transport

doit être traité par une flotte homogène de capacité 𝑄. Chaque

requête est un triplet origine, destination, quantité. On souhaite

traiter les requêtes en minimisant le nombre de véhicules et, de

manière secondaire, le coût.

Problème NP-complet

Généralisation du VRP


Globalement, mêmes variantes que pour le VRP

Le VRP modélise un transport organisé par le dépôt

Livraison depuis un dépôt logistique

Collecte (logistique inverse, retraitement)

Le PDP modélise un transport point-à-point

Déménagements

Bourse de transport

5.1 Le VRP

Données

Graphe 𝐺 = 𝑆, 𝐴 , dépôt 0, clients 1…𝑛, demande 𝑞𝑖, coût 𝑐𝑖𝑗 , véhicules de capacité 𝑄

Contraintes

Chaque client doit être desservi, en une seule fois

Chaque véhicule débute et termine sa tournée au dépôt

Sa capacité doit être respectée

Objectifs

Minimiser le nombre de véhicules (primaire)

Minimiser le coût total (secondaire)

5.1 Le VRP

Représentation géographique

Représentation logique

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2 3 4

5 6

7 9 8

10

11 12 13

0 0

5.1 Le VRP

Structures de données

Représentation du graphe

Vecteur de sommets

Vecteur d’arcs

Listes d’adjacence

Représentation d’une solution

Vecteur indexé sur les clients (indique le prochain arc)

Vecteur indexé sur les véhicules (indique le premier arc)

Éventuellement

Vecteur indexé sur les véhicules (indique le dernier arc)

Vecteur indexé sur les clients (charge en quittant le sommet)

Vecteur indexé sur les clients (numéro de tournée associée)

5.1 Le VRP

Heuristiques constructives Création de tournées valides (dépôt – {clients} – dépôt)

Respect à chaque itération de la capacité

Choix des arcs de faible coût

Principes généraux Séquentiel / parallèle : toutes les routes sont actives ou non

Clustering : regrouper un sous-ensemble de clients

Routing : ordonner un sous-ensemble de clients

Stratégie « cluster || route »

Stratégie « cluster first – route second »

Stratégie « route first – cluster second »

5.1 Le VRP

Heuristiques « classiques »

Savings (Clarke & Wright 64)

Construire des tournées élémentaires puis les fusionner

Insertion (Solomon 87), « cluster || route »

Ouvrir une nouvelle tournée puis insérer des clients tant que possible

Sweep (Gillett & Miller, 74), « cluster || route »

Balayage radial pour les clients, sinon ≈ insertion

Fisher & Jaikumar (81), « cluster first – route second »

Affectation généralisée pour le clustering, puis un TSP par route

Split (Beasley 83), « route first – cluster second »

TSP puis découpage optimal par algorithme Split

5.1 Le VRP

Heuristique Savings

On crée initialement une tournée par client


On considère la possibilité de concaténer deux tournées

Pour tout couple de tournées 0,… , 𝑖, 0 et 0, 𝑗, … , 0

Vérifier le respect de la capacité

Vérifier le gain en distance : 𝜇𝑖𝑗 = 𝑐𝑖0 + 𝑐0𝑗 − 𝑐𝑖𝑗 > 0

Choisir une fusion améliorante

Soit la première trouvée

Soit la meilleure trouvée

Astuce

trier les arcs selon le gain décroissant

évaluer les possibilités de fusion dans cet ordre

5.1 Le VRP

Heuristique Savings

Solution initiale Première itération

Seconde itération Troisième itération…

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

5.1 Le VRP

Heuristique d’insertion

On crée les tournées une à une

Pour chaque tournée

On commence par la tournée vide

Parmi les clients non traités, on recherche celui dont l’insertion en fin

Respecte la contrainte de capacité

Augmente le moins la distance

S’il existe, on l’insère, sinon on crée une nouvelle tournée

Nombreuses variantes

Considérer un ordre sur les clients

Considérer les insertions en fin ou n’importe où dans la tournée

Considérer les insertions dans la tournée courante ou dans toutes

5.1 Le VRP

Heuristique d’insertion

Solution initiale Première itération

Seconde itération Troisième itération…

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

1 2

3

4

5

6

7

9

8

10

11

12

13

0

5.1 Le VRP

Structures de voisinage

Mouvement de type 𝑘 − Opt

Défini à la base pour le TSP

Consiste à retirer 𝑘 arcs et à en insérer 𝑘 autres

𝑘-optimalité : il n’existe aucun mouvement 𝑘 − Opt améliorant

Complexité d’évaluer un voisinage 𝑘 − Opt

Nombre de voisins = 𝑂 𝑛𝑘

Évaluer un voisin = 𝑂 1

Complexité finale = 𝑂 𝑛𝑘

En pratique, on se limite à 𝑘 ≤ 4 (et encore, sur des cas particuliers)

5.1 Le VRP


Le mouvement 2-Opt

Remplacer 2 arcs par 2 autres

2 variantes, selon qu’ils appartiennent à la même tournée ou pas

2-Opt interne = renverser une partie de la tournée

Test de capacité inutile

Inutile de considérer 2 arcs successifs

Cas particulier, le swap

Illustration (général et swap)

5.1 Le VRP


Le mouvement 2-Opt

2-Opt externe = échanger deux fins de tournée

Tests de capacité nécessaires

Inutile de considérer simultanément les arcs initiaux ou finaux

Possibilité de supprimer une tournée

Illustration (général et suppression tournée)

5.1 Le VRP

Structures de voisinages

Voisinages de type 3-Opt

Remplacer 3 arcs par 3 autres

Davantage de variantes

3-Opt interne = déplacer un bloc de tournée dans la tournée

Test de capacité inutile

Habituellement, on limite la taille du bloc à déplacer (1, 2, 3 éléments)

Illustrations (général, bloc 1 élément)

5.1 Le VRP



3-Opt externe 1 = déplacer un bloc dans une autre tournée

Test de capacité nécessaire pour la tournée de réception

Habituellement, on limite la taille du bloc à déplacer (1, 2, 3 éléments)


Illustrations (général, bloc 1 élément, suppression)

5.1 Le VRP



3-Opt externe 2 = échanger la fin de 3 tournées

Tests de capacité nécessaires

Généralisation du 2-Opt externe


Illustrations (général, suppression)

5.1 Le VRPTW

Impact des fenêtres de temps

Chaque sommet 𝑖 ∈ 𝑆 reçoit

Une fenêtre de temps 𝐴𝑖; 𝐵𝑖

Une durée de livraison 𝑡𝑖

→ Plage de disponibilité du client (date d’ouverture et de fermeture)

Interprétation pour le dépôt

Les véhicules ne peuvent quitter le dépôt avant 𝐴0

Ils doivent retourner au dépôt avant 𝐵0

Extensions

Fenêtres de temps multiples

5.1 Le VRPTW

Impact des fenêtres de temps

Principe

Le véhicule ne peut arriver après 𝐵𝑖

S’il arrive dans la fenêtre, il traite le client immédiatement

S’il arrive avant 𝐴𝑖, il attend l’ouverture pour pouvoir traiter le client

Impact

Ajouter un vecteur indexé sur les clients (date d’arrivée)

Tests de respect des fenêtres de temps en 𝑂 𝑘 , voire en 𝑂 1

Documents

Outils d’Aide à la Décisionduhamel/OAD/2014_OAD.pdf · Temps de calcul ... Outils de profilage, de tests (unitaires, ... HAMILTONIEN(G,o,d) : existe-t-il un chemin hamiltonien