54
Septembre 2004 1 30 ANS DE RECHERCHE OPERATIONNELLE ET D’OPTIMISATION Yves Crama Ecole d’Administration des Affaires

Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Embed Size (px)

Citation preview

Page 1: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 1

30 ANS DE RECHERCHE

OPERATIONNELLEET D’OPTIMISATION

Yves CramaEcole d’Administration des Affaires

Page 2: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 2

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

Page 3: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 3

Intro…

HOMER SIMPSON

A CYBERLAND

Page 4: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 4

Page 5: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 5

Page 6: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 6

Page 7: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 7

Page 8: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 8

Page 9: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 9

Page 10: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 10

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

Page 11: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 11

Vieille question:

Pourquoi certains problèmes mathématiques sont-ils (ou semblent-ils) intrinsèquement plus difficiles à résoudre que d’autres ?

Page 12: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 12

Gödel, Turing, Von Neumann

~1965: Jack Edmonds introduit la notion de « bonne caractérisation » des solutions et d’algorithme «polynomial».

~ 1972: Stephen Cook définit les classes de problèmes P et NP

Page 13: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 13

Idée : distinguer entre les problèmes

1) pour lesquels on peut « facilement » trouver la réponse;

2) pour lesquels on peut « facilement » vérifier qu’une réponse est correcte, lorsqu’elle est connue;

3) les autres….

P et NP

Page 14: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 14

Exemple 1:

Déterminer si l’équation du second degré

5x2 - 4x - 3 = 0possède deux racines distinctes.

Facile à résoudre… (« oui »)

Page 15: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 15

Exemple 2:

Déterminer si

N1 = 281472829095937 est un nombre premier.

Pas très facile à résoudre…La réponse est « non ».

Page 16: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 16

281472829095937 = 131071 2147483647

Preuve:

Page 17: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 17

Exemple 3 (voyageur de commerce):

Déterminer si il existe une tournée de longueur inférieure à 1650 kms visitant 67 grandes villes de Belgique.

Pas très facile à résoudre…La réponse est « oui ».

Page 18: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 18

Preuve: Il suffit que je donne la tournée:

Page 19: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 19

Page 20: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 20

Page 21: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 21

Exemple 3 (suite):

Déterminer si il existe une tournée de longueur inférieure à 1500 kms visitant 67 grandes villes de Belgique.

Pas très facile à résoudre…La réponse est « non ».

Page 22: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 22

Preuve: ????

Page 23: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 23

Problèmes de décision

Un problème de décision est une question qui admet une réponse « Oui » ou « Non ».

Page 24: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 24

P et NP

Un problème de décision est dans P (polynomial) si il peut être résolu par un algorithme efficace, c’est-à-dire un algorithme dont le temps de calcul n'augmente pas trop rapidement (polynomialement) avec la taille du problème à résoudre.

Page 25: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 25

P et NP

Un problème de décision est dans NP (polynomial non déterministe) si il existe une preuve permettant de vérifier efficacement la validité de la réponse lorsque cette réponse est « Oui ».(par exemple, « existe-t-il une tournée de longueur au plus 1650…? »)

Page 26: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 26

P vs NP

Il est à peu près évident que P et NP sont deux classes différentes de problèmes. En fait, P contient par définition des problèmes « faciles » à résoudre, alors que certains problèmes très difficiles sont dans NP.

Page 27: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 27

NP

• problème du voyageur de commerce• programmation linéaire en variables binaires • ordonnancement d’ateliers• localisation d’entrepôts• etc.

Page 28: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 28

Cook (1972) a conjecturé que P n’est pas égal à NP.Mais personne n’a pu le démontrer rigoureusement !!Il s’agit d’un des problèmes ouverts les plus célèbres des maths et de l’informatique théorique.

P = NP ?

Page 29: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 29

P = NP ?

A l’occasion du passage à l’an 2000, le Clay Mathematics Institute a offert 1 million de dollars pour la solution de cette question (et de l’hypothèse de Riemann, etc.)

De là l’intérêt d’Homer Simpson…

Page 30: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 30

Page 31: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 31

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

Page 32: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 32

Programmation linéaire (PL)

Min cj xj

s.c. jaij xj ≤ bi (i = 1,…,m)

Résolu par l’algorithme du simplexe (Dantzig 1947). Archétype du modèle d’optimisation en RO.

Page 33: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 33

Complexité de la PL

Les travaux d’Edmonds, Cook et al. soulèvent de nouvelles questions:

• PL est-il dans NP ?

Oui (quand une solution est connue, il est facile de calculer sa valeur).

Page 34: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 34

Complexité de la PL

