A kutatók új sebességkorlátozáshoz közelednek a magproblémák miatt | Quanta Magazin

Az utazó eladó probléma az egyik legrégebbi ismert számítási kérdés. Az ideális útvonalat kéri egy bizonyos városlistán keresztül, minimálisra csökkentve a futásteljesítményt. Annak ellenére, hogy egyszerűnek tűnik, a probléma köztudottan nehéz. Míg nyers erővel ellenőrizheti az összes lehetséges útvonalat, amíg meg nem találja a legrövidebb utat, egy ilyen stratégia már néhány város után tarthatatlanná válik. Ehelyett alkalmazhat egy szigorú matematikai modellt, az úgynevezett lineáris programozást, amely nagyjából egyenlethalmazként közelíti meg a problémát, és módszeresen ellenőrzi a lehetséges kombinációkat, hogy megtalálja a legjobb megoldást.

Néha azonban optimalizálnia kell az egész számmal kapcsolatos problémákra. Mire jó egy gyári optimalizálási terv, amely 500.7 heverőt gyárt? Ehhez a kutatók gyakran a lineáris programozás egy változatához folyamodnak, az úgynevezett egészszámú lineáris programozás (ILP). Népszerű az olyan alkalmazásokban, amelyek diszkrét döntéseket foglalnak magukban, beleértve a gyártástervezést, a légitársaságok személyzetének ütemezését és a jármű útvonaltervezését. „Alapvetően az ILP a műveletek kutatásának kenyere, mind elméletben, mind gyakorlatban” – mondta Santosh Vempala, a Georgia Institute of Technology informatikusa.

Mióta először megfogalmazták az ILP-t több mint 60 éve, a kutatók különféle algoritmusokat fedeztek fel, amelyek megoldják az ILP-problémákat, de ezek mindegyike viszonylag lassú volt a szükséges lépések számát tekintve. A legjobb változat – egyfajta sebességkorlátozás – abból a triviális esetből származik, amikor a probléma változói (például, hogy az eladó ellátogat-e egy városba vagy sem) csak bináris értékeket (nulla vagy 1) feltételezhetnek. Ebben az esetben az ILP-nek van egy futásideje, amely exponenciálisan skálázódik a változók számával, amelyet dimenziónak is neveznek. (Ha csak egy változó van, mindössze két lépésre van szükség az összes lehetséges kombináció teszteléséhez és a probléma megoldásához; két változó négy lépést, három nyolc lépést jelent, és így tovább.)

Sajnos, ha a változók értéke meghaladja a nullát és az 1-et, az algoritmus futásideje sokkal hosszabb lesz. A kutatók régóta azon töprengenek, vajon közelebb kerülhetnének-e a triviális ideálhoz. A haladás lassú volt, a rekord az 1980-as években játszódik, és csak növekményes fejlesztések óta készült.

De a közelmúltban munka by Victor Reis, jelenleg az Institute for Advanced Study, és Thomas Rothvoss, a Washingtoni Egyetemen az elmúlt évtizedek legnagyobb futásidejű ugrását hajtotta végre. A lehetséges megoldásokat korlátozó geometriai eszközök kombinálásával új, gyorsabb algoritmust hoztak létre az ILP megoldására a triviális bináris esettel csaknem egyidőben. Az eredmény 2023-ban a legjobb papír díját kapta A számítástechnika alapjai konferencián.

„Ez az új algoritmus rendkívül izgalmas” – mondta Noah Stephens-Davidowitz, matematikus és informatikus a Cornell Egyetemen. "Ez közel 40 év óta az első [nagy] fejlesztés az ILP-megoldók terén."

Az ILP úgy működik, hogy egy adott problémát lineáris egyenletek halmazává alakít át, amelyeknek ki kell elégíteniük bizonyos egyenlőtlenségeket. A konkrét egyenletek az eredeti probléma részletein alapulnak. Bár ezek a részletek eltérőek lehetnek, az ILP-problémák alapvető felépítése változatlan marad, így a kutatók egyetlen módot kínálnak a problémák sokaságának megtámadására.

Ez nem azt jelenti, hogy könnyű munka. Csak 1983-ban a matematikus Hendrik Lenstra bizonyított hogy az általános probléma még megoldható is volt, megadva az első algoritmust, amely képes volt rá. Lenstra geometrikusan gondolkodott az ILP-ről. Először az ILP középpontjában lévő egyenlőtlenségeket konvex alakzattá alakította, például bármely szabályos sokszöget. Ez az alakzat a megoldandó egyéni probléma korlátait reprezentálja, legyen szó kanapégyártásról vagy légitársaság menetrendjéről, így az alakzat belseje minden lehetséges értéknek megfelel, ami megoldhatja az egyenlőtlenségeket, és így a problémát. Lenstra ezt az alakzatot konvex testnek nevezte. A probléma mérete befolyásolja ennek az alakzatnak a méretét: Két változóval lapos sokszög alakját veszi fel; három dimenzióban ez a Plátói szilárd anyag, És így tovább.

