Het handelsreizigersprobleem is een van de oudste bekende computationele vragen. Er wordt gevraagd om de ideale route door een bepaalde lijst met steden, waarbij het aantal kilometers wordt geminimaliseerd. Hoewel het probleem eenvoudig lijkt, is het notoir moeilijk. Hoewel je brute kracht kunt gebruiken om alle mogelijke routes te controleren totdat je het kortste pad hebt gevonden, wordt een dergelijke strategie al na een handvol steden onhoudbaar. In plaats daarvan kun je een rigoureus wiskundig model toepassen, genaamd lineaire programmering, dat het probleem grofweg benadert als een reeks vergelijkingen en de mogelijke combinaties methodisch controleert om de beste oplossing te vinden.

Maar soms moet u optimaliseren voor problemen met gehele getallen. Wat heb je aan een fabrieksoptimalisatieplan dat 500.7 banken produceert? Hiervoor wenden onderzoekers zich vaak tot een variant van lineaire programmering genaamd integer lineaire programmering (ILP). Het is populair in toepassingen waarbij discrete beslissingen nodig zijn, waaronder productieplanning, personeelsplanning van luchtvaartmaatschappijen en voertuigroutering. “In principe is ILP het brood en de boter van operationeel onderzoek, zowel in theorie als in de praktijk”, zegt hij Santosh Vempala, een computerwetenschapper aan het Georgia Institute of Technology.

Sinds ze voor het eerst ILP formuleerden meer dan 60 jaar geledenhebben onderzoekers verschillende algoritmen ontdekt die ILP-problemen oplossen, maar ze waren allemaal relatief traag wat betreft het aantal vereiste stappen. De beste versie die ze konden bedenken – een soort snelheidslimiet – komt voort uit het triviale geval waarin de variabelen van het probleem (zoals of een verkoper een stad bezoekt of niet) alleen binaire waarden kunnen aannemen (nul of 1). In dit geval heeft ILP een looptijd die exponentieel schaalt met het aantal variabelen, ook wel de dimensie genoemd. (Als er maar één variabele is, zijn er slechts twee stappen nodig om elke mogelijke combinatie te testen en het probleem op te lossen; twee variabelen betekenen vier stappen, drie betekenen acht stappen, enzovoort.)

Helaas, zodra de variabelen een waarde aannemen die verder gaat dan nul en 1, wordt de looptijd van het algoritme veel langer. Onderzoekers vragen zich al lang af of ze dichter bij het triviale ideaal kunnen komen. De vooruitgang verliep traag, met de record die zich in de jaren tachtig afspeelde en slechts incrementeel was verbeteringen sindsdien gemaakt.

Maar recent werk by Victor Reis, momenteel bij het Institute for Advanced Study, en Thomas Rothvoss, aan de Universiteit van Washington, heeft de grootste looptijdsprong in decennia gemaakt. Door geometrische hulpmiddelen te combineren om de mogelijke oplossingen te beperken, creëerden ze een nieuw, sneller algoritme voor het oplossen van ILP in bijna dezelfde tijd als het triviale binaire geval. Het resultaat ontving op de 2023 een prijs voor beste papier Grondslagen van de informatica conferentie.

"Dit nieuwe algoritme is buitengewoon opwindend", zei hij Noah Stephens-Davidowitz, een wiskundige en computerwetenschapper aan de Cornell University. “Het vertegenwoordigt de eerste [grote] verbetering voor ILP-oplossers in bijna 40 jaar.”

ILP werkt door een bepaald probleem om te zetten in een reeks lineaire vergelijkingen die aan een aantal ongelijkheden moeten voldoen. De specifieke vergelijkingen zijn gebaseerd op de details van het oorspronkelijke probleem. Maar hoewel deze details kunnen verschillen, blijft de basis van ILP-problemen hetzelfde, waardoor onderzoekers één enkele manier krijgen om een ​​groot aantal problemen aan te pakken.

Dat wil niet zeggen dat het gemakkelijk werk is. Pas in 1983 kwam de wiskundige Hendrik Lenstra bewezen dat het algemene probleem zelfs oplosbaar was en het eerste algoritme opleverde dat dit kon. Lenstra dacht geometrisch na over ILP. Ten eerste veranderde hij de ongelijkheden die de kern vormen van ILP in een convexe vorm, zoals elke regelmatige veelhoek. Deze vorm vertegenwoordigt de beperkingen van het individuele probleem dat u oplost, of het nu gaat om de productie van banken of de planning van luchtvaartmaatschappijen, dus het interieur van de vorm komt overeen met alle mogelijke waarden die de ongelijkheden, en dus het probleem, zouden kunnen oplossen. Lenstra noemde deze vorm het bolle lichaam. De dimensie van het probleem beïnvloedt de dimensie van deze vorm: met twee variabelen neemt deze de vorm aan van een platte veelhoek; in drie dimensies is het een Platonische vaste stof, Enzovoort.

