Cercetătorii abordează o nouă limită de viteză pentru problema seminal | Revista Quanta

Problema vânzătorului ambulant este una dintre cele mai vechi întrebări de calcul cunoscute. Solicită traseul ideal printr-o anumită listă de orașe, minimizând kilometrajul. În ciuda faptului că pare simplă, problema este notoriu de dificilă. Deși puteți folosi forța brută pentru a verifica toate rutele posibile până când găsiți cea mai scurtă cale, o astfel de strategie devine insuportabilă după doar câteva orașe. În schimb, puteți aplica un model matematic riguros numit programare liniară, care aproximează aproximativ problema ca un set de ecuații și verifică metodic combinațiile posibile pentru a găsi cea mai bună soluție.

Dar uneori, trebuie să optimizați pentru problemele care implică sume întregi. La ce este bun un plan de optimizare a fabricii care produce canapele 500.7? Pentru aceasta, cercetătorii apelează adesea la o variantă de programare liniară numită programare liniară cu numere întregi (ILP). Este popular în aplicațiile care implică decizii discrete, inclusiv planificarea producției, programarea echipajului companiei aeriene și rutarea vehiculelor. „Practic, ILP este painea și untul cercetării operaționale atât în ​​teorie, cât și în practică”, a spus Santosh Vempala, un informatician la Institutul de Tehnologie din Georgia.

De când au formulat prima dată ILP acum peste 60 de ani, cercetătorii au descoperit diverși algoritmi care rezolvă problemele ILP, dar toți au fost relativ lenți în ceea ce privește numărul de pași necesari. Cea mai bună versiune cu care ar putea veni – un fel de limită de viteză – vine din cazul banal în care variabilele problemei (cum ar fi dacă un vânzător vizitează sau nu un oraș) pot lua doar valori binare (zero sau 1). În acest caz, ILP are un timp de execuție care se scalează exponențial cu numărul de variabile, numit și dimensiune. (Dacă există o singură variabilă, este nevoie de doar doi pași pentru a testa fiecare combinație posibilă și a rezolva problema; două variabile înseamnă patru pași, trei înseamnă opt pași și așa mai departe.)

Din păcate, odată ce variabilele iau o valoare dincolo de zero și 1, timpul de rulare al algoritmului crește mult mai mult. Cercetătorii s-au întrebat de mult dacă s-ar putea apropia de idealul banal. Progresul a fost lent, cu record plasat în anii 1980 și doar progresiv îmbunătățiri făcută de atunci.

Dar recent muncă by Victor Reis, în prezent la Institutul de Studii Avansate, și Thomas Rothvoss, de la Universitatea din Washington, a făcut cel mai mare salt de rulare din ultimele decenii. Combinând instrumente geometrice pentru a limita soluțiile posibile, au creat un nou algoritm mai rapid pentru rezolvarea ILP aproape în același timp cu cazul binar trivial. Rezultatul a primit un premiu pentru cea mai bună lucrare la 2023 Bazele Informaticii conferinţă.

„Acest nou algoritm este extrem de interesant”, a spus Noah Stephens-Davidowitz, matematician și informatician la Universitatea Cornell. „Reprezintă prima îmbunătățire [majoră] a soluțiilor ILP în aproape 40 de ani.”

ILP funcționează prin transformarea unei probleme date într-un set de ecuații liniare care trebuie să satisfacă unele inegalități. Ecuațiile specifice se bazează pe detaliile problemei inițiale. Dar, în timp ce aceste detalii pot diferi, structura de bază a problemelor ILP rămâne aceeași, oferind cercetătorilor o singură modalitate de a ataca o multitudine de probleme.

Asta nu înseamnă că este o muncă ușoară. Abia în 1983 matematicianul Hendrik Lenstra s-au dovedit că problema generală era chiar rezolvabilă, oferind primul algoritm care ar putea să o facă. Lenstra s-a gândit geometric la ILP. Mai întâi, el a transformat inegalitățile din centrul ILP într-o formă convexă, cum ar fi orice poligon obișnuit. Această formă reprezintă constrângerile problemei individuale pe care o rezolvați, fie că este vorba de producția de canapele sau de programarea unei companii aeriene, astfel încât interiorul formei corespunde tuturor valorilor posibile care ar putea rezolva inegalitățile și, prin urmare, problema. Lenstra a numit această formă corpul convex. Dimensiunea problemei influențează dimensiunea acestei forme: Cu două variabile ia forma unui poligon plat; în trei dimensiuni este a Solid platonic, Și așa mai departe.

