Naukowcy zbliżają się do nowego ograniczenia prędkości w związku z poważnym problemem | Magazyn Quanta

Problem komiwojażera jest jednym z najstarszych znanych zagadnień obliczeniowych. Pyta o idealną trasę przez określoną listę miast, minimalizując przebieg. Pomimo pozornie prostego problemu, jest on niezwykle trudny. Chociaż możesz użyć brutalnej siły, aby sprawdzić wszystkie możliwe trasy, aż znajdziesz najkrótszą ścieżkę, taka strategia staje się nie do utrzymania po zaledwie kilku miastach. Zamiast tego można zastosować rygorystyczny model matematyczny zwany programowaniem liniowym, który z grubsza przybliża problem jako zbiór równań i metodycznie sprawdza możliwe kombinacje, aby znaleźć najlepsze rozwiązanie.

Czasami jednak konieczna jest optymalizacja pod kątem problemów związanych z liczbami całkowitymi. Co dobrego jest w planie optymalizacji fabryki, która produkuje kanapy 500.7? W tym celu badacze często sięgają po wariant programowania liniowego zwany programowanie liniowe całkowitoliczbowe (ILP). Jest popularny w zastosowaniach wymagających dyskretnych decyzji, w tym planowania produkcji, planowania załóg linii lotniczych i wyznaczania tras pojazdów. „Zasadniczo ILP to podstawa badań operacyjnych zarówno w teorii, jak i praktyce” – powiedział Santosh Wempala, informatyk w Georgia Institute of Technology.

Odkąd po raz pierwszy sformułowali ILP ponad 60 lat temubadacze odkryli różne algorytmy rozwiązujące problemy ILP, ale wszystkie są stosunkowo powolne pod względem liczby wymaganych kroków. Najlepsza wersja, jaką mogli wymyślić – coś w rodzaju ograniczenia prędkości – pochodzi z trywialnego przypadku, w którym zmienne problemu (takie jak to, czy sprzedawca odwiedza miasto, czy nie) mogą przyjmować jedynie wartości binarne (zero lub 1). W tym przypadku ILP ma czas wykonania, który skaluje się wykładniczo wraz z liczbą zmiennych, zwaną także wymiarem. (Jeśli istnieje tylko jedna zmienna, wystarczą dwa kroki, aby przetestować każdą możliwą kombinację i rozwiązać problem; dwie zmienne oznaczają cztery kroki, trzy oznaczają osiem kroków i tak dalej.)

Niestety, gdy zmienne przyjmą wartość większą niż zero i 1, czas działania algorytmu znacznie się wydłuża. Naukowcy od dawna zastanawiali się, czy uda im się zbliżyć do trywialnego ideału. Postęp był powolny, z rekord akcja rozgrywa się w latach 1980. XX wieku i ma charakter stopniowy ulepszenia zrobione od.

Ale ostatnie praca by Wiktor Reis, obecnie w Instytucie Studiów Zaawansowanych i Thomasa Rothvossana Uniwersytecie Waszyngtońskim dokonał największego od dziesięcioleci skoku w zakresie czasu działania. Łącząc narzędzia geometryczne w celu ograniczenia możliwych rozwiązań, stworzyli nowy, szybszy algorytm rozwiązywania ILP w niemal tym samym czasie, co trywialny przypadek binarny. Rezultatem była nagroda za najlepszy artykuł na festiwalu 2023 Podstawy informatyki konferencja.

„Ten nowy algorytm jest niezwykle ekscytujący” – powiedział Noaha Stephensa-Davidowitza, matematyk i informatyk z Cornell University. „Jest to pierwsze [ważne] udoskonalenie rozwiązań ILP od prawie 40 lat”.

ILP działa poprzez przekształcenie danego problemu w zbiór równań liniowych, które muszą spełniać pewne nierówności. Konkretne równania opierają się na szczegółach pierwotnego problemu. Ale choć szczegóły te mogą się różnić, podstawowy charakter problemów ILP pozostaje taki sam, co daje badaczom jeden sposób na zajęcie się wieloma problemami.

Nie oznacza to, że jest to łatwa praca. Dopiero w 1983 roku matematyk Henryk Lenstra okazały że ogólny problem można w ogóle rozwiązać, zapewniając pierwszy algorytm, który może to zrobić. Lenstra myślał o ILP geometrycznie. Najpierw przekształcił nierówności w sercu ILP w wypukły kształt, taki jak dowolny wielokąt foremny. Ten kształt reprezentuje ograniczenia indywidualnego problemu, który rozwiązujesz, niezależnie od tego, czy jest to produkcja kanap, czy planowanie linii lotniczych, więc wnętrze kształtu odpowiada wszystkim możliwym wartościom, które mogłyby rozwiązać nierówności, a tym samym problem. Lenstra nazwał ten kształt korpusem wypukłym. Wymiar problemu wpływa na wymiar tego kształtu: Przy dwóch zmiennych przyjmuje on postać płaskiego wielokąta; w trzech wymiarach jest to a Bryła platońskaI tak dalej.

