Il problema del commesso viaggiatore è uno dei più antichi problemi computazionali conosciuti. Richiede il percorso ideale attraverso un determinato elenco di città, riducendo al minimo il chilometraggio. Nonostante sembri semplice, il problema è notoriamente difficile. Sebbene sia possibile utilizzare la forza bruta per controllare tutti i percorsi possibili fino a trovare il percorso più breve, una strategia del genere diventa insostenibile dopo solo una manciata di città. Puoi invece applicare un modello matematico rigoroso chiamato programmazione lineare, che approssima approssimativamente il problema come un insieme di equazioni e controlla metodicamente le possibili combinazioni per trovare la soluzione migliore.

Ma a volte è necessario ottimizzare per problemi che coinvolgono importi di numeri interi. A cosa serve un piano di ottimizzazione di una fabbrica che produce 500.7 divani? Per questo, i ricercatori spesso si rivolgono a una variante della programmazione lineare chiamata programmazione lineare intera (ILP). È popolare nelle applicazioni che implicano decisioni discrete, tra cui la pianificazione della produzione, la pianificazione dell'equipaggio delle compagnie aeree e il routing dei veicoli. "Fondamentalmente, l'ILP è il pane quotidiano della ricerca operativa sia in teoria che in pratica", ha affermato Santosh Vempala, uno scienziato informatico presso il Georgia Institute of Technology.

Da quando hanno formulato per la prima volta l'ILP oltre 60 anni fa, i ricercatori hanno scoperto vari algoritmi che risolvono i problemi ILP, ma sono stati tutti relativamente lenti in termini di numero di passaggi richiesti. La versione migliore che sono riusciti a trovare - una sorta di limite di velocità - viene dal caso banale in cui le variabili del problema (ad esempio se un venditore visita o meno una città) possono assumere solo valori binari (zero o 1). In questo caso, ILP ha un runtime che scala esponenzialmente con il numero di variabili, chiamato anche dimensione. (Se c'è solo una variabile, sono necessari solo due passaggi per testare ogni possibile combinazione e risolvere il problema; due variabili significano quattro passaggi, tre significano otto passaggi e così via.)

Sfortunatamente, una volta che le variabili assumono un valore superiore a zero e 1, il tempo di esecuzione dell'algoritmo aumenta molto. I ricercatori si chiedono da tempo se potessero avvicinarsi a questo ideale banale. I progressi sono stati lenti, con il record ambientato negli anni '1980 e solo incrementale miglioramenti fatto da allora.

Ma recente lavoro by Vittorio Reis, attualmente presso l'Istituto per gli Studi Avanzati, e Tommaso Rothvoss, presso l'Università di Washington, ha compiuto il più grande salto di runtime degli ultimi decenni. Combinando strumenti geometrici per limitare le possibili soluzioni, hanno creato un nuovo algoritmo più veloce per risolvere l'ILP quasi nello stesso tempo del banale caso binario. Il risultato ha ricevuto il premio best-paper al concorso 2023 Fondamenti dell'informatica conferenza.

"Questo nuovo algoritmo è estremamente entusiasmante", ha affermato Noah Stephens-Davidowitz, matematico e informatico della Cornell University. "Rappresenta il primo [importante] miglioramento dei solutori ILP in quasi 40 anni."

L'ILP funziona trasformando un dato problema in un insieme di equazioni lineari che devono soddisfare alcune disuguaglianze. Le equazioni specifiche si basano sui dettagli del problema originale. Ma anche se questi dettagli possono differire, la composizione di base dei problemi ILP rimane la stessa, offrendo ai ricercatori un unico modo per affrontare una moltitudine di problemi.

Questo non vuol dire che sia un lavoro facile. Fu solo nel 1983 che il matematico Hendrik Lenstra dimostrato che il problema generale fosse addirittura risolvibile, fornendo il primo algoritmo in grado di farlo. Lenstra ha pensato all'ILP in modo geometrico. In primo luogo, ha trasformato le disuguaglianze alla base dell’ILP in una forma convessa, come qualsiasi poligono regolare. Questa forma rappresenta i vincoli del singolo problema che stai risolvendo, che si tratti della produzione di divani o della pianificazione di una compagnia aerea, quindi l'interno della forma corrisponde a tutti i possibili valori che potrebbero risolvere le disuguaglianze e quindi il problema. Lenstra chiamò questa forma corpo convesso. La dimensione del problema influenza la dimensione di questa forma: con due variabili assume la forma di un poligono piatto; in tre dimensioni è a Solido platonico, E così via.

