Forskere nærmer sig ny hastighedsgrænse for sædproblem | Quanta Magasinet

Problemet med den rejsende sælger er et af de ældste kendte beregningsspørgsmål. Den beder om den ideelle rute gennem en bestemt liste over byer, hvilket minimerer kilometertal. Trods det tilsyneladende simpelt, er problemet notorisk svært. Selvom du kan bruge brute force til at tjekke alle mulige ruter, indtil du finder den korteste vej, bliver en sådan strategi uholdbar efter blot en håndfuld byer. I stedet kan du anvende en streng matematisk model kaldet lineær programmering, som groft tilnærmer problemet som et sæt ligninger og metodisk kontrollerer de mulige kombinationer for at finde den bedste løsning.

Men nogle gange er du nødt til at optimere for problemer, der involverer hele talbeløb. Hvad hjælper en fabriksoptimeringsplan, der fremstiller 500.7 sofaer? Til dette søger forskere ofte en variant af lineær programmering kaldet heltals lineær programmering (ILP). Det er populært i applikationer, der involverer diskrete beslutninger, herunder produktionsplanlægning, flyselskabets besætningsplanlægning og ruteplanlægning af køretøjer. "Dybest set er ILP brød og smør for operationsforskning både i teori og praksis," sagde Santosh Vempala, en datalog ved Georgia Institute of Technology.

Siden de først formulerede ILP over 60 år siden, har forskere opdaget forskellige algoritmer, der løser ILP-problemer, men de har alle været relativt langsomme med hensyn til antallet af nødvendige trin. Den bedste version, de kunne finde på - en slags hastighedsgrænse - kommer fra det trivielle tilfælde, hvor problemets variabler (såsom om en sælger besøger en by eller ej) kun kan antage binære værdier (nul eller 1). I dette tilfælde har ILP en runtime, der skaleres eksponentielt med antallet af variable, også kaldet dimensionen. (Hvis der kun er én variabel, tager det kun to trin at teste alle mulige kombinationer og løse problemet; to variable betyder fire trin, tre betyder otte trin og så videre.)

Desværre, når variablerne tager en værdi ud over blot nul og 1, vokser algoritmens køretid meget længere. Forskere har længe spekuleret på, om de kunne komme tættere på det trivielle ideal. Fremskridtet har været langsomt, med optage foregår i 1980'erne og kun gradvist forbedringer lavet siden.

Men for nylig arbejde by Victor Reis, i øjeblikket ved Institute for Advanced Study, og Thomas Rothvoss, ved University of Washington, har taget det største runtime-spring i årtier. Ved at kombinere geometriske værktøjer for at begrænse de mulige løsninger, skabte de en ny, hurtigere algoritme til at løse ILP på næsten samme tid som det trivielle binære tilfælde. Resultatet modtog en pris for bedste papir ved 2023 Grundlaget for datalogi konference.

"Denne nye algoritme er ekstremt spændende," sagde Noah Stephens-Davidowitz, en matematiker og datalog ved Cornell University. "Det repræsenterer den første [store] forbedring af ILP-løsere i næsten 40 år."

ILP fungerer ved at transformere et givet problem til et sæt lineære ligninger, der skal tilfredsstille nogle uligheder. De specifikke ligninger er baseret på detaljerne i det oprindelige problem. Men selvom disse detaljer kan være forskellige, forbliver den grundlæggende sammensætning af ILP-problemer den samme, hvilket giver forskere en enkelt måde at angribe en lang række problemer på.

Dermed ikke sagt, at det er let arbejde. Det var først i 1983, at matematikeren Hendrik Lenstra bevist at det generelle problem endda var løseligt, hvilket gav den første algoritme, der kunne gøre det. Lenstra tænkte over ILP geometrisk. For det første forvandlede han ulighederne i hjertet af ILP til en konveks form, såsom enhver almindelig polygon. Denne form repræsenterer begrænsningerne for det individuelle problem, du løser, uanset om det er sofaproduktion eller flyveplanlægning, så formens indre svarer til alle mulige værdier, der kunne løse ulighederne og dermed problemet. Lenstra kaldte denne form for den konvekse krop. Problemets dimension påvirker dimensionen af ​​denne form: Med to variable har den form af en flad polygon; i tre dimensioner er det en Platonisk solid, og så videre.

