Introduction à l’Analyse Prescriptive · Plan 1. Introduction 2. Optimisation sous Contraintes 3. Focus sur l’Optimisation Combinatoire 4. Du problème à la solution 5. Contexte

Introduction à l’Analyse Prescriptive

M.-J. Huguet

https://homepages.laas.fr/huguet

2018-2019

Organisation Intervenants : Marie-José Huguet Patrick Esquirol Mikael Capelle Mohamed Siala

Evaluation : TP - Projet

2

Pré-requis : Logique, IA Graphes, Programmation Linéaire, Complexité, Méta-Heuristiques, Algorithmique

Plan

1. Introduction

2. Optimisation sous Contraintes

3. Focus sur l’Optimisation Combinatoire

4. Du problème à la solution

5. Contexte des données massives

3

Section 1. Introduction

4

Des données Origines : Capteurs, Téléphones portables, Sites Web, ….

Types : Séries numériques, images, textes, vidéos, …

Accessibilité : De plus en plus de données « ouvertes » collectivités locales, gouvernement, …

Caractéristiques : Explosion de la quantité de données numériques produites Hétérogénéité des données Protection de la vie privée

5

Exploitation des données (1)

3 niveaux de « data analytics » Analyse descriptive (Descriptive Analytics) Extraire des connaissances à partir des données

Que s’est-il passé ?

o Pourquoi y-a-t-il un bouchon ?

Analyse prédictive (Predictive Analytics) Construire des modèles pour prévoir le futur

Que va-t-il se passer ?

o Quel sera le trafic dans 1 heure ?

Analyse prescriptive (Prescriptive Analytics) Assister la prise de décision

Comment optimiser ?

o Quel est le meilleur itinéraire si je pars à 8:30 ?6

Voir UF du tronc commun

Mineure AP

Exploitation des données (2)

Analyse descriptive : Production d’indicateurs Comment les interpréter ? Lesquels choisir ? Comment les exploiter ?

Analyse prédictive : Construire des modèles pour prévoir le futur Comment agir sur une tendance prévue ?

Analyse prescriptive : Produire des optimisations Aide à la décision, Simulation,

Expert métier

o Exemples : systèmes de tarification, planification des transports et de la distribution, planification financière, allocation de ressources, …

7

Analyse prescriptive Très nombreuses applications : Villes intelligentes, Environnement, … Entreprises secteur industriel et services

Optimisation / Décision / Planification Intelligence Artificielle

Recherche arborescente, méta-heuristiques

Programmation par Contraintes, Satisfiabilité booléenne (SAT)

Recherche Opérationnelle Optimisation combinatoire

Programmation mathématique

8

En savoir plus ROADEF : Société Française de Recherche Opérationnelle et d’Aide à la

Décision (ROAEF) ROADEF : http://www.roadef.org

AFIA Association Française pour l'Intelligence Artificielle (AFIA)

AFIA : http://afia.asso.fr/

Chercheurs / Enseignants Chercheurs / Industriels

Stages, emplois,

Conférences, Formations, Ressources, ….

Journées conjointes ROADEF/AFIA Apprentissage et Optimisation combinatoire

9

En savoir plus Mais aussi : Association Française pour la programmation par Contraintes (AFPC)

o http://www.afpc-asso.org/

GdR RO / GdR IA (CNRS) : Recherche : différents groupes de travail

http://gdrro.lip6.fr/

http://www.gdria.fr/

10

Exemple Gestion des vélo en libre service Trouver un vélo / Trouver une place dans une station Modèle d’utilisation des vélos Capteurs sur les vélos

Prévisions météo

Calendrier

Dimensionnement des stations

Planification des acheminements

Calcul d’itinéraires

Aménagements cyclables

11http://data2b.net/

Exemple Optimisation des consommation énergétiques Prévision des besoins Sources énergétiques Météo

Planifier l’utilisation de l’énergie

12

Section 2. Optimisation sous Contraintes

13

Modélisation : Problème , , , : : ensemble des variables du problème : domaine des variables A chaque variable → : les valeurs pouvant être prises par

: contraintes du problème Relations entre les variables : restreindre les valeurs possibles

: → : fonction Objectif

Résoudre le problème , , , : Instancier chaque variable par une valeur tel que :

∈

