Teadlased lähenevad uuele kiiruspiirangule põhiprobleemi lahendamiseks

Taasavaldanud Platon

järgijaid: 0

Rändmüüja probleem on üks vanimaid teadaolevaid arvutuslikke küsimusi. See küsib ideaalset marsruuti läbi teatud linnade loendi, minimeerides läbisõitu. Vaatamata näiliselt lihtsale on probleem kurikuulsalt keeruline. Kuigi võite kasutada jõhkrat jõudu, et kontrollida kõiki võimalikke marsruute, kuni leiate lühima tee, muutub selline strateegia vastuvõetamatuks juba käputäie linnade järel. Selle asemel saate rakendada ranget matemaatilist mudelit, mida nimetatakse lineaarseks programmeerimiseks, mis ligikaudselt läheneb probleemile võrrandite kogumina ja kontrollib metoodiliselt võimalikke kombinatsioone, et leida parim lahendus.

Kuid mõnikord peate optimeerima täisarvudega seotud probleeme. Mis kasu on tehase optimeerimise plaanist, mis toodab 500.7 diivanit? Selleks pöörduvad teadlased sageli lineaarse programmeerimise variandi poole, mida nimetatakse täisarvuline lineaarne programmeerimine (ILP). See on populaarne rakendustes, mis hõlmavad diskreetseid otsuseid, sealhulgas tootmise planeerimist, lennumeeskonna sõiduplaani ja sõidukite marsruutimist. "Põhimõtteliselt on ILP operatsioonide uurimise leib ja võid nii teoorias kui ka praktikas," ütles Santosh Vempala, Georgia Tehnoloogiainstituudi arvutiteadlane.

Alates sellest, kui nad esimest korda ILP-d koostasid üle 60 aasta tagasi, on teadlased avastanud erinevaid algoritme, mis lahendavad ILP-probleeme, kuid need kõik on olnud nõutavate sammude arvu osas suhteliselt aeglased. Parim versioon, mille nad välja võivad pakkuda – omamoodi kiirusepiirang – pärineb triviaalsest juhtumist, kus probleemi muutujad (nt kas müüja külastab linna või mitte) võivad eeldada ainult kahendväärtusi (null või 1). Sel juhul on ILP-l käitusaeg, mis skaleerub eksponentsiaalselt muutujate arvuga, mida nimetatakse ka dimensiooniks. (Kui on ainult üks muutuja, kulub iga võimaliku kombinatsiooni testimiseks ja probleemi lahendamiseks vaid kaks sammu; kaks muutujat tähendavad nelja sammu, kolm tähendavad kaheksat sammu ja nii edasi.)

Kahjuks, kui muutujate väärtus on suurem kui null ja 1, pikeneb algoritmi käitusaeg palju pikemaks. Teadlased on pikka aega mõelnud, kas nad võiksid triviaalsele ideaalile lähemale jõuda. Edusammud on olnud aeglased rekord tegevus toimub 1980ndatel ja ainult järkjärguline parandusi aastast tehtud.

Kuid hiljuti töö by Viktor Reis, praegu Kõrgkoolide Instituudis ja Thomas Rothvoss, Washingtoni ülikoolis, on teinud aastakümnete suurima käitusaja hüppe. Kombineerides geomeetrilisi tööriistu võimalike lahenduste piiramiseks, lõid nad uue, kiirema algoritmi ILP lahendamiseks peaaegu sama aja jooksul kui triviaalne binaarjuhtum. Tulemus pälvis 2023. aastal parima paberi auhinna Arvutiteaduse alused konverents.

"See uus algoritm on äärmiselt põnev, " ütles Noa Stephens-Davidowitz, matemaatik ja arvutiteadlane Cornelli ülikoolist. "See on esimene [suur] ILP-lahendajate täiustus peaaegu 40 aasta jooksul."

ILP töötab, teisendades antud probleemi lineaarsete võrrandite kogumiks, mis peavad rahuldama mõningaid ebavõrdsusi. Konkreetsed võrrandid põhinevad algse probleemi üksikasjadel. Kuid kuigi need üksikasjad võivad erineda, jääb ILP-probleemide põhikoostis samaks, andes teadlastele ühe võimaluse paljude probleemide lahendamiseks.

