Forskare närmar sig ny hastighetsgräns för seminalproblem | Quanta Magazine

Problemet med resande säljare är en av de äldsta kända beräkningsfrågorna. Den frågar efter den idealiska rutten genom en viss lista med städer, vilket minimerar körsträckan. Trots att det verkar enkelt är problemet notoriskt svårt. Även om du kan använda brute force för att kontrollera alla möjliga rutter tills du hittar den kortaste vägen, blir en sådan strategi ohållbar efter bara en handfull städer. Istället kan du tillämpa en rigorös matematisk modell som kallas linjär programmering, som ungefär approximerar problemet som en uppsättning ekvationer och metodiskt kontrollerar möjliga kombinationer för att hitta den bästa lösningen.

Men ibland måste du optimera för problem som involverar helnummerbelopp. Vad hjälper en fabriksoptimeringsplan som tillverkar 500.7 soffor? För detta vänder sig forskare ofta till en variant av linjär programmering som kallas heltals linjär programmering (ILP). Det är populärt i applikationer som involverar diskreta beslut, inklusive produktionsplanering, schemaläggning av flygbesättningar och fordonsdirigering. "I grund och botten är ILP brödet för operationsforskning både i teori och praktik," sa Santosh Vempala, en datavetare vid Georgia Institute of Technology.

Sedan de först formulerade ILP för över 60 år sedan, har forskare upptäckt olika algoritmer som löser ILP-problem, men de har alla varit relativt långsamma när det gäller antalet steg som krävs. Den bästa versionen de kunde komma på — en sorts hastighetsbegränsning — kommer från det triviala fallet där problemets variabler (som huruvida en säljare besöker en stad eller inte) bara kan anta binära värden (noll eller 1). I det här fallet har ILP en körtid som skalas exponentiellt med antalet variabler, även kallad dimensionen. (Om det bara finns en variabel tar det bara två steg för att testa alla möjliga kombinationer och lösa problemet; två variabler betyder fyra steg, tre betyder åtta steg och så vidare.)

Tyvärr, när variablerna tar ett värde bortom bara noll och 1, växer algoritmens körtid mycket längre. Forskare har länge undrat om de kunde komma närmare det triviala idealet. Framstegen har varit långsamma, med post utspelar sig på 1980-talet och endast stegvis förbättringar gjort sedan dess.

Men nyligen arbete by Victor Reis, för närvarande vid Institutet för avancerade studier, och Thomas Rothvoss, vid University of Washington, har gjort det största körtidssprånget på årtionden. Genom att kombinera geometriska verktyg för att begränsa de möjliga lösningarna skapade de en ny, snabbare algoritm för att lösa ILP i nästan samma tid som det triviala binära fallet. Resultatet fick priset för bästa papper 2023 Grunderna för datavetenskap konferens.

"Denna nya algoritm är extremt spännande," sa Noah Stephens-Davidowitz, en matematiker och datavetare vid Cornell University. "Det representerar den första [stora] förbättringen av ILP-lösare på nästan 40 år."

ILP fungerar genom att omvandla ett givet problem till en uppsättning linjära ekvationer som måste uppfylla vissa ojämlikheter. De specifika ekvationerna är baserade på detaljerna i det ursprungliga problemet. Men även om dessa detaljer kan skilja sig åt, förblir den grundläggande sammansättningen av ILP-problem densamma, vilket ger forskare ett enda sätt att attackera en mängd problem.

Därmed inte sagt att det är lätt arbete. Det var inte förrän 1983 som matematikern Hendrik Lenstra visat att det allmänna problemet till och med var lösbart, vilket gav den första algoritmen som kunde göra det. Lenstra tänkte på ILP geometriskt. Först gjorde han ojämlikheterna i hjärtat av ILP till en konvex form, som vilken vanlig polygon som helst. Denna form representerar begränsningarna för det individuella problemet du löser, oavsett om det är soffproduktion eller flygplanering, så formens inre motsvarar alla möjliga värden som skulle kunna lösa ojämlikheterna, och därmed problemet. Lenstra kallade denna form för den konvexa kroppen. Problemets dimension påverkar dimensionen av denna form: Med två variabler tar den formen av en platt polygon; i tre dimensioner är det en Platoniskt solid, Och så vidare.