Toutes les contraintes sont respectées

La fonction soit minimisée / maximisée14

Classification (partielle) de problèmes ∅ : pas de contraintes Problèmes d’Optimisation

∅ : pas d’objectif Problèmes de Décision / Satisfaction de Contraintes

: domaines énumérables (discrets) Problèmes Combinatoires

linéaire, inéquations linéaires : Problèmes d’optimisation linéaire (Programmation Linéaire / PL)

: Problèmes d’optimisation linéaire en nombres entiers (PLNE)

0,1 : Problèmes d’optimisation linéaire en variables binaires

15

Focus sur problèmes combinatoires

Problèmes d’optimisation combinatoire

Types de problèmes Planifier, Ordonnancer, Allouer (Planning, Scheduling, Allocation)

Transporter (Routing,Transportation) Traveling Salesman Problem, Vehicle Routing Problem, …

Découpe et Empilement (Cutting, Packing) Knapsack, Bin packing, …

Objectifs usuels Temps, Argent, Quantité

Equilibrage, Qualité de service, sécurité, environnement, …

Robustesse, …

16

Complexité Quelques problèmes de complexité polynomiale :

Problèmes de programmation linéaire

Problèmes d’affectation / couplage maximal

Problèmes 2-SAT

Graphes : plus courts chemins, connexité, arbres couvrants, flot max, …

Beaucoup sont NP-difficiles : Graphes : Voyageur de Commerce, Coloriage, Clique, …

3-SAT,

….

17

Exemple (1) Problème de Voyageur de Commerce Traveling Salesman Problem (TSP) Trouver un circuit de cout minimal passant une fois et une seule par tous les

sommets d’un graphe Complexité : NP-difficile

Problème standard Matrice de distance connue

Contexte « dynamique » Le cout de chaque trajet dépend des horaires

Time-dependent Shortest Path

o Impact complexité (FIFO – non FIFO)

18

Explosion combinatoire Exemple : nombre de solutions d’un TSP ! possbilités Méthode « Brute Force »

19Univers : 14 E+09 ans

Processeur 3 GHz 3 instructions par nano seconde

10 villes 1/100s

15 villes 1 heure

19 villes 1 an

27 villes 8x âge Univers

Processeur plus rapide 1 instruction /temps de Planck (5.39 10 )s

10 villes -

15 villes -

19 villes -

27 villes -

35 villes 5/100s

40 villes 12h

50 villes 400x âge Univers

Et en pratique … Certaines instances de problèmes NP-difficiles peuvent être résolues

rapidement Impact du taux de contraintes

Transition de phase

Certains problèmes NP-difficile peuvent avoir des cas particuliers de complexité polynomiale

Certains problèmes NP-difficiles sont approximables en temps polynomial avec garantie de performances / qualité solution

Exploration intelligente de l’espace de recherche de solutions Maitriser l’explosion combinatoire méthodes exactes / complètes

Contourner l’explosion combinatoire méthodes approchées / incomplètes

20

Section 3. Focus Optimisation Combinatoire

21

Cadres de Modélisation Problème , , , : Hypothèse : domaines énumérables (discrets)

3 grands cadres de modélisation et de résolution SAT Satisfiabilité booléenne

PLNE Programmation Linéaire en Nombres Entiers (PLNE)

Contraintes Constraint Satisfaction Problem (CSP)

22

Modèle SAT (1)

Raisonnement logique (Cours 4IR-Info)

Problème N variables booléennes M clauses Une clause = disjonction de littéraux Problème = conjonction de clauses Pas de fonction objectif

Exemple :

23

Modèle SAT (2)

Solution Une clause est satisfaite : au moins 1 littéral est VRAI Le problème est satisfait : toutes les clauses sont satisfaites

Exemple :

est satisfait avec les affectations :

Exemple : n’est pas satisfiable

SAT : problème NP-Complet (Cours 3MIC-Info)

24

Modèle PLNE (1)

Cadre de la Prog Linéaire (Cours 3MIC-Info) avec variables entières

Programmation Linéaire en Nombres Entiers Variables entières Contraintes : combinaisons linéaires de variables Objectif : combinaison linéaire de variables

Solution : affectation des variables minimisant l’objectif

25

Contraintes d’intégrité

Modèle PLNE (2)

