211service.com
La soluzione Simplex
Mentre era seduto in un'aula di tribunale, in attesa di scoprire se sarebbe stato scelto come giurato, Daniel Spielman ha avuto una rivelazione: tutto il lavoro che lui e il collega Shanghua Teng avevano costruito negli ultimi tre anni era un castello di carte. Non dimenticherò mai, dice Spielman, professore associato di matematica. Mentre ero seduto lì ad aspettare, fortunatamente non per essere scelto: ho avuto questa terribile esperienza di rendermi conto che tutto ciò che stavamo facendo era sbagliato. Ho pensato di buttare via il mio programma di ricerca. E in quell'istante le carte crollarono.
La coppia aveva cercato di scoprire un modo per migliorare il metodo del simplesso, uno degli algoritmi più utilizzati al mondo. Consente a molti dei sistemi complessi che diamo per scontati, come le reti di telecomunicazioni e la programmazione di flotte di veicoli per le consegne o voli aerei, di funzionare nel modo più efficiente ed economico possibile. Come nuovo assistente professore, Spielman voleva affermarsi nel mondo della matematica e ottenere una cattedra al MIT lavorando su una grande sfida, ovvero rendere l'algoritmo più semplice, veloce e migliore. Ma dopo quel giorno in tribunale, quando si rese conto che l'applicazione di concetti da un'area non correlata all'algoritmo del simplesso era un vicolo cieco, sapeva che avrebbe dovuto trovare un'altra grande svolta per raggiungere i suoi obiettivi.
Pochi giorni dopo, come una persona la cui casa è stata distrutta da un uragano o da un tornado, Spielman iniziò a salvare ciò che era rimasto della sua rovina di ricerca. Ed è stato allora che ha avuto un'idea davvero grande: anche se il suo lavoro non poteva migliorare il metodo simplex, forse poteva spiegalo . Il metodo era stato sviluppato nel 1947, ma dopo più di 50 anni di analisi nessuno era riuscito a capire perché funzionasse. L'intuizione di Spielman si è rivelata giusta. Dopo altri tre anni di lavoro collaborativo e centinaia di formule matematiche, lui e Teng, professore alla Boston University, possono ora spiegare perché il metodo del simplesso funziona. Ciò può consentire ai cosiddetti esperti di ottimizzazione di risolvere problemi organizzativi ancora più complessi. La spiegazione, chiamata analisi levigata, è già stata citata dalla National Science Foundation come un importante progresso nella tecnologia dell'informazione.
Il percorso verso la scoperta
Spielman e Teng si incontrarono per la prima volta nell'autunno del 1990, quando Spielman, allora studente alla Yale University, visitò la Carnegie Mellon University per tenere un discorso. Teng, un dottorando lì, dice che lui e altri all'università ammiravano questo studente universitario dai capelli lunghi. Aveva già due tesine di qualità PhD. Naturalmente, era uno dei potenziali studenti più apprezzati che tutte le migliori università volevano attirare nei loro programmi di dottorato. Nel 1992, Spielman scelse il MIT. Teng arrivò quello stesso anno come istruttore all'Istituto. Il loro rapporto allievo-insegnante si è presto trasformato in amicizia e poi in una collaborazione che dura da 11 anni.
Nel 1996, dopo diversi anni di collaborazione in un'altra area, il duo ha iniziato a cercare di migliorare il metodo simplex. Il processo di ricerca è molto simile a cercare di trovare un tesoro su un'isola oscura con una piccola torcia, dice Teng. Abbiamo cercato di esplorare quei tanti indizi di speranza. Dan tiene sempre diari di lavoro dettagliati, che segnano sistematicamente le mappe dell'esplorazione.
Dopo tre anni di tale lavoro, Spielman ha avuto la sua realizzazione in tribunale. I due matematici cambiarono il loro obiettivo e attaccarono seriamente il nuovo problema di ricerca.
Teng, che a quel tempo era professore associato presso l'Università dell'Illinois a Urbana-Champaign, tornò in Massachusetts in un anno sabbatico e affittò un appartamento a cinque minuti da Spielman's. Successivamente, entrambi i ricercatori hanno trasformato i loro soggiorni in spazi di lavoro. Teng ha montato una grande lavagna sulla parete del soggiorno. Spielman ne teneva uno dietro il divano.
Da quel momento in poi, il loro lavoro insieme si è svolto a tutte le ore. È stata una di quelle cose in cui mia moglie si è lamentata del fatto che ho visto Shanghua più di quanto l'avessi vista per alcuni anni, dice Spielman. Teng lavorava a tempo pieno presso Akamai a Cambridge, ma si recava nell'appartamento di Spielman quasi tutte le sere dopo il lavoro e nei fine settimana. Stavamo svegli per molte ore, probabilmente fino alle due, lavorando, osserva Spielman. Teng aggiunge, ero come un membro adottivo della famiglia di Dan. Anche la loro gatta, Chloe, si è così abituata alla nostra presenza che si è appollaiata davanti alla lavagna e ci ha guardato con attenzione ogni volta che la sistemavamo. I ricercatori hanno ringraziato Chloe nei ringraziamenti del loro articolo di giornale.
Per tenere traccia del loro lavoro, Spielman ha continuato i suoi diari di lavoro, annotando ogni pensiero ed equazione contenuta nelle lavagne prima di cancellarli. Oggi, una dozzina di questi diari di 200 pagine in formato taccuino sono allineati su uno scaffale nel suo ufficio nell'Edificio 2. Dice che circa il 60 percento delle informazioni contenute nelle riviste è lavoro su analisi levigate. Nel frattempo, Teng ha utilizzato una fotocamera digitale per scattare circa 40 fotografie delle lavagne prima che venissero cancellate.
Finalmente Rispondendo Perché
Il risultato di tutta questa ricerca è stata la risposta alla semplice domanda Perché? Spielman e Teng hanno finalmente capito perché il metodo simplex ha funzionato così bene per tutto questo tempo. Lo hanno fatto sviluppando un nuovo modo di analizzare l'algoritmo.
Fino alla loro scoperta, la maggior parte dei matematici misurava gli algoritmi utilizzando l'analisi del caso peggiore, in cui a un algoritmo vengono dati i dati più difficili e quindi giudicati in base a quanto bene può calcolare con essi. Sarebbe come se qualcuno ti desse il peggior problema possibile sulla lunga divisione che potresti immaginare e poi testasse per vedere se potresti risolverlo e quanto tempo ci vorrebbe. Ma questo non funzionava con il metodo simplex.
Quindi Spielman e Teng hanno trovato un nuovo approccio. Hanno introdotto una certa variabilità nell'analisi del caso peggiore. Invece di usare numeri esatti come input per testare l'algoritmo, hanno permesso l'imprecisione. Ad esempio, se l'input era 1,31, consentivano un input casuale compreso tra 1,29 e 1,33. Hanno scoperto che consentendo l'imprecisione, l'algoritmo del simplesso risolveva sempre il problema in modo efficiente, ed è per questo che ha avuto così tanto successo.
L'idea sembra semplice, ma la matematica che la supporta è complessa. Il primo articolo su rivista di Spielman e Teng sull'argomento, ora in fase di revisione da parte dell'Association for Computing Machinery's Giornale dell'ACM , contiene 80 pagine di equazioni. Non so se così tante persone potrebbero leggere il giornale, dice Spielman. In effetti, scrivere il giornale ha persino confuso Spielman e Teng a volte. Un paio di volte abbiamo semplicemente buttato via ciò che era stato scritto e scritto di nuovo, perché se era complicato per noi, lo sarebbe stato ancora di più per [altre] persone, dice Spielman.
Spielman e Teng hanno presentato le loro scoperte in tutto il mondo ricevendo una risposta entusiasta. Hanno pubblicato un documento per una conferenza nel 2001 e da allora entrambi hanno tenuto presentazioni su invito e discorsi programmatici negli Stati Uniti e in Cina, Turchia, Italia, Svizzera e Danimarca.
Questa analisi levigata è uno sviluppo importante, afferma Michel Goemans, PhD '90, professore di matematica applicata al MIT. E David Johnson, capo del dipartimento Algorithms and Optimization presso AT&T Labs-Research, afferma che [l'analisi smussata] fornisce un ulteriore livello di sicurezza per coloro che utilizzano il metodo simplex.
Spielman dice che non ha tirato fuori la sua lavagna dalla scorsa estate, quando il giornale è stato finalmente finito, ma senza di essa non saremmo mai riusciti a scrivere il giornale. Ora, Spielman raccomanda ai giovani ricercatori di acquistare grandi lavagne bianche come primo passo per fare scoperte. Tuttavia, Teng attribuisce gran parte del loro successo alla mente dinamica di Spielman e al grande gusto nella scelta dei problemi di ricerca. Ha sempre il coraggio di lavorare sul problema aperto più difficile sul campo, dice Teng, e questo potrebbe essere un punto di partenza ancora migliore per ricercatori e curiosi di tutto il mondo.