211service.com
De Simplex-oplossing
Terwijl hij in een rechtszaal zat te wachten om erachter te komen of hij zou worden gekozen voor juryplicht, kreeg Daniel Spielman een openbaring: al het werk dat hij en collega Shanghua Teng de afgelopen drie jaar hadden opgebouwd, was een kaartenhuis. Ik zal het nooit vergeten, zegt Spielman, universitair hoofddocent wiskunde. Terwijl ik daar zat te wachten - gelukkig niet om uitgekozen te worden - ik had de vreselijke ervaring dat ik me realiseerde dat alles wat we hadden gedaan verkeerd was. Ik dacht erover om mijn onderzoeksprogramma weg te gooien. En op dat moment stortten de kaarten in.
Het paar had geprobeerd een manier te vinden om de simplex-methode, een van de meest gebruikte algoritmen ter wereld, te verbeteren. Het zorgt ervoor dat veel van de complexe systemen die we als vanzelfsprekend beschouwen, zoals telecommunicatienetwerken en planning voor wagenparken van bestelwagens of vluchten van luchtvaartmaatschappijen, zo efficiënt en goedkoop mogelijk kunnen werken. Als nieuwe assistent-professor wilde Spielman zich vestigen in de wereld van de wiskunde en een vaste aanstelling krijgen bij het MIT door te werken aan een grote uitdaging, namelijk het algoritme eenvoudiger, sneller en beter maken. Maar na die dag in het gerechtsgebouw, toen hij zich realiseerde dat het toepassen van concepten uit een niet-gerelateerd gebied op het simplex-algoritme een doodlopende weg was, wist hij dat hij een nieuwe grote doorbraak zou moeten vinden om zijn doelen te bereiken.
Een paar dagen later begon Spielman, als iemand wiens huis is verwoest door een orkaan of tornado, te redden wat er over was van zijn onderzoeksruïne. En toen kwam het echt grote idee: hoewel zijn werk de simplex-methode niet kon verbeteren, zou het dat misschien wel kunnen leg uit . De methode was ontwikkeld in 1947, maar na meer dan 50 jaar analyse had niemand kunnen achterhalen waarom het werkte. Spielmans voorgevoel bleek te kloppen. Na nog eens drie jaar samenwerken en honderden wiskundige formules, kunnen hij en Teng, een professor aan de Boston University, nu uitleggen waarom de simplex-methode werkt. Hierdoor kunnen de zogenaamde optimalisatie-experts mogelijk nog complexere organisatorische problemen oplossen. De verklaring, afgevlakte analyse genoemd, is al door de National Science Foundation aangehaald als een belangrijke vooruitgang in de informatietechnologie.
Het pad naar ontdekking
Spielman en Teng ontmoetten elkaar voor het eerst in de herfst van 1990, toen Spielman, toen een student aan de Yale University, de Carnegie Mellon University bezocht om een toespraak te houden. Teng, een promovendus daar, zegt dat hij en anderen op de universiteit bewondering hadden voor deze langharige studente. Hij had al twee papers van PhD-kwaliteit. Natuurlijk was hij een van de meest gewaardeerde toekomstige studenten die alle topuniversiteiten wilden aantrekken voor hun PhD-programma's. In 1992 koos Spielman voor MIT. Teng arriveerde datzelfde jaar als instructeur bij het Instituut. Hun relatie student-leraar werd al snel vriendschap en vervolgens een samenwerking die 11 jaar heeft geduurd.
In 1996, na enkele jaren van samenwerking op een ander gebied, begon het duo de simplex-methode te verbeteren. Het proces van onderzoek lijkt veel op het zoeken naar schatten op een donker eiland met een kleine zaklamp, zegt Teng. We hebben geprobeerd die vele hoopvolle aanwijzingen te onderzoeken. Dan houdt altijd gedetailleerde werkjournalen bij, die systematisch de kaarten van de verkenning markeren.
Na drie jaar van dergelijk werk had Spielman zijn rechtszaalrealisatie. De twee wiskundigen veranderden hun doel en vielen het nieuwe onderzoeksprobleem serieus aan.
Teng, die toen universitair hoofddocent was aan de Universiteit van Illinois in Urbana-Champaign, verhuisde op sabbatical terug naar Massachusetts en huurde een appartement op vijf minuten afstand van Spielman's. Daarna toverden beide onderzoekers hun woonkamer om tot werkruimte. Teng monteerde een groot whiteboard aan de muur van zijn woonkamer. Spielman bewaarde er een achter zijn bank.
Vanaf dat moment was hun samenwerking op alle uren plaats. Het was een van die dingen waar mijn vrouw klaagde dat ik Shanghua een paar jaar meer zag dan dat ik haar zag, zegt Spielman. Teng werkte fulltime bij Akamai in Cambridge, maar hij ging bijna elke avond na het werk en in het weekend naar het appartement van Spielman. We zouden vele uren opblijven, waarschijnlijk tot twee uur, aan het werk, merkt Spielman op. Teng voegt eraan toe: ik was als een geadopteerd lid van Dans familie. Zelfs hun kat, Chloe, raakte zo gewend aan onze aanwezigheid dat ze voor het whiteboard ging zitten en aandachtig toekeek wanneer we het opstelden. De onderzoekers bedankten Chloe in de dankbetuigingen van hun tijdschriftartikel.
Om hun werk bij te houden, ging Spielman door met zijn werkdagboeken, waarbij hij elke gedachte en vergelijking op de whiteboards opschreef voordat hij ze uitwist. Tegenwoordig staan een dozijn van deze 200 pagina's tellende tijdschriften op notebookformaat op een boekenplank in zijn kantoor in Gebouw 2. Hij zegt dat ongeveer 60 procent van de informatie die de tijdschriften bevatten werk is aan een soepele analyse. Ondertussen gebruikte Teng een digitale camera om ongeveer 40 foto's van de whiteboards te maken voordat ze werden gewist.
Eindelijk een antwoord geven op waarom
Het resultaat van al dit onderzoek was het antwoord op de simpele vraag Waarom? Spielman en Teng kwamen er eindelijk achter waarom de simplex-methode al die tijd zo goed heeft gewerkt. Dat deden ze door een nieuwe manier te ontwikkelen om het algoritme te analyseren.
Tot hun ontdekking maten de meeste wiskundigen algoritmen met behulp van worst-case analyse, waarbij een algoritme de moeilijkste gegevens krijgt en vervolgens beoordeeld hoe goed het ermee kan rekenen. Het zou zijn alsof iemand je het ergst mogelijke lange-delingsprobleem geeft dat je je kunt voorstellen en vervolgens testte om te zien of je het zou kunnen oplossen en hoe lang het zou duren. Maar dit werkte gewoon niet met de simplex-methode.
Dus vonden Spielman en Teng een nieuwe aanpak. Ze introduceerden enige variabiliteit in de worst-case-analyse. In plaats van exacte getallen als invoer te gebruiken om het algoritme te testen, lieten ze onnauwkeurigheid toe. Als de invoer bijvoorbeeld 1,31 was, stond een willekeurige invoer tussen 1,29 en 1,33 toe. Ze ontdekten dat door onnauwkeurigheid toe te staan, het simplex-algoritme het probleem altijd efficiënt oploste, en daarom is het zo succesvol geweest.
Het idee klinkt eenvoudig, maar de wiskunde die het ondersteunt is complex. Spielman en Teng's eerste tijdschriftartikel over dit onderwerp, nu beoordeeld door de Association for Computing Machinery's Tijdschrift van de ACM , bevat 80 pagina's met vergelijkingen. Ik weet niet of er zoveel mensen door de krant zouden kunnen lopen, zegt Spielman. Het schrijven van de krant bracht zelfs Spielman en Teng af en toe in verwarring. Een paar keer gooiden we gewoon weg wat er was geschreven en schreven opnieuw, want als het ingewikkeld was voor ons, zou het nog ingewikkelder zijn voor [andere] mensen, zegt Spielman.
Spielman en Teng hebben hun bevindingen over de hele wereld gepresenteerd met enthousiaste reacties. Ze publiceerden in 2001 een conferentiepaper en sindsdien hebben ze allebei presentaties op uitnodiging en keynote-toespraken gegeven in de Verenigde Staten en in China, Turkije, Italië, Zwitserland en Denemarken.
Deze gestroomlijnde analyse is een belangrijke ontwikkeling, zegt Michel Goemans, PhD '90, een MIT-hoogleraar toegepaste wiskunde. En David Johnson, hoofd van de afdeling Algorithms and Optimization bij AT&T Labs-Research, zegt: [Gestroomlijnde analyse] biedt een extra niveau van vertrouwen voor degenen die de simplex-methode gebruiken.
Spielman zegt dat hij zijn whiteboard niet meer tevoorschijn heeft gehaald sinds afgelopen zomer, toen het dagboekpapier eindelijk af was, maar zonder dat was het ons nooit gelukt om het papier te schrijven. Nu raadt Spielman jonge onderzoekers aan om grote whiteboards te kopen als een goede eerste stap op weg naar doorbraken. Teng schrijft echter een groot deel van hun succes toe aan Spielmans dynamische geest en geweldige smaak bij het kiezen van onderzoeksproblemen. Hij heeft altijd de moed om aan het moeilijkste open probleem in het veld te werken, zegt Teng, en dat is misschien een nog beter uitgangspunt voor onderzoekers en nieuwsgierige mensen overal.