Apoi Lenstra și-a imaginat toate numerele întregi ca un set infinit de puncte ale grilei, cunoscut în matematică ca o rețea. O versiune bidimensională arată ca o mare de puncte, iar în trei dimensiuni arată ca punctele în care grinzile de oțel dintr-o clădire se conectează. Dimensiunea rețelei depinde și de dimensiunea unei probleme date.

Pentru a rezolva o anumită problemă ILP, Lenstra a arătat că căutați doar unde soluțiile posibile se întâlnesc cu mulțimea de numere întregi: la intersecția corpului convex și a rețelei. Și a venit cu un algoritm care ar putea căuta în acest spațiu în mod exhaustiv - dar pentru a fi eficient, uneori trebuia să descompună problema în bucăți de dimensiuni mai mici, adăugând mulți pași la timpul de execuție.

În anii următori, câțiva cercetători au explorat cum să facă acest algoritm să ruleze mai rapid. În 1988, Ravi Kannan și László Lovász au introdus un concept numit raza de acoperire, împrumutat din studiul coduri de corectare a erorilor, pentru a ajuta corpul convex și rețeaua să se intersecteze mai eficient. Aproximativ, raza de acoperire se asigură că corpul convex conține întotdeauna cel puțin un punct întreg, indiferent de locul în care îl plasați pe rețea. Ca rezultat, dimensiunea razei de acoperire determină, de asemenea, cât de eficient puteți rezolva problema ILP.

Deci totul s-a rezumat la determinarea dimensiunii razei ideale de acoperire. Din păcate, aceasta s-a dovedit a fi o problemă grea în sine, iar cel mai bun lucru pe care Kannan și Lovász l-au putut face a fost să restrângă o valoare posibilă prin căutarea limitelor superioare și inferioare. Ei au arătat că limita superioară - dimensiunea maximă a razei de acoperire - a crescut liniar cu dimensiunea. Acest lucru a fost destul de rapid, dar nu suficient pentru a accelera semnificativ timpul de execuție ILP. În următorii 30 de ani, alți cercetători s-au putut descurca doar puțin mai bine.

Ceea ce i-a ajutat în cele din urmă pe Reis și Rothvoss să treacă peste a fost un rezultat matematic fără legătură, care s-a concentrat exclusiv pe zăbrele. În 2016, Oded Regev și Stephens-Davidowitz a arătat, de fapt, câte puncte de rețea ar putea încadra într-o anumită formă. Reis și Rothvoss au aplicat acest lucru altor forme, ceea ce le-a permis să estimeze mai bine numărul de puncte ale rețelei conținute într-o rază de acoperire a ILP, scăzând limita superioară. „Cea mai recentă descoperire a venit odată cu realizarea că de fapt poți face alte tipuri de forme”, a spus Regev.

Această nouă limită superioară înăsprită a reprezentat o îmbunătățire vastă, permițând lui Reis și Rothvoss să obțină o accelerare dramatică a algoritmului general ILP. Munca lor aduce timpul de execuție la (log n)^O(n), În cazul în care n este numărul de variabile și O (n)înseamnă că se scalează liniar cu n. (Această expresie este considerată „aproape” la fel cu durata de rulare a problemei binare.)

„Este un triumf la intersecția dintre matematică, informatică și geometrie”, a spus Daniel Dadush al institutului național de cercetare CWI din Țările de Jos, care a ajutat la lansarea algoritmului folosit de Reis și Rothvoss pentru a măsura durata de rulare a ILP.

Deocamdată, noul algoritm nu a fost de fapt folosit pentru a rezolva probleme logistice, deoarece ar fi nevoie de prea multă muncă actualizarea programelor de astăzi pentru a-l folosi. Dar pentru Rothvoss, asta nu are rost. „Este vorba despre înțelegerea teoretică a unei probleme care are aplicații fundamentale”, a spus el.

În ceea ce privește dacă eficiența computațională a ILP ar putea fi îmbunătățită în continuare, cercetătorii sunt încă sperați că se vor apropia în continuare de timpul de execuție ideal - dar nu în curând. „Asta ar necesita o idee fundamental nouă”, a spus Vempala.