Prog Linéaire (var. continues) Complexité : problème « facile » Existence d’un algo polynomial

Prog. Linéaire en variables entières Complexité : problèmes NP-difficiles Réduction (complexité linéaire) de toute instance

SAT en une instance de PLNE en variables 0/1

Illustration

Programmation Linéaire en variables 0-1 Programmation Linéaire en variables mixtes

26

Modèle CSP (1)

Constraint Satisfaction Problem Variables quelconques à domaines finis

(discrets) (continus)

Contraintes : quelconques en intension ou en extension

Solution : instanciation des variables

Complexité NP Complet : généralisation SAT

27

Modèle CSP (2)

Exemple

Objectif Quelconque Problème de décision ou d’optimisation

28

Modèle CSP (3)

CP : Constraint Programming Méthodes et Outils pour Modélisation :

Spécifier un problème dans un langage déclaratif

Résolution : Comment résoudre un problème

Méthodes par défaut

(CP PPC = Programmation par Contraintes)

29Ref cours – P. Flener– Summer School ACP-RO, 2017

Bilan sur les cadres de modélisation

Nature des domaines SAT : booléen / PLNE : entiers / CSP : quelconques mais finis

Contraintes SAT : clauses / PLNE : combinaison linéaire / CSP : quelconques

Objectif SAT : non / PLNE : oui / CSP : (oui, non)

Solution : affectation de valeurs aux variables

Problèmes NP-Complet Equivalent en termes de complexité

Pour un problème donné modèles non équivalents dans les 3 formalismes

efficacité pratique des méthodes différentes

30

Etude de ces 3 cadres dans la suite de l’UF

Résolution (1)

Espace de recherche des solutions : Ensemble de solutions (alternatives) : produit cartésien des domaines Taille de l’ensemble des solutions : …

Ensemble de solutions admissibles : Une solution ← , ∈ et satisfaites

Taille de : dépend des contraintes (et des domaines)

Taille espace de recherche : explosion combinatoire

Différents buts : Une solution décision/satisfaction

Une solution optimale optimisation

Toutes les solutions

31

Résolution (2)

Problème de décision / problème d’optimisation Pb d’optimisation : Min sachant contraintes Pb de décision : existe-t-il solution s avec contrainte et ?

Problème de décision problème d’optimisation Résoudre pb de décision pour différentes valeur de k Exemple : pour la minimisation

S’il existe une solution pour une valeur k donnée

o Diminuer la valeur de k

Sinon

o Augmenter la valeur de k

Complexité problème optimisation = celle du problème de décision associé

32

Résolution (3)

Comment contenir l’explosion combinatoire ? Exploration intelligente de l’espace de recherche de solutions

Maitriser l’explosion combinatoire méthodes exactes / complètes

Contourner l’explosion combinatoire méthodes approchées / incomplètes

Méthode complète / incomplète (décision) fournit une solution si le pb est satisfiable et prouve l’absence de solution si le pb

est insatisfiable

Méthode exacte / approchée (optimisation) fournit une solution dont l’optimalité est prouvée

Méthode approchées / incomplètes Heuristique

Méta-heuristique33

Vues en 4e-IR Info

Résolution (4)

Base des méthodes exactes / complètes Recherche arborescentes Pour les 3 cadres de modélisation (SAT, PLNE, CSP)

But : Maitriser l’explosion combinatoire

Principes généraux Décomposition en sous problèmes

Elagages

34

Résolution (4)

Base des méthodes exactes/complètes Recherche arborescente (SAT, PLNE, CSP) But : Maitriser explosion combinatoire

Principe recherche arborescente Séparer (Branch) :

Structurer l’exploration

Décomposer en sous problèmes disjoints de taille restreinte

Heuristiques de choix de variables et de choix de valeur

Elaguer : (Bound) Calcul de bornes / Objectif

(Propagate/Filtering) Propager pour réduire les domaines

35

P

P1 P2

P11 P12 P13

Résolution (5)

Principe des méthodes arborescentes Si une solution est obtenue pour un sous problème Arrêt de la décomposition

Si , , - Problème de satisfaction a une solution ssi ou ont une solution

Si une solution est obtenue pour : arrêt ( non considéré)

Si , , , - Problème d’optimisation (min) Opt ,

