211service.com
Simplexní řešení
Zatímco Daniel Spielman seděl v soudní síni a čekal, zda bude vybrán do funkce poroty, došlo k odhalení – veškerá práce, kterou on a kolega Shanghua Teng za poslední tři roky vybudovali, byl domeček z karet. Nikdy nezapomenu, říká Spielman, docent matematiky. Jak jsem tam seděl a čekal - naštěstí ne být vybrán – měl jsem ten hrozný zážitek, když jsem si uvědomil, že všechno, co jsme dělali, bylo špatné. Myslel jsem, že svůj výzkumný program zahodím. A v tu chvíli se karty zhroutily.
Dvojice se snažila objevit způsob, jak zlepšit simplexovou metodu, jeden z nejrozšířenějších algoritmů na světě. Umožňuje mnoha komplexním systémům, které považujeme za samozřejmost – jako jsou telekomunikační sítě a plánování pro flotily doručovacích vozidel nebo letů leteckých společností – pracovat co nejefektivněji a levně. Jako nový odborný asistent se Spielman chtěl prosadit ve světě matematiky a získat držbu na MIT tím, že pracoval na velké výzvě, konkrétně na zjednodušení, rychlejším a lepším algoritmu. Ale po tom dni u soudu, když si uvědomil, že použití konceptů z nesouvisející oblasti na simplexní algoritmus je slepá ulička, věděl, že bude muset najít další velký průlom, aby dosáhl svých cílů.
O několik dní později, jako člověk, jehož domov zničil hurikán nebo tornádo, začal Spielman zachraňovat to, co zbylo z jeho trosek výzkumu. A tehdy zasáhla opravdu velká myšlenka: ačkoli jeho práce nedokázala vylepšit simplexovou metodu, možná ano vysvětli to . Metoda byla vyvinuta v roce 1947, ale po více než 50 letech analýz nebyl nikdo schopen zjistit, proč funguje. Spielmanovo tušení se ukázalo jako správné. Po dalších třech letech společné práce a stovkách matematických vzorců nyní on a Teng, profesor z Bostonské univerzity, mohou vysvětlit, proč simplexová metoda funguje. To může umožnit takzvaným optimalizačním expertům řešit ještě složitější organizační problémy. Vysvětlení, nazývané vyhlazená analýza, již bylo citováno Národní vědeckou nadací jako významný pokrok v informační technologii.
Cesta k objevu
Spielman a Teng se poprvé setkali na podzim roku 1990, kdy Spielman, tehdy vysokoškolák na Yale University, navštívil Carnegie Mellon University, aby přednesl projev. Teng, tamní doktorand, říká, že on a další na univerzitě obdivovali tohoto dlouhovlasého juniora. Měl již dvě práce v kvalitě PhD. Přirozeně byl jedním z nejoceňovanějších potenciálních studentů, které všechny špičkové univerzity chtěly přilákat do svých doktorandských programů. V roce 1992 si Spielman vybral MIT. Teng přišel téhož roku jako instruktor v Institutu. Z jejich vztahu mezi studentem a učitelem se brzy stalo přátelství a následně spolupráce, která trvá již 11 let.
V roce 1996, po několika letech společné práce v jiné oblasti, se duo začalo snažit vylepšit simplexovou metodu. Proces výzkumu je hodně podobný pokusu najít poklad na tmavém ostrově s malou baterkou, říká Teng. Snažili jsme se prozkoumat těch mnoho nadějných vodítek. Dan si vždy vede podrobné pracovní deníky, které systematicky označují mapy průzkumu.
Po třech letech takové práce se Spielman dočkal realizace soudní síně. Dva matematici změnili svůj cíl a vážně zaútočili na nový výzkumný problém.
Teng, který byl v té době docentem na Illinoiské univerzitě v Urbana-Champaign, se o volnu přestěhoval zpět do Massachusetts a pronajal si byt pět minut od Spielman's. Poté oba výzkumníci proměnili své obývací pokoje v pracovní prostory. Teng si na stěnu obývacího pokoje připevnil velkou bílou tabuli. Spielman měl jeden uložený za pohovkou.
Od té doby jejich společná práce probíhala ve všech hodinách. Byla to jedna z věcí, kdy si moje žena stěžovala, že jsem viděl Shanghuu více než několik let, říká Spielman. Teng pracoval na plný úvazek v Akamai v Cambridge, ale do Spielmanova bytu chodil téměř každou noc po práci ao víkendech. Zůstali bychom vzhůru mnoho hodin, pravděpodobně do dvou, pracovali, poznamenává Spielman. Teng dodává, že jsem byl jako adoptovaný člen Danovy rodiny. Dokonce i jejich kočka Chloe si na naši přítomnost tak zvykla, že seděla před tabulí a pozorně sledovala, kdykoli jsme ji postavili. Vědci poděkovali Chloe v poděkování ve svém deníku.
Aby měl Spielman přehled o jejich práci, pokračoval ve svých pracovních deníkech a zapisoval si každou myšlenku a rovnici, které tabule obsahovaly, než je vymazal. Dnes tucet těchto 200stránkových deníků velikosti notebooku lemuje poličku v jeho kanceláři v budově 2. Říká, že asi 60 procent informací, které časopisy obsahují, je práce na hladké analýze. Mezitím Teng pomocí digitálního fotoaparátu pořídil asi 40 fotografií tabulí, než byly vymazány.
Konečně odpověď Proč
Výsledkem celého tohoto výzkumu byla odpověď na jednoduchou otázku Proč? Spielman a Teng konečně přišli na to, proč simplexová metoda celou tu dobu tak dobře fungovala. Dokázali to vyvinutím nového způsobu analýzy algoritmu.
Až do svého objevu většina matematiků měřila algoritmy pomocí analýzy nejhoršího případu, ve které jsou algoritmu zadány nejobtížnější údaje a pak se posuzuje, jak dobře s nimi dokáže počítat. Bylo by to, jako by vám někdo předal nejhorší možný problém s dlouhým dělením, jaký si dokážete představit, a poté otestoval, zda ho dokážete vyřešit a jak dlouho to bude trvat. Ale u simplexové metody to prostě nefungovalo.
Spielman a Teng tedy našli nový přístup. Zavedli určitou variabilitu do analýzy nejhoršího případu. Namísto použití přesných čísel jako vstupů pro testování algoritmu umožnili nepřesnost. Pokud byl například vstup 1,31, umožnili náhodný vstup mezi 1,29 a 1,33. Zjistili, že tím, že počítá s nepřesností, simplexní algoritmus vždy efektivně vyřeší problém, a proto byl tak úspěšný.
Myšlenka zní jednoduše, ale matematika, která ji podporuje, je složitá. První časopis Spielmana a Tenga na toto téma, nyní pod kontrolou Asociace pro výpočetní techniku Věstník ACM , obsahuje 80 stran rovnic. Nevím, jestli by tolik lidí mohlo projít novinami, říká Spielman. Ve skutečnosti psaní článku občas zmátlo Spielmana a Tenga. Několikrát jsme prostě vyhodili, co bylo napsáno, a napsali znovu, protože když to bylo komplikované pro nás, pro [jiné] to bude ještě složitější, říká Spielman.
Spielman a Teng prezentovali svá zjištění po celém světě s nadšeným ohlasem. V roce 2001 publikovali příspěvek na konferenci a od té doby oba přednesli pozvané prezentace a hlavní projevy po celých Spojených státech a v Číně, Turecku, Itálii, Švýcarsku a Dánsku.
Tato vyhlazená analýza je důležitým pokrokem, říká Michel Goemans, PhD ‘90, profesor aplikované matematiky na MIT. A David Johnson, vedoucí oddělení algoritmů a optimalizace v AT&T Labs-Research, říká, že [Smoothed analysis] poskytuje extra úroveň důvěry pro ty, kteří používají simplexovou metodu.
Spielman říká, že svou tabuli nevytáhl od loňského léta, kdy byly noviny konečně hotové, ale bez ní bychom ten papír nikdy nedokázali napsat. Nyní Spielman doporučuje, aby si mladí vědci koupili velké bílé tabule jako dobrý první krok k dosažení průlomů. Teng však připisuje velkou část jejich úspěchu Spielmanově dynamické mysli a skvělé chuti při výběru výzkumných problémů. Vždy má odvahu pracovat na nejtěžším otevřeném problému v této oblasti, říká Teng, a to by mohlo být ještě lepším výchozím bodem pro výzkumníky a zvědavé lidi všude.