Premier jet d'intro...
La recherche opérationnelle peut se définir comme étant la science de l'optimisation. Bien qu'appelée par ce nom seulement depuis une cinquantaine d'année suite à son utilisation militaire, deux grands faits antérieurs permettent néanmoins de l'appeler par ce nom : Archimède tout d'abord qui l'utilisa pour optimiser (a) le siège de Syracuse contre les romains au III$^e$S av notre ère ainsi que, plus proche de nous, Gaspard Monge, qui, au XVIII$^e$S l'utilisa pour des problèmes de remblais et de travaux publics. Mais la vraie première publication scientifique, en latin, est l'œuvre de Leonhard Euler qui, en 1736, publie [1] "Solutio problematis ad geometriam situs pertinentis", y démontrant que le problème des 7 ponts de Kœnigsberg (b) n'a pas de solution.
C'est Robert Watson-Watt (avec Frederick Lanchester, Patrick Blackett and Frank Yates), un spécialiste du radar pendant la deuxième guerre mondiale qui revendiqua la paternité de l'appellation "Recherche Opérationnelle" du fait des différents équipements entre les nations alliées qui souhaitaient optimiser au maximum la synthèse des différentes informations : la récupération, la diffusion, la localisation de batiments ennemis afin de répartir au mieux les moyens de les détruire. Il s'agissait alors de faire de la recherche (de navires) afin d'être au maximum opérationnel.
La Recherche Opérationnelle, telle qu'ainsi définie et pensée aurait pu s'arrêter là : la théorie n'étant pas une fin en soi, le calcul des solutions requérait rapidement de lourds moyens, indisponibles à l'époque. Néanmoins, un premier enseignement fut créé au MIT en 1948, le premier séminaire au Case Institut of Technologie en 1951, simultanément avec l'ouverture de cours en Angleterre ainsi qu'en France. Le premier journal, OR society of America, parut en 1952, avec l'AFCET, son homologue et premier journal français dédié à la recherche opérationnelle. Depuis, de nombreux journaux lui sont particulièrement dédiée, et les enseignements s'il se font dans le supérieur, sont présents partout dans le monde.
De nos jours, les ordinateurs ont considérablement progressé. De fait, des problèmes de taille de plus en plus conséquente peuvent être résolus.
L'optimisation combinatoire [2] occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d'une part par la grande difficulté des problèmes d'optimisation [3] et d'autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d'un problème d'optimisation combinatoire [4]. Bien que ces derniers soient souvent faciles à définir, ils sont généralement difficiles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent donc pas à ce jour de solution algorithmique (c) efficace valable pour toutes les données [5].
Cependant, si nous précisons la mission de la recherche opérationnelle, nous pouvons indiquer alors qu'elle est la science permettant la résolution de problèmes du monde réel, qui auront été préalablement modélisés mathématiquement et dont la solution peut être satisfaisante sur d'autres critères que la seule exactitude ou optimalité. Ces problèmes sont à la base des problèmes de décisions. Aussi, les modèles mathématiques dont nous parlons peuvent être définis comme possédant des variables de décision, qui sont les inconnues à déterminer pour la solution du modèle, des contraintes qui représentent les limites physiques du système, une fonction objectif à qualifier et une solution qui représente l'instance prise par les variables qui satisfont alors toutes les données du modèle, et qui maximise ou minimise la fonction d'objectif.
D'une façon générale, nous pouvons considérer la recherche opérationnelle comme l'application de stratégie ou de réflexion scientifiques à la prise de décision. Fondamentalement, la philosophie de la recherche opérationnelle tient au fait qu'une décision doit être prise, que l'emploi d'une méthode quantitative (explicite) mènera en moyenne à de meilleures décisions que ne l'aurait fait tout autre approche (implicite, énumérative) y compris par des décideurs humains. Cependant, bien que la recherche opérationnelle soit imparfaite, elle donne bien souvent la meilleure solution(d) compte-tenu des contraintes financières, matérielles et temporelles implicites.
Parmi ces problèmes fortement combinatoires, il en est un, celui communément appelé "problème du sac à dos multicontraint". Ce mémoire concerne donc une variante de résolution de ce problème. Sa NP-complétude connue, nous pouvons déjà indiquer qu'il ne s'agit pas d'une méthode exacte.
Dans une première partie, nous commençons par présenter la problématique, sa formulation, découverte à partir d'exemples, des résultats connus de complexité NP-complétude et les différents schémas d'approximation). Enfin, nous terminerons ce premier chapitre par un court récapitulatif historique des études menées sur ce problème.
Dans un deuxième temps, nous prenons un peu de recul et nous présentons les différents moyens existants pour s'attaquer à la résolution de problèmes en optimisation combinatoire. Dans une première partie, nous présentons les algorithmes à garantie de performances, avec notamment les algorithmes exacts, puis dans une deuxième partie, nous développons la notion de solution approchée sans garantie de performance avec par exemple le monde des heuristiques et autres métaheuristiques.
Enfin, dans un troisième et dernier chapitre, nous abordons le travail proprement dit: Tout d'abord, nous présentons succinctement le travail de Babacar Tionghane sur lequel nous nous sommes appuyés. Puis, l'extension, en terme de classe de problèmes de sacs à dos qui fut proposé. Un mot sur les nouvelles instances. Enfin, le cœur même du travail avec l'amélioration puis l'hybridation de schéma de sous gradient avec des métaheuristiques. Une variante dérivée de la VNS qui fait une large part à l'hyperdiversification est également proposée. Le chapitre se termine évidemment par l'aggrégation de résultats.
C'est Robert Watson-Watt (avec Frederick Lanchester, Patrick Blackett and Frank Yates), un spécialiste du radar pendant la deuxième guerre mondiale qui revendiqua la paternité de l'appellation "Recherche Opérationnelle" du fait des différents équipements entre les nations alliées qui souhaitaient optimiser au maximum la synthèse des différentes informations : la récupération, la diffusion, la localisation de batiments ennemis afin de répartir au mieux les moyens de les détruire. Il s'agissait alors de faire de la recherche (de navires) afin d'être au maximum opérationnel.
La Recherche Opérationnelle, telle qu'ainsi définie et pensée aurait pu s'arrêter là : la théorie n'étant pas une fin en soi, le calcul des solutions requérait rapidement de lourds moyens, indisponibles à l'époque. Néanmoins, un premier enseignement fut créé au MIT en 1948, le premier séminaire au Case Institut of Technologie en 1951, simultanément avec l'ouverture de cours en Angleterre ainsi qu'en France. Le premier journal, OR society of America, parut en 1952, avec l'AFCET, son homologue et premier journal français dédié à la recherche opérationnelle. Depuis, de nombreux journaux lui sont particulièrement dédiée, et les enseignements s'il se font dans le supérieur, sont présents partout dans le monde.
De nos jours, les ordinateurs ont considérablement progressé. De fait, des problèmes de taille de plus en plus conséquente peuvent être résolus.
L'optimisation combinatoire [2] occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d'une part par la grande difficulté des problèmes d'optimisation [3] et d'autre part par de nombreuses applications pratiques pouvant être formulées sous la forme d'un problème d'optimisation combinatoire [4]. Bien que ces derniers soient souvent faciles à définir, ils sont généralement difficiles à résoudre. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP-difficiles et ne possèdent donc pas à ce jour de solution algorithmique (c) efficace valable pour toutes les données [5].
Cependant, si nous précisons la mission de la recherche opérationnelle, nous pouvons indiquer alors qu'elle est la science permettant la résolution de problèmes du monde réel, qui auront été préalablement modélisés mathématiquement et dont la solution peut être satisfaisante sur d'autres critères que la seule exactitude ou optimalité. Ces problèmes sont à la base des problèmes de décisions. Aussi, les modèles mathématiques dont nous parlons peuvent être définis comme possédant des variables de décision, qui sont les inconnues à déterminer pour la solution du modèle, des contraintes qui représentent les limites physiques du système, une fonction objectif à qualifier et une solution qui représente l'instance prise par les variables qui satisfont alors toutes les données du modèle, et qui maximise ou minimise la fonction d'objectif.
D'une façon générale, nous pouvons considérer la recherche opérationnelle comme l'application de stratégie ou de réflexion scientifiques à la prise de décision. Fondamentalement, la philosophie de la recherche opérationnelle tient au fait qu'une décision doit être prise, que l'emploi d'une méthode quantitative (explicite) mènera en moyenne à de meilleures décisions que ne l'aurait fait tout autre approche (implicite, énumérative) y compris par des décideurs humains. Cependant, bien que la recherche opérationnelle soit imparfaite, elle donne bien souvent la meilleure solution(d) compte-tenu des contraintes financières, matérielles et temporelles implicites.
Parmi ces problèmes fortement combinatoires, il en est un, celui communément appelé "problème du sac à dos multicontraint". Ce mémoire concerne donc une variante de résolution de ce problème. Sa NP-complétude connue, nous pouvons déjà indiquer qu'il ne s'agit pas d'une méthode exacte.
Dans une première partie, nous commençons par présenter la problématique, sa formulation, découverte à partir d'exemples, des résultats connus de complexité NP-complétude et les différents schémas d'approximation). Enfin, nous terminerons ce premier chapitre par un court récapitulatif historique des études menées sur ce problème.
Dans un deuxième temps, nous prenons un peu de recul et nous présentons les différents moyens existants pour s'attaquer à la résolution de problèmes en optimisation combinatoire. Dans une première partie, nous présentons les algorithmes à garantie de performances, avec notamment les algorithmes exacts, puis dans une deuxième partie, nous développons la notion de solution approchée sans garantie de performance avec par exemple le monde des heuristiques et autres métaheuristiques.
Enfin, dans un troisième et dernier chapitre, nous abordons le travail proprement dit: Tout d'abord, nous présentons succinctement le travail de Babacar Tionghane sur lequel nous nous sommes appuyés. Puis, l'extension, en terme de classe de problèmes de sacs à dos qui fut proposé. Un mot sur les nouvelles instances. Enfin, le cœur même du travail avec l'amélioration puis l'hybridation de schéma de sous gradient avec des métaheuristiques. Une variante dérivée de la VNS qui fait une large part à l'hyperdiversification est également proposée. Le chapitre se termine évidemment par l'aggrégation de résultats.
(a) : Probablement avec plus de bon sens qu'à l'aide d'une vraie et rigoureuse formulation
(b) : Aujourd'hui Kalilingrad, enclave russe
(c) : Dans l'encyclopédie Britannica, le mot "algorithme" dérive d'une transformation latine "Algoritmi de numero Indorum" du mathématicien musulman du IX$^e$S, Abu Ja'far ibn Muhammad Musa Al-Kwarizmi qui y écrivait: "Al-Khwarizmi concernant l'Art Hindou du comptage".
(d) : Sans que celle ci soit obligatoirement la solution mathématique optimale de l'instance.
[1] : L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitanae, 8 (1736), 128-140
[2] : Jin-Kao Hao, Philippe Galinier, Michel Habib, Méthaheuristiques pour l'optimisation combinatoire et la Seletion sous contraintes. Revue d'Intelligence Artificielle Vol : No. 1999
[3] : C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization - algorithms and complexity. Prentice Hall, 1982.
[4] : C.C. Ribeiro, N.Maculan (Eds.), Applications of combinatorial optimization. Annals of Operations Research 50, 1994.
[5] : M.R. Garey, D.S. Johnson , Computers and intractability : a guide to the theory of NP-completeness, W.H. Freeman and Company, New York, 1979.
(b) : Aujourd'hui Kalilingrad, enclave russe
(c) : Dans l'encyclopédie Britannica, le mot "algorithme" dérive d'une transformation latine "Algoritmi de numero Indorum" du mathématicien musulman du IX$^e$S, Abu Ja'far ibn Muhammad Musa Al-Kwarizmi qui y écrivait: "Al-Khwarizmi concernant l'Art Hindou du comptage".
(d) : Sans que celle ci soit obligatoirement la solution mathématique optimale de l'instance.
[1] : L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitanae, 8 (1736), 128-140
[2] : Jin-Kao Hao, Philippe Galinier, Michel Habib, Méthaheuristiques pour l'optimisation combinatoire et la Seletion sous contraintes. Revue d'Intelligence Artificielle Vol : No. 1999
[3] : C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization - algorithms and complexity. Prentice Hall, 1982.
[4] : C.C. Ribeiro, N.Maculan (Eds.), Applications of combinatorial optimization. Annals of Operations Research 50, 1994.
[5] : M.R. Garey, D.S. Johnson , Computers and intractability : a guide to the theory of NP-completeness, W.H. Freeman and Company, New York, 1979.
Posté par Vicnent | 6:49 PM
1 Comments:
Merci, très intéressant et clairement exprimé pour une personne non spécialiste de maths comme moi.
De l'ensemble c'est cette phrase que je retiendrai et dont je pourrais être amenée à me servir plus tard (Copyright Vincent of course):
* D'une façon générale, nous pouvons considérer la recherche opérationnelle comme l'application de stratégie ou de réflexion scientifiques à la prise de décision. *
Hum, au cas où ce soit un abstract avant l'heure, corrige déjà ds la note b) "KaliNingrad".
A bientôt, :)
Enregistrer un commentaire
<< Home