Lenstra föreställde sig sedan alla heltal som en oändlig uppsättning rutnätspunkter, kända i matematiken som ett gitter. En tvådimensionell version ser ut som ett hav av prickar, och i tre dimensioner ser den ut som punkterna där stålbalkar i en byggnad ansluter. Gallrets dimension beror också på dimensionen av ett givet problem.

För att lösa ett givet ILP-problem visade Lenstra att man bara letar efter var de möjliga lösningarna möter uppsättningen av heltal: i skärningspunkten mellan den konvexa kroppen och gittret. Och han kom på en algoritm som kunde söka igenom det här utrymmet uttömmande - men för att vara effektiv var den ibland tvungen att dela upp problemet i mindre dimensioner och lägga till många steg till körtiden.

Under de följande åren undersökte flera forskare hur man kan få denna algoritm att köra snabbare. 1988 introducerade Ravi Kannan och László Lovász ett koncept som kallas täckningsradien, lånad från studiet av felkorrigerande koder, för att hjälpa den konvexa kroppen och gittret att skära varandra mer effektivt. Grovt sett ser täckradien till att den konvexa kroppen alltid innehåller minst en heltalspunkt, oavsett var du placerar den på gallret. Som ett resultat avgör storleken på täckningsradien också hur effektivt du kan lösa ILP-problemet.

Så det hela handlade om att bestämma storleken på den ideala täckningsradien. Tyvärr visade detta sig vara ett svårt problem i sig, och det bästa Kannan och Lovász kunde göra var att begränsa ett möjligt värde genom att söka efter övre och nedre gränser. De visade att den övre gränsen - den maximala storleken på täckningsradien - skalas upp linjärt med dimensionen. Detta var ganska snabbt, men inte tillräckligt för att avsevärt snabba upp ILP-körtiden. Under de kommande 30 åren kunde andra forskare bara göra något bättre.

Det som i slutändan hjälpte Reis och Rothvoss att slå igenom var ett orelaterade matematiskt resultat som enbart fokuserade på gitter. 2016, Oded Regev och Stephens-Davidowitz visade, i själva verket, hur många gitterpunkter kan passa inom en specifik form. Reis och Rothvoss tillämpade detta på andra former, vilket gjorde det möjligt för dem att bättre uppskatta antalet gitterpunkter som finns i en ILP som täcker radien, vilket sänker den övre gränsen. "Det senaste genombrottet kom med insikten att du faktiskt kan göra andra typer av former," sa Regev.

Denna nya skärpta övre gräns var en enorm förbättring, vilket gjorde det möjligt för Reis och Rothvoss att uppnå en dramatisk hastighet på den övergripande ILP-algoritmen. Deras arbete tar körtiden till (logg n)^O(n)Där n är antalet variabler och O (n)betyder att den skalas linjärt med n. (Detta uttryck anses "nästan" vara detsamma som körtiden för det binära problemet.)

"Det är en triumf i skärningspunkten mellan matematik, datavetenskap och geometri," sa Daniel Dadush från det nationella forskningsinstitutet CWI i Nederländerna, som hjälpte till att banbryta algoritmen Reis och Rothvoss använde för att mäta ILP-körtiden.

För närvarande har den nya algoritmen faktiskt inte använts för att lösa några logistiska problem, eftersom det skulle krävas för mycket arbete att uppdatera dagens program för att kunna använda den. Men för Rothvoss är det vidrigt. "Det handlar om den teoretiska förståelsen av ett problem som har grundläggande tillämpningar," sa han.

När det gäller huruvida beräkningseffektiviteten hos ILP kan förbättras ytterligare, är forskare fortfarande hoppfulla att de kommer att fortsätta närma sig den ideala körtiden - men inte när som helst snart. "Det skulle kräva en i grunden ny idé," sa Vempala.