Lenstra ezután az összes egész számot rácspontok végtelen halmazaként képzelte el, amelyet a matematika rácsként ismer. A kétdimenziós változat ponttengernek tűnik, három dimenzióban pedig úgy néz ki, mint azok a pontok, ahol az épület acélgerendái összekapcsolódnak. A rács mérete az adott probléma méretétől is függ.

Egy adott ILP feladat megoldásához Lenstra megmutatta, hogy csak azt kell keresni, hogy a lehetséges megoldások hol találkoznak az egész számokkal: a konvex test és a rács metszéspontjában. És kitalált egy algoritmust, amely kimerítően képes keresni ezt a helyet – de ahhoz, hogy hatékony legyen, néha kisebb méretű darabokra kellett bontania a problémát, és sok lépést kellett hozzáadnia a futásidőhöz.

A következő években több kutató is megvizsgálta, hogyan lehetne gyorsabbá tenni ezt az algoritmust. Ravi Kannan és Lovász László 1988-ban vezette be a fedősugár fogalmát, kölcsönzött tanulmányából hibajavító kódok, hogy segítse a konvex test és a rács hatékonyabb metszéspontját. Nagyjából a lefedési sugár gondoskodik arról, hogy a konvex test mindig tartalmazzon legalább egy egész pontot, függetlenül attól, hogy hol helyezzük el a rácson. Ennek eredményeként a lefedési sugár mérete azt is meghatározza, hogy milyen hatékonyan tudja megoldani az ILP problémát.

Tehát minden az ideális fedési sugár méretének meghatározásában dőlt el. Sajnos ez önmagában is nehéz problémának bizonyult, és Kannan és Lovász legjobban az volt, hogy leszűkítettek egy lehetséges értéket a felső és alsó határok keresésével. Megmutatták, hogy a felső korlát – a lefedési sugár maximális mérete – lineárisan skálázódik a mérettel. Ez elég gyors volt, de nem elég ahhoz, hogy jelentősen felgyorsítsa az ILP futási idejét. A következő 30 évben más kutatók csak valamivel jobb eredményeket értek el.

Ami végül segített Reisnek és Rothvossnak áttörni, az egy független matematikai eredmény volt, amely pusztán a rácsokra összpontosított. 2016-ban Oded Regev és Stephens-Davidowitz kimutatta,, valójában hány rácspont fér el egy adott alakzaton belül. Reis és Rothvoss ezt más alakzatokra is alkalmazta, ami lehetővé tette számukra, hogy jobban megbecsüljék az ILP lefedési sugárban található rácspontok számát, csökkentve a felső korlátot. „A legújabb áttörést az a felismerés hozta, hogy valójában másfajta formákat is lehet készíteni” – mondta Regev.

Ez az új szigorított felső korlát hatalmas előrelépést jelentett, lehetővé téve Reis és Rothvoss számára, hogy drámai módon felgyorsítsák az általános ILP-algoritmust. Munkájuk a futási időt a (log n)^O(n), Ahol n a változók száma és O (n)azt jelenti, hogy lineárisan skálázódik vele n. (Ez a kifejezés „majdnem” megegyezik a bináris probléma futási idejével.)

„Ez egy diadal a matematika, a számítástechnika és a geometria metszéspontjában” – mondta Daniel Dadush a holland CWI nemzeti kutatóintézet munkatársa, aki segített úttörőként kidolgozni azt az algoritmust, amelyet Reis és Rothvoss használt az ILP futási idejének mérésére.

Az új algoritmust egyelőre nem használták logisztikai problémák megoldására, mivel túl sok munkát igényelne a mai programok frissítése, hogy kihasználják. De Rothvoss számára ez nem a lényeg. „Egy olyan probléma elméleti megértéséről van szó, amelynek alapvető alkalmazásai vannak” – mondta.

Ami azt illeti, hogy az ILP számítási hatékonysága tovább javítható-e, a kutatók továbbra is abban reménykednek, hogy továbbra is megközelítik az ideális futási időt – de nem egyhamar. „Ehhez alapvetően új ötletre lenne szükség” – mondta Vempala.