211service.com
La solution simplex
Alors qu'il était assis dans une salle d'audience, attendant de savoir s'il serait choisi pour faire partie du jury, Daniel Spielman a eu une révélation : tout le travail que lui et son collègue Shanghua Teng avaient construit au cours des trois dernières années était un château de cartes. Je n'oublierai jamais, dit Spielman, professeur agrégé de mathématiques. Alors que j'étais assis là à attendre-heureusement ne pas d'être choisi - j'ai eu cette horrible expérience de réaliser que tout ce que nous avions fait était mal. J'ai pensé à jeter mon programme de recherche. Et à cet instant, les cartes se sont effondrées.
La paire avait essayé de découvrir un moyen d'améliorer la méthode du simplexe, l'un des algorithmes les plus utilisés au monde. Il permet à de nombreux systèmes complexes que nous tenons pour acquis, tels que les réseaux de télécommunications et la planification des flottes de véhicules de livraison ou des vols aériens, de fonctionner de manière aussi efficace et économique que possible. En tant que nouveau professeur assistant, Spielman voulait s'établir dans le monde des mathématiques et obtenir un poste au MIT en travaillant sur un grand défi, à savoir rendre l'algorithme plus simple, plus rapide et meilleur. Mais après cette journée au palais de justice, lorsqu'il s'est rendu compte que l'application de concepts d'un domaine non lié à l'algorithme du simplex était une impasse, il savait qu'il devrait trouver une autre grande avancée pour atteindre ses objectifs.
Quelques jours plus tard, comme une personne dont la maison a été détruite par un ouragan ou une tornade, Spielman a commencé à récupérer ce qui restait de sa ruine de recherche. Et c'est à ce moment-là que la très grande idée a germé : bien que son travail n'ait pas pu améliorer la méthode du simplexe, il pourrait peut-être Explique le . La méthode avait été développée en 1947, mais après plus de 50 ans d'analyse, personne n'avait pu comprendre pourquoi cela fonctionnait. L'intuition de Spielman s'est avérée juste. Après trois autres années de travail collaboratif et des centaines de formules mathématiques, lui et Teng, professeur à l'Université de Boston, peuvent maintenant expliquer pourquoi la méthode du simplexe fonctionne. Cela peut permettre aux experts en optimisation de résoudre des problèmes d'organisation encore plus complexes. Déjà, l'explication, appelée analyse lissée, a été citée par la National Science Foundation comme une avancée majeure dans les technologies de l'information.
Le chemin de la découverte
Spielman et Teng se sont rencontrés pour la première fois à l'automne 1990, lorsque Spielman, alors étudiant de premier cycle à l'Université de Yale, s'est rendu à l'Université Carnegie Mellon pour prononcer un discours. Teng, un doctorant là-bas, dit que lui et d'autres à l'université admiraient ce jeune universitaire aux cheveux longs. Il avait déjà deux articles de qualité PhD. Naturellement, il était l'un des étudiants potentiels les plus prisés que toutes les meilleures universités voulaient attirer dans leurs programmes de doctorat. En 1992, Spielman a choisi le MIT. Teng est arrivé la même année en tant qu'instructeur à l'Institut. Leur relation élève-professeur est vite devenue une amitié puis une collaboration qui a duré 11 ans.
En 1996, après plusieurs années de collaboration dans un autre domaine, le duo a commencé à chercher à améliorer la méthode simplex. Le processus de recherche ressemble beaucoup à essayer de trouver un trésor sur une île sombre avec une petite lampe de poche, explique Teng. Nous avons essayé d'explorer ces nombreuses pistes prometteuses. Dan tient toujours des journaux de travail détaillés, qui marquent systématiquement les cartes de l'exploration.
Après trois ans d'un tel travail, Spielman a eu sa réalisation en salle d'audience. Les deux mathématiciens changèrent d'objectif et s'attaquèrent sérieusement au nouveau problème de recherche.
Teng, qui était alors professeur agrégé à l'Université de l'Illinois à Urbana-Champaign, est retourné dans le Massachusetts en congé sabbatique et a loué un appartement à cinq minutes de Spielman. Après cela, les deux chercheurs ont transformé leurs salons en espaces de travail. Teng a monté un grand tableau blanc sur le mur de son salon. Spielman en gardait un rangé derrière son canapé.
Dès lors, leur travail en commun se déroule à toute heure. C'était l'une de ces choses où ma femme se plaignait que je voyais Shanghua plus que je ne la voyais pendant quelques années, dit Spielman. Teng travaillait à temps plein chez Akamai à Cambridge, mais il se rendait à l'appartement de Spielman presque tous les soirs après le travail et le week-end. Nous resterions debout pendant de nombreuses heures, probablement jusqu'à deux heures, à travailler, note Spielman. Teng ajoute, j'étais comme un membre adopté de la famille de Dan. Même leur chat, Chloé, s'est tellement habitué à notre présence qu'elle se perchait devant le tableau blanc et regardait attentivement chaque fois que nous l'installions. Les chercheurs ont remercié Chloé dans les remerciements de leur article de journal.
Pour garder une trace de leur travail, Spielman a continué ses journaux de travail, écrivant chaque pensée et équation que les tableaux blancs contenaient avant de les effacer. Aujourd'hui, une douzaine de ces journaux de 200 pages de la taille d'un cahier s'alignent sur une étagère de son bureau du bâtiment 2. Il dit qu'environ 60 pour cent des informations que contiennent les journaux sont des travaux d'analyse lissée. Pendant ce temps, Teng a utilisé un appareil photo numérique pour prendre environ 40 photographies des tableaux blancs avant qu'ils ne soient effacés.
enfin répondre pourquoi
Le résultat de toutes ces recherches a été la réponse à la simple question Pourquoi ? Spielman et Teng ont finalement compris pourquoi la méthode du simplexe a si bien fonctionné pendant tout ce temps. Ils l'ont fait en développant une nouvelle façon d'analyser l'algorithme.
Jusqu'à leur découverte, la plupart des mathématiciens mesuraient les algorithmes en utilisant l'analyse du pire des cas, dans laquelle un algorithme recevait les données les plus difficiles, puis était jugé sur la façon dont il pouvait calculer avec. Ce serait comme si quelqu'un vous remettait le pire problème de longue division possible que vous puissiez imaginer, puis testé pour voir si vous pouviez le résoudre et combien de temps cela prendrait. Mais cela ne fonctionnait tout simplement pas avec la méthode simplex.
Spielman et Teng ont donc trouvé une nouvelle approche. Ils ont introduit une certaine variabilité dans l'analyse du pire des cas. Au lieu d'utiliser des nombres exacts comme entrées pour tester l'algorithme, ils ont permis l'imprécision. Par exemple, si l'entrée était de 1,31, ils autorisaient une entrée aléatoire entre 1,29 et 1,33. Ils ont découvert qu'en tenant compte de l'imprécision, l'algorithme du simplexe résolvait toujours efficacement le problème, et c'est pourquoi il a eu tant de succès.
L'idée semble simple, mais les mathématiques qui la soutiennent sont complexes. Le premier article de journal de Spielman et Teng sur le sujet, actuellement en cours d'examen par l'Association for Computing Machinery's Journal de l'ACM , contient 80 pages d'équations. Je ne sais pas si autant de personnes pourraient parcourir le journal, dit Spielman. En fait, écrire le journal a même parfois confondu Spielman et Teng. À quelques reprises, nous avons juste jeté ce qui était écrit et écrit à nouveau, parce que si c'était compliqué pour nous, ça allait être encore plus compliqué pour [d'autres] personnes, dit Spielman.
Spielman et Teng ont présenté leurs découvertes dans le monde entier à une réponse enthousiaste. Ils ont publié un document de conférence en 2001, et depuis lors, tous deux ont donné des présentations invitées et des allocutions à travers les États-Unis et en Chine, en Turquie, en Italie, en Suisse et au Danemark.
Cette analyse lissée est un développement important, déclare Michel Goemans, PhD '90, professeur de mathématiques appliquées au MIT. Et David Johnson, chef du département Algorithmes et optimisation chez AT&T Labs-Research, déclare que [L'analyse lissée] offre un niveau de confiance supplémentaire à ceux qui utilisent la méthode du simplexe.
Spielman dit qu'il n'a pas sorti son tableau blanc depuis l'été dernier, lorsque le papier du journal était enfin terminé, mais sans lui, nous n'aurions jamais réussi à écrire le papier. Maintenant, Spielman recommande que les jeunes chercheurs achètent de grands tableaux blancs comme un bon premier pas vers des percées. Cependant, Teng attribue une grande partie de leur succès à l'esprit dynamique de Spielman et à son bon goût dans le choix des problèmes de recherche. Il a toujours le courage de travailler sur le problème ouvert le plus difficile sur le terrain, dit Teng, et cela pourrait être un meilleur point de départ pour les chercheurs et les curieux du monde entier.