36

P

P1 P2

P11 P12 P13

Résolution (6)

Composition d’une recherche arborescente : Méthode de décomposition Comment séparer en sous-problème ?

Stratégie d’exploration Comment parcourir les sous-problèmes ? (profondeur, largeur,..)

Méthode d’élagage (coupe) : Peut-on éliminer des parties de l’arborescence ?

Evaluation Nombre de nœuds explorés Profondeur / Hauteur

37

Résolution (7)

Exemple de méthodes Algorithme DPLL (vu en 4e année – Prog Logique) Instanciation progressive de variables (ordre de parcours)

Elagage de l’arborescence (simplifier les clauses)

Retour arrière chronologique en cas d’échec

Algorithme A* (vu en 4e année – IA) Recherche d’un chemin dans des graphes d’états

Recherche guidée par fonction d’évaluation

38

Logiciels

SAT https://satcompetition.org/

PLNE Cplex, Gurobi, FicoXpress (Artelys) , … Scip, OR-Tools (google), Coin-OR AMPL, …

CP https://en.wikipedia.org/wiki/Constraint_programming CP Optimizer, … Choco, Gecode, Oscar, Comet, MiniZinc

39

Section 4. Illustration méthodes arborescentes

40

Cadre SAT – Recherche arborescente (1)

SAT Variables Booléennes : , ∈ 1,

Contraintes sous forme de clauses

Décomposition Sélectionner une variable : SP1 : ← et SP2 : ←

Taille arborescence Profondeur max = nombre de variable

Taille max : ∑ 2 2

Stratégie de parcours En profondeur d’abord

41


Algo DPLL (Davis-Putnam-Logemann–Loveland) Choisir un littéral et lui affecter une valeur (true ou false)

Si test cohérence == true passer au littéral suivant

Sinon Retour arrière

Arrêt Toutes les variables sont instanciées (une solution)

Incohérence du problème

Pb satisfiable : toutes les variables sont affectées sans détecter d’incohérence

Pb insatisfiable : explorer toute l’arborescence

42


Retour arrière De manière chronologique

Après chaque affectation ← (resp. ← ) Réduire les clauses

Éliminer les clauses contenant (resp. )

Eliminer des clauses le contenant (resp. )

Choix du littéral stratégie de branchement Impact sur la taille de l’arborescence

43


Exemple : ∨ ∨ ∧ ∨ ∨ Développer l’arborescence obtenue par l’algorithme DPLL Cas 1 : choisir puis puis ; valeur true en premier

Cas 2 : choisir puis puis

44


Améliorations Apparition de clauses unaires : fixer la valeur des variables présentes dans

une clause unaire (Propagation unaire) Les variables des clauses unaires sont sélectionnées en priorité pour le

branchement

Effet en cascade de réduction de clauses

Elimination de littéraux purs Littéral n’ayant qu’une seule forme dans toutes les clauses

Fixer la valeur du littéral (dans la stratégie de branchement)

Effet en cascade

45


Approfondissement Heuristiques de branchement efficaces Structures de données pour propager les clauses unaires efficacement Backjumping (retour arrière non chronologique) Inférer une clause expliquant l’incohérence

Revenir sur une instanciation source de l’incohérence

Apprentissage de clauses La clause inférée peut être ajoutée à l’ensemble des clauses du problème pour ne

pas reproduire l’échec

Restart Stopper l’exploration et la relancer

Ajouter de l’aléatoire dans l’heuristique de branchement

46

Cadre CSP – Recherche arborescente (1)

CSP Variables à domaines finis

Décomposition Pour chaque variable prise successivement

Décomposer en fonction des valeurs de cette variable

Arrêt toutes les variables ont une valeur (une solution)

47

P

X1 a X1 b

X2 a X2 b X2 c

X1 X1

X2X2

X2


Taille de l’arborescence CSP

Variables

Domaines

Taille max des domaines :

Taille arborescence

Stratégie de parcours : Profondeur d’abord

48


Algorithme : Choisir une variable

Lui affecter une valeur : ← Si test cohérence == true

passer à la variable suivante

Sinon Retour arrière

Arrêt Toutes les variables sont instanciées (une solution)

Incohérence du problème

