Rozwiązanie Simplex

Siedząc na sali sądowej, czekając, aby dowiedzieć się, czy zostanie wybrany na ławę przysięgłych, Daniel Spielman doznał objawienia – cała praca, którą on i jego kolega Shanghua Teng zbudowali w ciągu ostatnich trzech lat, była domkiem z kart. Nigdy nie zapomnę, mówi Spielman, docent matematyki. Jak tam siedziałam i czekałam-na szczęście nie zostać wybranym – miałem okropne doświadczenie, kiedy zdałem sobie sprawę, że wszystko, co robiliśmy, było złe. Pomyślałem o wyrzuceniu mojego programu badawczego. I w tym momencie karty upadły.

Para próbowała znaleźć sposób na ulepszenie metody simplex, jednego z najczęściej używanych algorytmów na świecie. Dzięki temu wiele złożonych systemów, które przyjmujemy za pewnik — takich jak sieci telekomunikacyjne i planowanie dla flot pojazdów dostawczych lub lotów linii lotniczych — może działać tak wydajnie i tanio, jak to tylko możliwe. Jako nowy adiunkt, Spielman chciał zagłębić się w świat matematyki i zdobyć etat na MIT, pracując nad dużym wyzwaniem, a mianowicie uproszczeniem, przyspieszeniem i usprawnieniem algorytmu. Ale po tym dniu w sądzie, kiedy zdał sobie sprawę, że stosowanie pojęć z niezwiązanego obszaru do algorytmu simpleks to ślepy zaułek, wiedział, że będzie musiał znaleźć kolejny wielki przełom, aby osiągnąć swoje cele.

Kilka dni później, niczym człowiek, którego dom został zniszczony przez huragan lub tornado, Spielman zaczął ratować to, co zostało z ruin jego badań. I wtedy pojawił się naprawdę wielki pomysł: chociaż jego praca nie mogła ulepszyć metody simplex, być może mogłaby… wyjaśnić . Metoda została opracowana w 1947 roku, ale po ponad 50 latach analiz nikt nie był w stanie dowiedzieć się, dlaczego to działa. Przeczucie Spielmana okazało się słuszne. Po kolejnych trzech latach wspólnej pracy i setkach formuł matematycznych, on i Teng, profesor na Uniwersytecie w Bostonie, mogą teraz wyjaśnić, dlaczego metoda simpleks działa. Może to pozwolić tzw. ekspertom od optymalizacji na rozwiązywanie jeszcze bardziej złożonych problemów organizacyjnych. Już teraz wyjaśnienie, zwane wygładzoną analizą, zostało cytowane przez National Science Foundation jako znaczący postęp w technologii informacyjnej.

Droga do odkrycia

Spielman i Teng spotkali się po raz pierwszy jesienią 1990 roku, kiedy Spielman, wówczas student Uniwersytetu Yale, odwiedził Carnegie Mellon University, aby wygłosić przemówienie. Teng, tamtejszy doktorant, mówi, że on i inni na uniwersytecie podziwiali tego długowłosego juniora. Miał już dwie prace doktorskie. Oczywiście był jednym z najbardziej cenionych potencjalnych studentów, których wszystkie czołowe uniwersytety chciały przyciągnąć do swoich programów doktoranckich. W 1992 roku Spielman wybrał MIT. Teng przybył w tym samym roku jako instruktor w Instytucie. Ich relacja uczeń-nauczyciel szybko przekształciła się w przyjaźń, a następnie współpracę, która trwała 11 lat.

W 1996 roku, po kilku latach wspólnej pracy w innym obszarze, duet zaczął dążyć do udoskonalenia metody simplex. Proces badawczy jest bardzo podobny do poszukiwania skarbu na ciemnej wyspie za pomocą małej latarki, mówi Teng. Próbowaliśmy zbadać te wiele obiecujących tropów. Dan zawsze prowadzi szczegółowe dzienniki robocze, które systematycznie zaznaczają mapy eksploracji.

Po trzech latach takiej pracy Spielman doczekał się realizacji sali sądowej. Obaj matematycy zmienili swój cel i poważnie zaatakowali nowy problem badawczy.

Teng, który wtedy był profesorem nadzwyczajnym na Uniwersytecie Illinois w Urbana-Champaign, wrócił do Massachusetts na urlop naukowy i wynajął mieszkanie pięć minut od domu Spielmana. Następnie obaj badacze zamienili swoje salony w miejsca pracy. Teng zawiesił dużą białą tablicę na ścianie w swoim salonie. Spielman trzymał jeden za sofą.

