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

Septembre 2004 1

30 ANS DE RECHERCHE

OPERATIONNELLEET D’OPTIMISATION

Yves CramaEcole d’Administration des Affaires

Septembre 2004 2

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

Septembre 2004 3

Intro…

HOMER SIMPSON

A CYBERLAND

Septembre 2004 4

Septembre 2004 5

Septembre 2004 6

Septembre 2004 7

Septembre 2004 8

Septembre 2004 9

Septembre 2004 10

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

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 ?

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

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

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 »)

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 ».

Septembre 2004 16

281472829095937 = 131071 2147483647

Preuve:

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 ».

Septembre 2004 18

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

Septembre 2004 19

Septembre 2004 20

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 ».

Septembre 2004 22

Preuve: ????

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 ».

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.

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…? »)

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.

Septembre 2004 27

NP

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

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 ?

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…

Septembre 2004 30

Septembre 2004 31

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

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.

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).

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 »).

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.

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.

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.

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).

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

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

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, …

Septembre 2004 42

PLAN:

1. Quelques notions de complexité algorithmique

2. Impact en optimisation

3. Retombées industrielles

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.

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,…)

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)

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.

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

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

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

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, …)

Septembre 2004 51

Conclusions

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)

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.

Septembre 2004 54