Mécanisme de retour-arrière Backtrack Affecter une autre valeur à la variable : ← ’ Revenir à la variable précédente (chronologique)

49

BACKTRACK CHRONOLOGIQUE


Test de cohérence après instanciation Vérifier les contraintes liant aux variables précédentes

BACKWARD CHECKING

Retirer du domaine des variables reliées à la variable par une contrainte, toutes les valeurs ne satisfaisant pas la contrainte (Filtrage)

Si un domaine devient vide : incohérence FORWARD CHECKING

Autre : filtrage plus poussé (ex. arc-cohérence)

Impact important sur l’efficacité de la méthode

50


Stratégie de parcours (suite) Profondeur d’abord Ordre sur les variables Ordre sur les valeurs

Heuristiques d’instanciation statiques / dynamiques Heuristiques d’instanciation dédiées / génériques

Impact important sur l’efficacité de la méthode

51

Heuristique d’instanciation


Exemple

On recherche toutes les solutions de ce CSP Donner l’arborescence obtenu avec l’algo de Backtrack Chronologique

utilisant le Forward Checking Cas 1. Heuristique statique : ordre lexicographique sur les variables et les valeurs

Cas 2. Heuristique dynamique : Variable de plus petit domaine en priorité et ordre lexicographique sur les valeurs

52


Améliorations Techniques de propagation Compromis niveau de propagation / recherche

Heuristiques d’instanciation Heuristiques dédiées ou génériques

Backjumping Effectuer retour-arrière sur une variable cause de l’incohérence

Nogood recording Mémoriser les instanciations sources d’incohérence

Restart

53

Cadre PLNE– Recherche arborescente (1)

PLNE Variables entières Contraintes linéaires et Objectif linéaire

Recherche arborescente Nœud = un état du problème (espace de solutions) Arc = un changement d’état

Décomposition Séparation de l’espace des solutions

Evaluation des espaces de solutions Pour éliminer des espaces de solution

54

Branch and Bound


On veut résoudre

Soit l’espace des solution Partitionner deux ensembles et

Alors l’optimum

Si alors ne pas poursuivre l’exploration de

55


Evaluation Rôle clé dans un Branch and Bound

Principe pour un problème de maximisation Évaluation par borne supérieure: évaluation de la meilleure solution

possible

Quelle fonction d’évaluation ? Toute borne supérieure.

Par exemple la relaxation continue (obtention d’un PL)

56


Développement de l’arborescence Obtention d’un nœud

Si = 1 solution alors la mémoriser si elle améliore la solution courante

Si = pas de solution admissible alors éliminer

Si < solution courante alors ne pas le mémoriser

Sinon mémoriser dans l’ensemble des nœuds dont il faut poursuivre l’exploration

Dans quel ordre poursuivre la décomposition ?

57


Ordre d’exploration des nœuds Le dernier crée profondeur d’abord Privilégie l’obtention rapide d’une solution même de mauvaise qualité

Celui de meilleure évaluation largeur d’abord Limite la taille de l’arborescence

Séparation Choisir une variable et séparer par rapport à sa valeur non entière obtenue

lors de la résolution du PL Variable la plus contrainte, …

58


Exemple

Evaluer le PL àchaque nœud

59

S z=17.67

x1=1.55; x2=4.03

S1z=15.67

x1=1; x2=3.67

S2z=17

x1=2; x2=3.75

S5z=13

x1=1; x2=3

S6Incohérence

X1<= 1 X1 >= 2

X3<= 3X2 <= 3

X2 >=4 S4Incohérence

S3z=15.2

x1=3.2; x2=3

X3>= 4

S7z=15

x1=3; x2=3

X1<= 3 X1 >= 4

S8Incohérence


Améliorations du Branch & Bound Coupes Branch and Cut

Décomposition des contraintes Génération de colonnes

Branch and Price

60

Bilan méthodes arborescentes

Méthodes complètes / exactes Garantie d’optimalité Garantie d’absence de solutions

Mécanismes similaires dans les différents formalismes Heuristiques de branchement Stratégie de parcours

Spécificité en optimisation Estimation/Borne pour élaguer des parties de l’espace de recherche

61

Exercice – Recherche arborescente (1)

Développer un Branch and Bound Application : problème de voyageur de commerce (TSP) à 5 villes

Partir de A Séparation : Choisir arc de plus petit cout

