Forskere nærmer seg ny fartsgrense for sædproblem | Quanta Magazine

Problemet med reisende selger er et av de eldste kjente beregningsspørsmålene. Den spør etter den ideelle ruten gjennom en bestemt liste over byer, og minimerer kjørelengden. Til tross for at det virker enkelt, er problemet notorisk vanskelig. Mens du kan bruke brute force for å sjekke alle mulige ruter til du finner den korteste veien, blir en slik strategi uholdbar etter bare en håndfull byer. I stedet kan du bruke en streng matematisk modell kalt lineær programmering, som grovt sett tilnærmer problemet som et sett med ligninger og metodisk sjekker mulige kombinasjoner for å finne den beste løsningen.

Men noen ganger må du optimalisere for problemer som involverer hele tallbeløp. Hva hjelper en fabrikkoptimaliseringsplan som produserer 500.7 sofaer? For dette bruker forskere ofte en variant av lineær programmering kalt heltalls lineær programmering (ILP). Det er populært i applikasjoner som involverer diskrete beslutninger, inkludert produksjonsplanlegging, planlegging av flybesetninger og ruteføring av kjøretøy. "I bunn og grunn er ILP brød og smør for operasjonsforskning både i teori og praksis," sa Santosh Vempala, en informatiker ved Georgia Institute of Technology.

Siden de først formulerte ILP for over 60 år siden, har forskere oppdaget ulike algoritmer som løser ILP-problemer, men de har alle vært relativt trege når det gjelder antall nødvendige trinn. Den beste versjonen de kunne komme opp med — en slags fartsgrense — kommer fra det trivielle tilfellet der problemets variabler (som om en selger besøker en by eller ikke) bare kan anta binære verdier (null eller 1). I dette tilfellet har ILP en kjøretid som skaleres eksponentielt med antall variabler, også kalt dimensjonen. (Hvis det bare er én variabel, tar det bare to trinn for å teste alle mulige kombinasjoner og løse problemet; to variabler betyr fire trinn, tre betyr åtte trinn, og så videre.)

Dessverre, når variablene tar en verdi utover bare null og 1, vokser algoritmens kjøretid mye lenger. Forskere har lenge lurt på om de kunne komme nærmere det trivielle idealet. Fremgangen har vært sakte, med rekord satt på 1980-tallet og bare gradvis forbedringer laget siden.

Men nylig arbeid by Victor Reis, for tiden ved Institute for Advanced Study, og Thomas Rothvoss, ved University of Washington, har tatt det største kjøretidsspranget på flere tiår. Ved å kombinere geometriske verktøy for å begrense de mulige løsningene, skapte de en ny, raskere algoritme for å løse ILP på nesten samme tid som det trivielle binære tilfellet. Resultatet mottok en pris for beste papir i 2023 Grunnlaget for informatikk konferanse.

"Denne nye algoritmen er ekstremt spennende," sa Noah Stephens-Davidowitz, en matematiker og informatiker ved Cornell University. "Det representerer den første [store] forbedringen til ILP-løsere på nesten 40 år."

ILP fungerer ved å transformere et gitt problem til et sett med lineære ligninger som må tilfredsstille noen ulikheter. De spesifikke ligningene er basert på detaljene i det opprinnelige problemet. Men selv om disse detaljene kan variere, forblir den grunnleggende sammensetningen av ILP-problemer den samme, og gir forskere en enkelt måte å angripe en rekke problemer.

Det er ikke dermed sagt at det er lett arbeid. Det var først i 1983 at matematikeren Hendrik Lenstra beviste at det generelle problemet til og med var løsbart, og ga den første algoritmen som kunne gjøre det. Lenstra tenkte på ILP geometrisk. Først gjorde han ulikhetene i hjertet av ILP til en konveks form, for eksempel en hvilken som helst vanlig polygon. Denne formen representerer begrensningene til det individuelle problemet du løser, enten det er sofaproduksjon eller planlegging av flyselskaper, så formens indre tilsvarer alle mulige verdier som kan løse ulikhetene, og dermed problemet. Lenstra kalte denne formen den konvekse kroppen. Problemets dimensjon påvirker dimensjonen til denne formen: Med to variabler tar den form av en flat polygon; i tre dimensjoner er det en Platonisk solid, Og så videre.