• PL est-il dans P ?Oui (parce que la méthode du simplexe est efficace)? Pas évident…Klee et Minty (1972) observent que la méthode du simplexe peut effectuer un nombre exponentiel d'itérations sur certains exemples et n'est donc pas un algorithme polynomial (« efficace »).

Page 35: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 35

Complexité de la PL

• PL est-il dans P ?Cette question a généré un nouvel intérêt pour la PL et un important courant de résultats.

Page 36: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 36

Complexité de la PL

• Khachiyan (1979) propose un algo polynomial pour la PL – mais inefficace en pratique!

• Karmarkar (1984) décrit un algo polynomial et efficace en pratique: méthode de point intérieur.

Page 37: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 37

Retombées algorithmiques

Développement de nouvelles méthodes de points intérieurs, de plus en plus efficaces

Suscite des améliorations spectaculaires de la méthode du simplexe.

Page 38: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 38

État des lieux

• Empiriquement, méthodes du simplexe et de point intérieur sont complémentaires (selon les caractéristiques du problème à résoudre).

Page 39: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 39

État des lieux

De 1987 à 2002, réduction du temps de calcul pour la solution de grands problèmes: facteur de 1.000.000 (1 an 30 sec), dont

- facteur de 1000 dû au « hardware »

- facteur de 1000 dû aux algorithmes

Page 40: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 40

HeuristiquesPuisque certains problèmes ne peuvent pas être résolus en temps polynomial:

Heuristiques: méthodes approchées efficaces

Métaheuristiques: stratégies génériques de développement d’heuristiques

Page 41: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 41

HeuristiquesExemples:

- recuit simulé (simulated annealing)

- exploration tabou (tabu search)

- algorithmes génétiques

- arrondi déterministe ou stochastique, voisinages variables, algorithmes de fourmis, réseaux de neurones, …

Page 42: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 42

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

Page 43: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 43

Tendance lourde:Développement simultané et « symbiotique » de l’informatique (micro-informatique, structures de données, bases de données, systèmes embarqués,…) et de la RO. Intégration croissante des algos d’optimisation dans les systèmes d’information et d’aide à la décision.

Page 44: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 44

Exemples:

- calcul de routes et de tournées (navigateurs GPS, transport routier, Géoroute, …)

- construction d’horaires (écoles, infirmiers, équipes d’ouvriers,…)

- planification de production (affectation aux unités de production, gestion des stocks, ordonnancement, projets,…)

Page 45: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 45

Exemples:

- optimisation des achats (localisation, rabais, …)

- optimisation des recettes de production (pétrochimie, agro-alimentaire,…)

- découpe de matériaux (verre, métal, tissu)

- électronique (conception et production de circuits intégrés)

Page 46: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 46

Exemples:- yield management (optimisation des réservations et pricing pour les compagnies de transport, hôtels, …)- optimisation de portefeuilles financiers- moteurs de recherche Internet- bioinformatique (identification de structures génétiques)- etc.

Page 47: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 47

Un exemple d’intégration:ERP - APS

1970-80: Systèmes MRP

- aide à la gestion des matières (approvisionnement des stocks, lancements de production)

- comportent des fonctionnalités d’optimisation, peu utilisées

Page 48: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 48

Un exemple d’intégration:ERP - APS

1990: Systèmes ERP

- systèmes d’information couvrant les différentes fonctions de l’entreprise (production, stocks, achats, clients, personnel, comptabilité, …)

- peu de capacité d’optimisation

Page 49: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 49

Un exemple d’intégration:ERP - APS

2000: Systèmes APS (Advanced Planning Systems)

- compléments aux ERP

- optimisation de l’allocation des ressources, planification de production, ordonnancement d’ateliers, etc

Page 50: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 50

Un exemple d’intégration:ERP - APS

Rendus possibles grâce à l’adoption des systèmes ERP (dont ils utilisent les bases de données) et à l’amélioration des performances des algorithmes d’optimisation (programmation linéaire, programmation en variables entières, heuristiques, …)

Page 51: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 51

Conclusions

Page 52: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 52

De la théorie à la pratique…

Cheminement:théorie de la complexité (informatique

théorique) algorithmes d’optimisation plus efficaces

(simplexe, point intérieur, heuristiques)

systèmes d’aide à la décision performants (ERP, etc)

Page 53: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 53

The world’s most important invisible profession…

Les algorithmes de RO sont intégrés de plus en plus complètement dans les systèmes d’aide à la décision ils deviennent invisibles pour l’utilisateur (cf. M. Jourdain)C’est probablement une preuve de succès.

Page 54: Septembre 20041 30 ANS DE RECHERCHE OPERATIONNELLE ET DOPTIMISATION Yves Crama Ecole dAdministration des Affaires

Septembre 2004 54