Evaluation somme des n arcs de plus petits couts

62

A B C D EA X 1 7 3 14B 3 X 6 9 1C 6 14 X 3 7D 2 3 5 X 9E 15 7 11 2 X


Lien avec Algorithme A* (cours 4IR) Recherche dans des graphes d’états Etat initial

Etats Finaux

Opérateurs de changement d’état

But : découvrir un chemin de l’état initial vers un état final à cout minimal

Recherche ordonnée Utilisation d’une fonction heuristique sur les nœuds

Fonction d’évaluation

63


Algorithme A* Recherche ordonnée « de type A » La fonction heuristique au nœud x dépend de 2 sous fonctions

g(x) = Cout réel de l’état initial vers x

h(x) =Cout estimé de x vers un état final

Recherche ordonnée A* Le cout estimé h(x) est un minorant du cout réel

64


Dérouler l’algorithme A* sur le problème de TSP précédent

Etat initial : une ville X

Etats Finaux : toute séquence X*X

Changement d’état : ajouter une ville dans la séquence

Fonctions d’évaluation g(X*Y) = cout depuis X jusqu’à Y

h(X*Y) = estimation du trajet restant depuis Y

o Nb arcs restants * cout minimal des arcs possibles restants

o Somme des p arcs de plus petits couts s’il manque p arcs

65

Section 4. Du problème à la solution

66

Différentes étapes (1)1. Etude du problème

Entrées, Sorties, Relations

Complexité théorique

Construire un modèle

Déterminer une méthode de résolution adaptée

2. Conception de l’algorithme Propriétés (complexité, terminaison,

correction)

Retour en 1 si besoin

3. Développement de l’algo Propriétés (terminaison, correction)

Est-ce que le code fonctionne et produit les résultats attendus ?

Ex : vérificateur solution 67

Méthodes et outils : Complexité des algorithmes et des

problèmes (3MIC)Preuve de programmes (non vu dans la

formation)

Attention : un test peut montrer l’absence d’une propriétéLe test ne peut pas prouver la terminaison et la

correction (sauf si on peut énumérer toutes les entrées et

les tester toutes ….)

Différentes étapes (2)4. Préparation évaluation expérimentale

Conception de l’expérimentation : indicateurs, jeux de test, protocole, …

Mise en place d’un environnement de tests : infrastructure, scripts,

5. Réalisation de l’expérimentation Lancer l’exécution des scripts et collecter les résultats

Analyser les résultats

Retour étapes 1, 2 ou 3 si besoin

6. Amélioration de l’algorithme / du code Optimisation du code / de l’algorithme

Retour étape 5 si besoin

68

Focus sur évaluation expérimentale

Evaluation expérimentale : Evaluation des performances

Métrique de performance : critères à évaluer (durée d’exécution, qualité des solution, occupation mémoire, occupation bande passante, ….)

Indicateurs de performance : quantité mesurée pour évaluer une métrique Ex : temps CPU pour évaluer la durée d’exécution

Paramètres : élément qui a un impact sur la valeur d’un indicateur Paramètres de l’algorithme

Paramètres de l’instance (taille, caractéristique, …)

Paramètres de l’environnement (Processeur, Compilateur, OS, …)

69

Métriques et Indicateurs de performance Principales métriques

Qualité de la solution

Durée de l’exécution

Consommation mémoire

Dépendance entre ces métriques Consommation Bande Passante (algo répartis)

Calcul d’indicateurs de qualité Qualité solution :

Ecart (%) à la solution optimale ou à la meilleure solution connue

% d’exécution ayant atteint l’optimum (ou la meilleure solution connue)

Durée d’exécution : Nombre d’opérations caractéristiques

Temps CPU

70

Qualité d’une solution Ecart (%) à la solution optimale ou à la meilleure solution connue Soit une instance d’un problème de minimisation , , ,

représente la valeur optimale (minimale)

représente la valeur trouvée par une méthode

o C’est une borne supérieure de l’optimum (en minimisation)

o 100 / = écart (%) à la solution optimale

o L’écart à l’optimum est toujours positif

représente la meilleure valeur trouvée (référence …)

o 100 / = écart (%) à meilleure solution

o L’écart peut être positif ou négatif

représente une borne inférieure de l’optimum