Lenstra immaginò poi tutti i numeri interi come un insieme infinito di punti della griglia, noto in matematica come reticolo. Una versione bidimensionale sembra un mare di punti, mentre in tre dimensioni assomiglia ai punti in cui si collegano le travi di acciaio di un edificio. La dimensione del reticolo dipende anche dalla dimensione di un dato problema.

Per risolvere un dato problema ILP, Lenstra ha mostrato che basta cercare dove le possibili soluzioni incontrano l'insieme degli interi: all'intersezione del corpo convesso e del reticolo. E ha ideato un algoritmo in grado di effettuare ricerche esaustive in questo spazio, ma per essere efficace a volte doveva suddividere il problema in parti di dimensioni più piccole, aggiungendo molti passaggi al tempo di esecuzione.

Negli anni successivi, diversi ricercatori esplorarono come rendere questo algoritmo più veloce. Nel 1988, Ravi Kannan e László Lovász introdussero un concetto chiamato raggio di copertura, preso in prestito dallo studio di codici di correzione degli errori, per aiutare il corpo convesso e il reticolo a intersecarsi in modo più efficiente. In parole povere, il raggio di copertura fa sì che il corpo convesso contenga sempre almeno un punto intero, indipendentemente da dove lo si posiziona sul reticolo. Di conseguenza, la dimensione del raggio di copertura determina anche l’efficienza con cui è possibile risolvere il problema ILP.

Quindi tutto si è ridotto a determinare la dimensione del raggio di copertura ideale. Sfortunatamente, questo si è rivelato un problema di per sé difficile, e il meglio che Kannan e Lovász hanno potuto fare è stato restringere un possibile valore cercando i limiti superiore e inferiore. Hanno dimostrato che il limite superiore – la dimensione massima del raggio di copertura – aumentava linearmente con la dimensione. Questo è stato abbastanza veloce, ma non abbastanza per accelerare in modo significativo il tempo di esecuzione dell'ILP. Nei successivi 30 anni, altri ricercatori avrebbero potuto fare solo leggermente meglio.

Ciò che alla fine aiutò Reis e Rothvoss a sfondare fu un risultato matematico non correlato che si concentrava esclusivamente sui reticoli. Nel 2016, Oded Regev e Stephens-Davidowitz ha mostrato, in effetti, quanti punti del reticolo potrebbero rientrare in una forma specifica. Reis e Rothvoss lo hanno applicato ad altre forme, il che ha permesso loro di stimare meglio il numero di punti reticolari contenuti in un raggio di copertura ILP, abbassando il limite superiore. "L'ultima svolta è arrivata con la consapevolezza che si possono effettivamente realizzare altri tipi di forme", ha detto Regev.

Questo nuovo limite superiore più rigido ha rappresentato un notevole miglioramento, consentendo a Reis e Rothvoss di ottenere una notevole accelerazione dell’algoritmo ILP complessivo. Il loro lavoro porta il runtime a (log n)^O(n), Dove n è il numero di variabili e O (n)significa che si ridimensiona linearmente con n. (Questa espressione è considerata “quasi” uguale al tempo di esecuzione del problema binario.)

"È un trionfo all'intersezione tra matematica, informatica e geometria", ha detto Daniele Dadush dell’istituto di ricerca nazionale CWI nei Paesi Bassi, che ha contribuito a creare l’algoritmo utilizzato da Reis e Rothvoss per misurare il tempo di esecuzione dell’ILP.

Per ora il nuovo algoritmo non è stato effettivamente utilizzato per risolvere alcun problema logistico, poiché per poterlo utilizzare occorrerebbe troppo lavoro di aggiornamento dei programmi odierni. Ma per Rothvoss questo non è il punto. "Si tratta della comprensione teorica di un problema che ha applicazioni fondamentali", ha affermato.

Per quanto riguarda la possibilità di migliorare ulteriormente l'efficienza computazionale dell'ILP, i ricercatori sperano ancora di continuare ad avvicinarsi al tempo di esecuzione ideale, ma non in tempi brevi. “Ciò richiederebbe un’idea fondamentalmente nuova”, ha detto Vempala.