Raziskovalci pristopijo k novi omejitvi hitrosti za prvotno težavo | Revija Quanta

Problem trgovskega potnika je eno najstarejših znanih računalniških vprašanj. Zahteva idealno pot skozi določen seznam mest, kar zmanjša kilometrino. Kljub temu, da se zdi preprosta, je težava znano težka. Medtem ko lahko uporabite surovo silo, da preverite vse možne poti, dokler ne najdete najkrajše poti, postane takšna strategija nevzdržna že po nekaj mestih. Namesto tega lahko uporabite strog matematični model, imenovan linearno programiranje, ki približno približa problem kot niz enačb in metodično preverja možne kombinacije, da bi našel najboljšo rešitev.

Toda včasih morate optimizirati za težave, ki vključujejo količine celih števil. Kaj pomaga načrt za optimizacijo tovarne, ki proizvaja kavče 500.7? Za to se raziskovalci pogosto obrnejo na različico linearnega programiranja, imenovano celoštevilsko linearno programiranje (ILP). Priljubljen je v aplikacijah, ki vključujejo diskretne odločitve, vključno z načrtovanjem proizvodnje, razporedom letalskih posadk in usmerjanjem vozil. "V bistvu je ILP kruh in maslo operacijskih raziskav tako v teoriji kot v praksi," je dejal Santosh Vempala, računalničar na Georgia Institute of Technology.

Odkar so prvič oblikovali ILP pred več kot 60 leti, so raziskovalci odkrili različne algoritme, ki rešujejo težave ILP, vendar so bili vsi razmeroma počasni v smislu števila potrebnih korakov. Najboljša različica, ki so jo lahko iznašli – nekakšna omejitev hitrosti – izhaja iz trivialnega primera, ko lahko spremenljivke problema (na primer, ali prodajalec obišče mesto ali ne) prevzamejo le binarne vrednosti (nič ali 1). V tem primeru ima ILP čas izvajanja, ki se eksponentno spreminja s številom spremenljivk, imenovanih tudi dimenzija. (Če obstaja samo ena spremenljivka, sta potrebna samo dva koraka, da preizkusimo vsako možno kombinacijo in rešimo problem; dve spremenljivki pomenita štiri korake, tri pomenijo osem korakov in tako naprej.)

Na žalost, ko spremenljivke sprejmejo vrednost, ki presega le nič in 1, se čas izvajanja algoritma precej podaljša. Raziskovalci so se dolgo spraševali, ali bi se lahko približali trivialnemu idealu. Napredek je bil počasen, z zapis nastavljen v osemdesetih letih prejšnjega stoletja in le postopen Izboljšave narejeno od.

Toda nedavno delo by Viktor Reis, trenutno na Inštitutu za napredne študije, in Thomas Rothvoss, na Univerzi v Washingtonu, je naredil največji preskok v času delovanja v zadnjih desetletjih. S kombiniranjem geometrijskih orodij za omejitev možnih rešitev so ustvarili nov, hitrejši algoritem za reševanje ILP v skoraj istem času kot trivialni binarni primer. Rezultat je leta 2023 prejel nagrado za najboljši prispevek Osnove računalništva konferenca.

"Ta novi algoritem je izjemno vznemirljiv," je rekel Noah Stephens-Davidowitz, matematik in računalničar na univerzi Cornell. "Predstavlja prvo [večjo] izboljšavo reševalcev ILP v skoraj 40 letih."

ILP deluje tako, da dano težavo pretvori v niz linearnih enačb, ki morajo izpolnjevati nekatere neenakosti. Posebne enačbe temeljijo na podrobnostih prvotnega problema. Toda čeprav se te podrobnosti lahko razlikujejo, osnovna sestava problemov ILP ostaja enaka, kar daje raziskovalcem en sam način za napad na množico problemov.

To ne pomeni, da je delo enostavno. Šele leta 1983 je matematik Hendrik Lenstra dokazano da je splošna težava celo rešljiva, s čimer smo zagotovili prvi algoritem, ki je to zmogel. Lenstra je razmišljal o ILP geometrijsko. Najprej je neenakosti v središču ILP spremenil v konveksno obliko, kot je kateri koli pravilni mnogokotnik. Ta oblika predstavlja omejitve posameznega problema, ki ga rešujete, ne glede na to, ali gre za proizvodnjo kavča ali načrtovanje letalskih prevozov, tako da notranjost oblike ustreza vsem možnim vrednostim, ki bi lahko rešile neenakosti in s tem problem. Lenstra je to obliko imenoval konveksno telo. Dimenzija problema vpliva na dimenzijo te oblike: Z dvema spremenljivkama ima obliko ravnega mnogokotnika; v treh dimenzijah je a Platonska trdna snov, in tako naprej.