o 100 / = écart (%) à une borne inférieure

71

Durée d’exécution Compter les opérations caractéristiques

Identification des opérations les plus fréquentes

Ajout d’un compteur

Indépendant / langage ou de l’OS mais pas toujours représentatif de la durée réelle

Mesurer le temps écoulé Temps réel : non fiable (impact de la charge)

Temps CPU : moyennement fiable

Bien analyser les résultats Impact de la charge en mémoire sur le temps

Quelques outils : time, gprof, getrusage()

72

Constitution d’un jeu de tests (1) Jeux de tests et nature des expérimentations

Programme correct

Evaluation des performances sur des cas réels Peut-on se comparer à des résultats antérieurs ?

Evaluation des performances dans le pire cas

Evaluation du passage à l’échelleo Jeux de tests aléatoires

Comparaison avec d’autres approches Jeux de tests existant (littérature)

Privilégier des jeux de tests homogènes (ou décomposables en classes homogènes) pour l’analyse des résultats

Privilégier des jeux de tests variés pour des résultats plus généraux73

Constitution d’un jeu de tests (2) Caractériser la difficulté d’une instance de test

Taille (ex : nb sommets et arcs d’un graphe)

Structure (ex: densité d’un graphe)

Taux de contraintes (Décision) Transition de phase

Caractéristique Espace des solutions (Optimisation) : paysage de recherche

Eliminer instances spécifiques (trop faciles ou trop difficiles)

Avoir des instances de difficulté variable74

Image– Cours C. Solnon – INSA Lyon, 2016

0

200

400

600

800

1000

1200

0 20 40 60 80 100 120

Analyse des résultats Techniques d’Analyse de données

Méthodes statistiques : Tests et analyses descriptives : pour valider ou invalider un hypothèse

Méthodes d’analyse exploratoire et de visualisation

Générer des données (résultats) faciles à analyser Mêmes jeux de tests pour toutes les expérimentations

Constitution de classes homogènes de jeux de test

Collecter et mémoriser toutes les données (résultats) pertinents

Normaliser les sorties des programmes

75

Cours Analyse Exploratoire et Visualisation de Données (5-SDBD)

Différents outils d’analyse

Campagne d’expérimentations (1) Conseils : Ne pas coder les paramètres de la méthode en dur

Lire dans un fichier ou passage d’arguments en ligne de commande

Utiliser un langage de script pour décrire les expérimentations Mémoriser tous les scripts (nature, date)

Organiser les expérimentations Plusieurs exécutions (scripts) indépendants

Organiser le stockage des résultats

Prévoir un script de lecture des résultats

o Tableaux de données brutes

76

Campagne d’expérimentations (2) But : obtenir des résultats intéressants et nouveaux

Caractéristiques Reproductibilité

Conserver toutes les spécificités (instances, paramètres, processeur, OS, ….)

Minimiser les dépendances …

Efficacité Automatiser le processus de lancement des expérimentations

Automatiser le processus d’analyse de données

Ne pas lancer d’expérimentations inutiles (cout en temps CPU et en temps de cerveau)

Mise à disposition du code avec machine virtuelle

77Ref. Section 4 :

Cours Christine Solnon – INSA Lyon (2016)C. McGeoch – A guide to experimental algorithmics, (2012, Cambridge Univ Press)

Section 5. Contexte des données massives

78

Impact des données (1) Problèmes déterministes Les données du modèle de décision/optimisation sont connues avant la

résolution

Décider en présence de données imprécises Certaines données sont obtenues à partir d’une analyse prédictive : au

moment de la prise de décision des données sont estimées Construction d’un modèle (prédictif) de ces données

Certaines données sont difficilement mesurables

La prise de décision s’effectue avec des données estimées (pour le calcul) L’application de la décision s’effectue sur des données différentes

79

Impact des données (2) Exemple : Ordonnancement sur 1 ressource

Problèmes : activités, date de fin de l’activité . ∑

Instance avec 4 activités de durée estimées : 23, 24, 25, 27

Ordonner par durée croissante. Solution obtenue : ∑ 241

Variation : 26 (+3); Solution ∑ 253 (+12)

Meilleure solution ∑ 250

80Adaptation cours – Christian Artigues– LAAS-CNRS, Master2 Recherche Opérationnelle, 2017