Lenstra stelde zich vervolgens alle gehele getallen voor als een oneindige reeks rasterpunten, in de wiskunde bekend als een rooster. Een tweedimensionale versie ziet eruit als een zee van stippen, en in drie dimensies lijkt het op de punten waar stalen balken in een gebouw met elkaar verbinden. De afmeting van het rooster hangt ook af van de afmeting van een bepaald probleem.

Om een ​​bepaald ILP-probleem op te lossen, liet Lenstra zien dat je gewoon zoekt naar waar de mogelijke oplossingen samenkomen met de reeks gehele getallen: op het snijpunt van het convexe lichaam en het rooster. En hij bedacht een algoritme dat deze ruimte uitputtend kon doorzoeken, maar om effectief te zijn moest het het probleem soms opdelen in stukjes van kleinere afmetingen, waardoor veel stappen aan de looptijd werden toegevoegd.

In de daaropvolgende jaren onderzochten verschillende onderzoekers hoe ze dit algoritme sneller konden laten werken. In 1988 introduceerden Ravi Kannan en László Lovász een concept genaamd de dekkingsradius, geleend uit de studie van foutcorrigerende codes, om het convexe lichaam en het rooster efficiënter te laten kruisen. Grofweg zorgt de dekkingsradius ervoor dat het bolle lichaam altijd minstens één geheel punt bevat, ongeacht waar u het op het rooster plaatst. Hierdoor bepaalt de grootte van de dekkingsradius ook hoe efficiënt u het ILP-probleem kunt oplossen.

Het kwam dus allemaal neer op het bepalen van de grootte van de ideale dekkingsradius. Helaas bleek dit op zichzelf een moeilijk probleem te zijn, en het beste wat Kannan en Lovász konden doen was een mogelijke waarde beperken door te zoeken naar boven- en ondergrenzen. Ze toonden aan dat de bovengrens – de maximale grootte van de dekkingsradius – lineair opschaalde met de afmeting. Dit was behoorlijk snel, maar niet genoeg om de ILP-runtime aanzienlijk te versnellen. In de komende dertig jaar zouden andere onderzoekers het slechts een klein beetje beter kunnen doen.

Wat Reis en Rothvoss uiteindelijk hielp doorbreken was een niet-gerelateerd wiskundig resultaat dat zich puur op roosters concentreerde. In 2016 Oded Regev en Stephens-Davidowitz vertoonde, in feite, hoeveel roosterpunten er binnen een specifieke vorm zouden kunnen passen. Reis en Rothvoss pasten dit toe op andere vormen, waardoor ze het aantal roosterpunten in een ILP-dekkingsradius beter konden inschatten, waardoor de bovengrens werd verlaagd. “De nieuwste doorbraak kwam met het besef dat je ook andere soorten vormen kunt maken”, zegt Regev.

Deze nieuwe, aangescherpte bovengrens was een enorme verbetering, waardoor Reis en Rothvoss een dramatische versnelling van het algehele ILP-algoritme konden bereiken. Hun werk brengt de runtime naar (log n)^O(n), Waar n is het aantal variabelen en O (n)betekent dat het lineair schaalt met n. (Deze uitdrukking wordt beschouwd als “bijna” hetzelfde als de looptijd van het binaire probleem.)

"Het is een triomf op het kruispunt van wiskunde, informatica en meetkunde", zei hij Daniël Dadush van het nationale onderzoeksinstituut CWI in Nederland, die hielp bij het pionieren van het algoritme dat Reis en Rothvoss gebruikten om de ILP-runtime te meten.

Voorlopig is het nieuwe algoritme nog niet daadwerkelijk gebruikt om logistieke problemen op te lossen, omdat het te veel werk zou kosten om de huidige programma's te updaten om er gebruik van te kunnen maken. Maar voor Rothvoss doet dat er niet toe. “Het gaat om het theoretisch begrip van een probleem dat fundamentele toepassingen heeft,” zei hij.

Wat betreft de vraag of de rekenefficiëntie van ILP verder kan worden verbeterd, hebben onderzoekers nog steeds hoop dat ze de ideale looptijd zullen blijven benaderen – maar niet op korte termijn. “Dat zou een fundamenteel nieuw idee vereisen”, zei Vempala.