Lenstra så for seg alle heltallene som et uendelig sett med rutenettpunkter, kjent i matematikk som et gitter. En todimensjonal versjon ser ut som et hav av prikker, og i tre dimensjoner ser den ut som punktene der stålbjelker i en bygning kobles sammen. Dimensjonen på gitteret avhenger også av dimensjonen til et gitt problem.

For å løse et gitt ILP-problem, viste Lenstra at man bare ser etter hvor de mulige løsningene møter settet med heltall: i skjæringspunktet mellom den konvekse kroppen og gitteret. Og han kom opp med en algoritme som kunne søke uttømmende i denne plassen - men for å være effektiv måtte den noen ganger bryte problemet opp i biter med mindre dimensjoner, og legge til mange trinn til kjøretiden.

I de påfølgende årene undersøkte flere forskere hvordan man kunne få denne algoritmen til å kjøre raskere. I 1988 introduserte Ravi Kannan og László Lovász et konsept kalt dekkradius, lånt fra studiet av feilrettende koder, for å hjelpe den konvekse kroppen og gitteret til å krysse hverandre mer effektivt. Grovt sett sørger dekkradius for at den konvekse kroppen alltid inneholder minst ett heltallspunkt, uansett hvor du plasserer det på gitteret. Som et resultat avgjør størrelsen på dekkradiusen også hvor effektivt du kan løse ILP-problemet.

Så alt kom ned til å bestemme størrelsen på den ideelle dekkradius. Dessverre viste dette seg å være et vanskelig problem i seg selv, og det beste Kannan og Lovász kunne gjøre var å begrense en mulig verdi ved å søke etter øvre og nedre grenser. De viste at den øvre grensen - den maksimale størrelsen på dekningsradiusen - ble skalert opp lineært med dimensjonen. Dette var ganske raskt, men ikke nok til å øke hastigheten på ILP-kjøringen betydelig. I løpet av de neste 30 årene kunne andre forskere bare gjøre det litt bedre.

Det som til slutt hjalp Reis og Rothvoss til å slå gjennom, var et ikke-relatert matematisk resultat som kun fokuserte på gitter. I 2016, Oded Regev og Stephens-Davidowitz viste, faktisk, hvor mange gitterpunkter kan passe innenfor en bestemt form. Reis og Rothvoss brukte dette på andre former, noe som gjorde at de bedre kunne estimere antall gitterpunkter inneholdt i en ILP som dekker radius, og senket den øvre grensen. "Det siste gjennombruddet kom med erkjennelsen av at du faktisk kan gjøre andre typer former," sa Regev.

Denne nye, strammede øvre grensen var en enorm forbedring, som tillot Reis og Rothvoss å oppnå en dramatisk hastighetsøkning av den generelle ILP-algoritmen. Arbeidet deres bringer kjøretiden til (logg n)^O(n), Hvor n er antall variabler og O (n)betyr at den skalerer lineært med n. (Dette uttrykket regnes som "nesten" det samme som kjøretiden for det binære problemet.)

"Det er en triumf i skjæringspunktet mellom matematikk, informatikk og geometri," sa Daniel Dadush fra det nasjonale forskningsinstituttet CWI i Nederland, som var med på å pionere algoritmen Reis og Rothvoss brukte for å måle ILP-kjøretiden.

Foreløpig har den nye algoritmen faktisk ikke blitt brukt til å løse noen logistiske problemer, siden det ville kreve for mye arbeid å oppdatere dagens programmer for å bruke den. Men for Rothvoss er det ved siden av poenget. "Det handler om den teoretiske forståelsen av et problem som har grunnleggende anvendelser," sa han.

Når det gjelder om beregningseffektiviteten til ILP kan forbedres ytterligere, håper forskerne fortsatt på at de vil fortsette å nærme seg den ideelle kjøretiden - men ikke når som helst snart. "Det ville kreve en fundamentalt ny idé," sa Vempala.