Lenstra si je nato zamislil vsa cela števila kot neskončno množico točk mreže, ki je v matematiki znana kot mreža. Dvodimenzionalna različica je videti kot morje pik, v treh dimenzijah pa kot točke, kjer se povezujejo jekleni nosilci v zgradbi. Dimenzija rešetke je odvisna tudi od razsežnosti danega problema.

Za rešitev danega problema ILP je Lenstra pokazal, da samo iščete, kje se možne rešitve srečajo z nizom celih števil: na presečišču konveksnega telesa in mreže. In prišel je do algoritma, ki bi lahko izčrpno preiskal ta prostor - toda da bi bil učinkovit, je moral včasih problem razbiti na dele manjših dimenzij in dodal veliko korakov v čas izvajanja.

V naslednjih letih je več raziskovalcev raziskovalo, kako narediti ta algoritem hitrejši. Leta 1988 sta Ravi Kannan in László Lovász predstavila koncept, imenovan pokrivni radij, izposojeni iz študije o kode za popravljanje napak, da se konveksno telo in mreža učinkoviteje sekata. V grobem, pokrivni radij zagotavlja, da konveksno telo vedno vsebuje vsaj eno celo točko, ne glede na to, kam ga postavite na mrežo. Kot rezultat, velikost polmera pokrivanja tudi določa, kako učinkovito lahko rešite problem ILP.

Vse se je torej zmanjšalo na določitev velikosti idealnega polmera pokrivanja. Na žalost se je to samo po sebi izkazalo za težko težavo in najboljše, kar sta lahko naredila Kannan in Lovász, je bilo, da sta zožila možno vrednost z iskanjem zgornje in spodnje meje. Pokazali so, da se zgornja meja - največja velikost pokritega polmera - povečuje linearno z dimenzijo. To je bilo precej hitro, vendar ne dovolj, da bi znatno pospešilo čas izvajanja ILP. V naslednjih 30 letih bi lahko drugi raziskovalci dosegli le nekoliko boljše rezultate.

Kar je na koncu pomagalo Reisu in Rothvossu, da sta se prebila, je bil nepovezan matematični rezultat, ki se je osredotočal izključno na rešetke. Leta 2016 Oded Regev in Stephens-Davidowitz je pokazala,, v resnici, koliko mrežnih točk se lahko prilega določeni obliki. Reis in Rothvoss sta to uporabila pri drugih oblikah, kar jima je omogočilo, da sta bolje ocenila število mrežnih točk v polmeru, ki pokriva ILP, in znižala zgornjo mejo. »Najnovejši preboj je prišel s spoznanjem, da lahko dejansko naredite druge vrste oblik,« je dejal Regev.

Ta nova strožja zgornja meja je bila velika izboljšava, ki je Reisu in Rothvossu omogočila dramatično pospešitev celotnega algoritma ILP. Njihovo delo pripelje čas izvajanja do (log n)^O(n), Kjer n je število spremenljivk in O (n)pomeni, da se skalira linearno z n. (Ta izraz velja za "skoraj" enako kot čas izvajanja binarnega problema.)

"To je zmagoslavje na stičišču matematike, računalništva in geometrije," je dejal Daniel Daduš iz nacionalnega raziskovalnega inštituta CWI na Nizozemskem, ki je pomagal pri pionirju algoritma, ki sta ga Reis in Rothvoss uporabila za merjenje izvajalnega časa ILP.

Novi algoritem zaenkrat dejansko še ni bil uporabljen za reševanje kakršnih koli logističnih težav, saj bi bilo treba preveč delati s posodobitvijo današnjih programov, da bi ga lahko izkoristili. Toda za Rothvossa to ni pomembno. "Gre za teoretično razumevanje problema, ki ima temeljne aplikacije," je dejal.

Glede tega, ali bi lahko računalniško učinkovitost ILP še izboljšali, raziskovalci še vedno upajo, da se bodo še naprej približevali idealnemu času delovanja - vendar ne kmalu. "To bi zahtevalo bistveno novo idejo," je dejal Vempala.