Odtąd ich wspólna praca odbywała się przez całą dobę. To była jedna z tych rzeczy, w których moja żona narzekała, że ​​widuję Shanghua częściej niż ją przez kilka lat, mówi Spielman. Teng pracował na pełny etat w Akamai w Cambridge, ale prawie każdego wieczoru po pracy i w weekendy chodził do mieszkania Spielmana. Siedzieliśmy na nogach przez wiele godzin, prawdopodobnie do drugiej, pracując, zauważa Spielman. Teng dodaje, byłem jak adoptowany członek rodziny Dana. Nawet ich kotka, Chloe, tak przyzwyczaiła się do naszej obecności, że przysiadała przed tablicą i uważnie się przyglądała, kiedy ją ustawialiśmy. Naukowcy podziękowali Chloe w podziękowaniach w swoim czasopiśmie.

Aby śledzić ich pracę, Spielman kontynuował swoje dzienniki robocze, spisując każdą myśl i równanie zawarte na tablicach przed ich wymazaniem. Dziś na półce w jego biurze w budynku 2 stoi tuzin tych 200-stronicowych czasopism wielkości zeszytu. Mówi, że około 60 procent informacji zawartych w czasopismach to praca nad wygładzoną analizą. W międzyczasie Teng użył aparatu cyfrowego, aby zrobić około 40 zdjęć tablic, zanim zostały usunięte.

W końcu odpowiadam dlaczego

Wynikiem wszystkich tych badań była odpowiedź na proste pytanie Dlaczego? Spielman i Teng w końcu zorientowali się, dlaczego metoda simpleks działa tak dobrze przez cały ten czas. Zrobili to, opracowując nowy sposób analizy algorytmu.

Do czasu ich odkrycia większość matematyków mierzyła algorytmy za pomocą analizy najgorszego przypadku, w której algorytm otrzymuje najtrudniejsze dane, a następnie ocenia, jak dobrze może z nimi obliczyć. To tak, jakby ktoś podał ci najgorszy możliwy problem z długim podziałem, jaki możesz sobie wyobrazić, a następnie przetestował, czy możesz go rozwiązać i jak długo to zajmie. Ale to po prostu nie działało w przypadku metody simplex.

Więc Spielman i Teng znaleźli nowe podejście. Wprowadzili pewną zmienność do analizy najgorszego przypadku. Zamiast używać dokładnych liczb jako danych wejściowych do testowania algorytmu, pozwolili na niedokładność. Na przykład, jeśli dane wejściowe wynosiły 1,31, zezwalali na losowe dane wejściowe między 1,29 a 1,33. Odkryli, że pozwalając na nieprecyzyjność, algorytm simpleks zawsze skutecznie rozwiązywał problem i dlatego odniósł taki sukces.

Pomysł brzmi prosto, ale matematyka, która go wspiera, jest złożona. Pierwszy artykuł w czasopiśmie Spielmana i Tenga na ten temat, obecnie recenzowany przez Association for Computing Machinery Dziennik ACM , zawiera 80 stron równań. Nie wiem, czy tyle osób mogłoby przejść przez gazetę – mówi Spielman. W rzeczywistości pisanie gazety czasami nawet myliło Spielmana i Tenga. Kilka razy po prostu wyrzuciliśmy to, co zostało napisane i pisaliśmy od nowa, ponieważ jeśli było to dla nas skomplikowane, to dla innych ludzi będzie jeszcze bardziej skomplikowane, mówi Spielman.

Spielman i Teng zaprezentowali swoje odkrycia na całym świecie z entuzjastycznym przyjęciem. Opublikowali referat konferencyjny w 2001 r. i od tego czasu obaj wygłosili zaproszone prezentacje i wygłosili przemówienia w całych Stanach Zjednoczonych oraz w Chinach, Turcji, Włoszech, Szwajcarii i Danii.

Ta wygładzona analiza jest ważnym osiągnięciem, mówi dr Michel Goemans w latach 90., profesor matematyki stosowanej na MIT. A David Johnson, szef Działu Algorytmów i Optymalizacji w AT&T Labs-Research, mówi: [Analiza wygładzona] zapewnia dodatkowy poziom pewności dla tych, którzy używają metody simplex.

Spielman mówi, że nie wyciągnął swojej tablicy od zeszłego lata, kiedy artykuł w dzienniku został wreszcie ukończony, ale bez niej nigdy nie bylibyśmy w stanie napisać artykułu. Teraz Spielman zaleca młodym naukowcom kupowanie dużych tablic jako dobry pierwszy krok w kierunku dokonania przełomu. Jednak Teng przypisuje dużą część swojego sukcesu dynamicznemu umysłowi Spielmana i świetnemu gustowi w wyborze problemów badawczych. Zawsze ma odwagę pracować nad najtrudniejszym otwartym problemem w tej dziedzinie, mówi Teng, a to może być jeszcze lepszym punktem wyjścia dla badaczy i ciekawskich ludzi na całym świecie.

ukryć