Exemples Taux de compression d’une image satellite variable

Présence ou non de nuages dans l’image compression différente

Temps de transfert satellite – sol dépend de la taille de l’image

Comment planifier les transferts ? Besoin d’anticiper un planning au sol (qualité de service, ….)

Données historique et Prévisions météorologiques

Plan d’acquisitions

Durée de trajet variable selon les horaires la circulation est plus ou moins fluide temps de trajets différents

Comment planifier l’organisation des trajets d’une flotte de véhicules ? Besoin d’anticiper un planning (fenêtre de collecte/livraison, temps de travail, …)

Données : historique des temps de trajets par tronçons,

capteurs sur les voies81

Approches de résolution (1) Retarder la prise de décision pour augmenter la fiabilité des données Décision « en ligne »

Parfois des besoins d’anticipation

Partage de la prise de décision Hors ligne : anticipation (données estimées/prévisionnelles)

En Ligne : adaptation (données mesurées)

Modifier la solution à partir des données réelles Pas toujours possible (ex : durée de trajet connue après sa réalisation)

82

Approches de résolution (2) Décision par horizon glissant

Contexte : décisions à appliquer dans la durée

Déterminer une solution pour un horizon de temps

Relancer la résolution par pas de temps pour intégrer de nouvelles données

Ex : plus court chemin par horizon glissant

83Adaptation cours – Christian Artigues, LAAS-CNRS – Master2 Recherche Opérationnelle, 2017

Approches de résolution (3) Optimisation Stochastique Les données varient selon des lois de probabilités Problème posé :

Déterminer des lois de probabilité représentant la variabilité des données

Prise de décision Données incertaines : variables aléatoires avec loi de probabilité

Minimisation de l’Espérance ( ) de la fonction objectif Hypothèses :

Lois de probabilités indépendantes

Composition de lois de probabilité

Passage à l’échelle

84

Exemple Ordonnancement sur 1 ressource Modélisation des durées des activités par des variables aléatoires

Objectif :Min ∑

Ordre des activités : plus petite durée espérée : 1 | 2 | 3 | 5

23,5; 24; 24,5; 25

Solution : ∑ 240

85

Approches de résolution (4) Optimisation Robuste Contexte : obtenir la décision la moins pire si le pire scénario se produit

Prise de décision : Modélisation de la variabilité des données :

Ensemble de scénarios et valeur des données pour chaque scénario

Données variant dans un intervalle de valeurs possibles

Objectif : minimiser la fonction objectif du pire scénario (minimax)

Passage à l’échelle : nombre de scénario

Le pire cas peut être sans intérêt pratique le plus mauvais taux de compression (jamais de nuages)

Autre objectif minimax et regret (absolu ou relatif)

86

Exemple Ordonnancement sur 1 ressource Modélisation des durées des activités par des intervalles

Scénario : Les combinaisons des valeurs bornes

Pire des cas : durée maximale de chaque activité 24, 27, 29, 45

Solution : ordre 1 | 2 | 3 | 4; ∑ 280

87

Illustration : Optimisation trajets Modèles prédictifs et optimisation Capteurs fournissant des informations de trafic (débit de véhicules, nombre

de véhicules) à intervalles réguliers Estimation de la vitesse pour chaque intervalle de temps

Modèles prédictifs : Vitesse prévisible chaque jour (régression linéaire, k-NN, …)

Regrouper les jours similaires (clustering) Vitesse médiane prévisible

Décision Optimiser les trajets des véhicules avec des durées de trajets dépendent des

horaires

Conséquence sur le problème d’optimisation Propriété FIFO et Plus court chemin

88

Conclusion

Analyse prescriptive Optimisation de la prise de décision Approche opérationnelle de la décision Interactions entre différents paramètres influençant la prise de décision

Processus complexes Différents formalismes de modélisation et d’analyse des modèles

Optimisation « hors ligne », « en ligne », processus centralisé / distribué, …

Différents outils de résolution

Analyse et interprétation des résultats obtenus

89

90

Documents

Introduction à l’Analyse Prescriptive · Plan 1. Introduction 2. Optimisation sous Contraintes 3. Focus sur l’Optimisation Combinatoire 4. Du problème à la solution 5. Contexte