See ei tähenda, et see on lihtne töö. Alles 1983. aastal sai matemaatik Hendrik Lenstra tõestatud et üldine probleem oli isegi lahendatav, pakkudes esimest algoritmi, mis seda teha suutis. Lenstra mõtles ILP-le geomeetriliselt. Esiteks muutis ta ILP keskmes olevad ebavõrdsused kumeraks kujundiks, näiteks mis tahes korrapäraseks hulknurgaks. See kujund esindab teie lahendatava individuaalse probleemi piiranguid, olgu see siis diivani tootmine või lennufirma ajakava, nii et kujundi sisemus vastab kõigile võimalikele väärtustele, mis võiksid ebavõrdsust ja seega ka probleemi lahendada. Lenstra nimetas seda kuju kumeraks kehaks. Ülesande mõõde mõjutab selle kujundi mõõdet: Kahe muutujaga on see tasase hulknurga kuju; kolmemõõtmeliselt on see a Platooniline tahke aine, ja nii edasi.

Järgmisena kujutas Lenstra kõiki täisarve ette lõpmatu võrgupunktide kogumina, mida matemaatikas tuntakse võrena. Kahemõõtmeline versioon näeb välja nagu täppide meri ja kolmemõõtmelisena näeb see välja nagu punktid, kus hoone terastalad ühenduvad. Võre mõõde oleneb ka antud ülesande mõõtmest.

Antud ILP-ülesande lahendamiseks näitas Lenstra, et tuleb lihtsalt otsida, kus võimalikud lahendused kohtuvad täisarvude hulgaga: kumera keha ja võre ristumiskohas. Ja ta mõtles välja algoritmi, mis võiks seda ruumi ammendavalt otsida – kuid tõhususe tagamiseks pidi see mõnikord probleemi väiksemateks tükkideks jagama, lisades käitusajale palju samme.

Järgnevatel aastatel uurisid mitmed teadlased, kuidas seda algoritmi kiiremini tööle panna. 1988. aastal võtsid Ravi Kannan ja László Lovász kasutusele kontseptsiooni, mida nimetatakse katteraadiuseks, laenatud uuringust veaparanduskoodid, et aidata kumeral kehal ja võrel tõhusamalt ristuda. Ligikaudu katteraadius tagab, et kumer keha sisaldab alati vähemalt ühte täisarvu, olenemata sellest, kuhu te selle võre asetate. Selle tulemusena määrab katte raadiuse suurus ka selle, kui tõhusalt saate ILP-probleemi lahendada.

Nii et kõik taandus ideaalse katteraadiuse suuruse määramisele. Kahjuks osutus see omaette raskeks probleemiks ning parim, mida Kannan ja Lovász teha said, oli võimalikku väärtust vähendada, otsides ülemist ja alumist piiri. Nad näitasid, et ülemine piir - katteraadiuse maksimaalne suurus - suurenes lineaarselt mõõtmega. See oli üsna kiire, kuid mitte piisav, et oluliselt kiirendada ILP tööaega. Järgmise 30 aasta jooksul saaksid teised teadlased vaid veidi paremini hakkama.

See, mis lõpuks aitas Reisil ja Rothvossil läbi murda, oli sõltumatu matemaatiline tulemus, mis keskendus puhtalt võrele. 2016. aastal Oded Regev ja Stephens-Davidowitz näitas, kui palju võrepunkte mahub konkreetse kuju sisse. Reis ja Rothvoss rakendasid seda teistele kujunditele, mis võimaldas neil paremini hinnata ILP katteraadiuses sisalduvate võrepunktide arvu, alandades ülemist piiri. "Viimane läbimurre tuli mõistmisega, et saate tegelikult teha ka muid kujundeid, " ütles Regev.

See uus pingutatud ülempiir oli tohutu edasiminek, võimaldades Reisil ja Rothvossil saavutada üldise ILP-algoritmi järsu kiirendamise. Nende töö toob käitusaja (log n)^O⁽ⁿ⁾, Kus n on muutujate arv ja O (n)tähendab, et see mastaabib lineaarselt n. (Seda avaldist peetakse "peaaegu" samaks kui binaarse probleemi käitamisaega.)

"See on triumf matemaatika, arvutiteaduse ja geomeetria ristumiskohas," ütles Daniel Dadush Madalmaade riiklikust uurimisinstituudist CWI, kes aitas välja töötada algoritmi, mida Reis ja Rothvoss kasutasid ILP käitusaja mõõtmiseks.

Praegu pole uut algoritmi tegelikult kasutatud logistiliste probleemide lahendamiseks, kuna tänapäevaste programmide värskendamine nõuaks liiga palju tööd, et seda kasutada. Kuid Rothvossi jaoks on see asja kõrval. "See puudutab teoreetilise arusaama probleemist, millel on põhimõttelised rakendused, " ütles ta.

Seoses sellega, kas ILP arvutuslikku efektiivsust saaks veelgi parandada, loodavad teadlased endiselt, et nad lähenevad ideaalsele käitusajale, kuid mitte niipea. "See nõuaks täiesti uut ideed," ütles Vempala.