Następnie Lenstra wyobraził sobie wszystkie liczby całkowite jako nieskończony zbiór punktów siatki, znany w matematyce jako siatka. Wersja dwuwymiarowa wygląda jak morze kropek, a w trzech wymiarach wygląda jak punkty, w których łączą się stalowe belki w budynku. Wymiar siatki zależy również od wymiaru danego problemu.

Aby rozwiązać dany problem ILP, Lenstra pokazał, że wystarczy szukać miejsca, w którym możliwe rozwiązania spotykają się ze zbiorem liczb całkowitych: na przecięciu ciała wypukłego i siatki. Opracował algorytm, który mógł wyczerpująco przeszukać tę przestrzeń, ale aby był skuteczny, czasami musiał podzielić problem na kawałki o mniejszych wymiarach, wydłużając czas działania o wiele kroków.

W kolejnych latach kilku badaczy badało, jak przyspieszyć działanie tego algorytmu. W 1988 Ravi Kannan i László Lovász wprowadzili koncepcję zwaną promieniem krycia, zapożyczone z badania kody korygujące błędy, aby pomóc wypukłemu ciału i siatce skuteczniej się przecinać. Z grubsza promień pokrycia zapewnia, że ​​wypukły korpus zawsze zawiera co najmniej jeden punkt całkowity, niezależnie od tego, gdzie go umieścisz na siatce. W rezultacie wielkość promienia pokrycia określa również, jak skutecznie można rozwiązać problem ILP.

Wszystko sprowadzało się więc do określenia wielkości idealnego promienia krycia. Niestety samo w sobie okazało się to trudnym problemem i najlepsze, co mogli zrobić Kannan i Lovász, to zawęzić możliwą wartość, szukając górnych i dolnych granic. Wykazali, że górna granica – maksymalny rozmiar promienia pokrycia – zwiększała się liniowo wraz z wymiarem. Było to dość szybkie, ale niewystarczające, aby znacząco przyspieszyć działanie ILP. W ciągu następnych 30 lat inni badacze mogli osiągnąć jedynie nieco lepsze wyniki.

Tym, co ostatecznie pomogło Reisowi i Rothvossowi w przebiciu się, był niepowiązany wynik matematyczny, który skupiał się wyłącznie na siatkach. W 2016 r. Oded Regev i Stephens-Davidowitz pokazałw efekcie, ile punktów sieci zmieści się w określonym kształcie. Reis i Rothvoss zastosowali to do innych kształtów, co pozwoliło im lepiej oszacować liczbę punktów sieci zawartych w promieniu pokrycia ILP, obniżając górną granicę. „Najnowszy przełom nastąpił wraz z uświadomieniem sobie, że tak naprawdę można tworzyć inne kształty” – powiedział Regev.

Ta nowa, zaostrzona górna granica stanowiła ogromną poprawę, umożliwiając Reisowi i Rothvossowi osiągnięcie dramatycznego przyspieszenia całego algorytmu ILP. Ich praca sprowadza środowisko wykonawcze do (log n)^O(n), Gdzie n jest liczbą zmiennych i Na)oznacza, że ​​skaluje się liniowo z n. (Wyrażenie to jest uważane za „prawie” takie samo jak czas wykonania problemu binarnego.)

„To triumf na styku matematyki, informatyki i geometrii” – powiedział Daniel Dadusz krajowego instytutu badawczego CWI w Holandii, który był pionierem algorytmu stosowanego przez Reisa i Rothvossa do pomiaru czasu działania ILP.

Na razie nowy algorytm nie został właściwie wykorzystany do rozwiązania jakichkolwiek problemów logistycznych, ponieważ aktualizacja dzisiejszych programów wymagałaby zbyt wiele pracy, aby móc z niego skorzystać. Ale dla Rothvossa nie ma to znaczenia. „Chodzi o teoretyczne zrozumienie problemu, który ma fundamentalne zastosowania” – powiedział.

Jeśli chodzi o to, czy można jeszcze poprawić wydajność obliczeniową ILP, badacze nadal mają nadzieję, że uda im się zbliżyć do idealnego czasu działania, ale nie w najbliższej przyszłości. „To wymagałoby całkowicie nowego pomysłu” – powiedział Vempala.