Lenstra forestillede sig derefter alle de heltal som et uendeligt sæt af gitterpunkter, kendt i matematik som et gitter. En todimensionel version ligner et hav af prikker, og i tre dimensioner ligner den de punkter, hvor stålbjælker i en bygning forbinder. Dimensionen af ​​gitteret afhænger også af dimensionen af ​​et givent problem.

For at løse et givent ILP-problem, viste Lenstra, at man bare kigger efter, hvor de mulige løsninger møder sættet af heltal: i skæringspunktet mellem det konvekse legeme og gitteret. Og han kom op med en algoritme, der kunne søge i dette rum udtømmende - men for at være effektiv måtte den nogle gange bryde problemet op i mindre dimensioner, hvilket tilføjede mange trin til kørselstiden.

I de følgende år undersøgte flere forskere, hvordan man kunne få denne algoritme til at køre hurtigere. I 1988 introducerede Ravi Kannan og László Lovász et koncept kaldet den dækkende radius, Lånte fra studiet af fejlkorrigerende koder, for at hjælpe den konvekse krop og gitteret til at skære mere effektivt. Groft sagt sørger dækningsradius for, at det konvekse legeme altid indeholder mindst ét ​​heltalspunkt, uanset hvor du placerer det på gitteret. Som følge heraf bestemmer størrelsen af ​​dækningsradius også, hvor effektivt du kan løse ILP-problemet.

Så det hele handlede om at bestemme størrelsen af ​​den ideelle dækningsradius. Desværre viste dette sig at være et hårdt problem i sig selv, og det bedste Kannan og Lovász kunne gøre var at indsnævre en mulig værdi ved at søge efter øvre og nedre grænser. De viste, at den øvre grænse - den maksimale størrelse af dækningsradius - skaleres op lineært med dimensionen. Dette var ret hurtigt, men ikke nok til at fremskynde ILP-kørselstiden markant. I løbet af de næste 30 år kunne andre forskere kun gøre det lidt bedre.

Det, der i sidste ende hjalp Reis og Rothvoss med at bryde igennem, var et ikke-relateret matematisk resultat, der udelukkende fokuserede på gitter. I 2016, Oded Regev og Stephens-Davidowitz viste, i virkeligheden, hvor mange gitterpunkter kan passe inden for en bestemt form. Reis og Rothvoss anvendte dette på andre former, hvilket gjorde det muligt for dem bedre at estimere antallet af gitterpunkter indeholdt i en ILP, der dækker radius, hvilket sænker den øvre grænse. "Det seneste gennembrud kom med erkendelsen af, at du faktisk kan lave andre former for former," sagde Regev.

Denne nye strammede øvre grænse var en enorm forbedring, der gjorde det muligt for Reis og Rothvoss at opnå en dramatisk fremskyndelse af den overordnede ILP-algoritme. Deres arbejde bringer kørselstiden til (log n)^O(n)Hvor n er antallet af variable og O (n)betyder, at den skalerer lineært med n. (Dette udtryk betragtes som "næsten" det samme som kørselstiden for det binære problem.)

"Det er en triumf i skæringspunktet mellem matematik, datalogi og geometri," sagde Daniel Dadush fra det nationale forskningsinstitut CWI i Holland, som var med til at pionere den algoritme Reis og Rothvoss brugte til at måle ILP-runtiden.

Indtil videre er den nye algoritme faktisk ikke blevet brugt til at løse nogen logistiske problemer, da det ville kræve for meget arbejde at opdatere nutidens programmer at gøre brug af det. Men for Rothvoss er det ved siden af ​​sagen. "Det handler om den teoretiske forståelse af et problem, der har grundlæggende anvendelser," sagde han.

Med hensyn til om ILP's beregningseffektivitet kan forbedres yderligere, håber forskerne stadig på, at de vil blive ved med at nærme sig den ideelle kørselstid - men ikke når som helst snart. "Det ville kræve en grundlæggende ny idé," sagde Vempala.