Nel mondo della logistica e di altri settori, la ricerca di soluzioni ottimali per problemi complessi di ottimizzazione è una sfida costante. Le aziende si affidano a software specializzati, noti come risolutori di programmazione lineare intera mista (MILP), per trovare il percorso più efficiente per la distribuzione globale dei pacchi o per la gestione della rete elettrica. Tuttavia, questi software possono impiegare ore o addirittura giorni per arrivare a una soluzione, spesso costringendo le aziende ad accettare risultati non ideali a causa dei limiti di tempo.
Recentemente, un gruppo di ricercatori del MIT e dell’ETH Zurigo ha sviluppato una tecnica che combina l’apprendimento automatico con l’ottimizzazione tradizionale, accelerando il processo di risoluzione dei problemi MILP fino al 70%, migliorando così l’efficienza in vari ambiti. Questo nuovo approccio consente alle aziende di personalizzare un risolutore MILP generico per problemi specifici, utilizzando i propri dati per trovare soluzioni ottimali più rapidamente o, per problemi particolarmente complessi, soluzioni migliori in un tempo gestibile.
I problemi MILP presentano un numero esponenziale di soluzioni potenziali, rendendoli estremamente complessi e difficili da risolvere. Questi problemi sono classificati come NP-hard, il che significa che è altamente improbabile trovare un algoritmo efficiente per risolverli. Di conseguenza, per problemi di grandi dimensioni, l’obiettivo è raggiungere prestazioni subottimali. I risolutori MILP utilizzano una serie di tecniche e trucchi pratici per ottenere soluzioni ragionevoli in un tempo accettabile.
I ricercatori hanno ideato un meccanismo di filtraggio che riduce lo spazio di ricerca dei separatori da oltre 130.000 combinazioni potenziali a circa 20 opzioni. Questo meccanismo si basa sul principio dei rendimenti marginali decrescenti, secondo cui il maggior beneficio deriva da un piccolo insieme di algoritmi e l’aggiunta di algoritmi aggiuntivi non porta a miglioramenti significativi. Successivamente, utilizzano un modello di apprendimento automatico per scegliere la migliore combinazione di algoritmi tra le 20 opzioni rimanenti.
Il modello è addestrato con un dataset specifico per il problema di ottimizzazione dell’utente, imparando così a scegliere gli algoritmi più adatti al compito specifico. Aziende come FedEx, che hanno risolto problemi di routing molte volte in passato, possono trarre vantaggio da dati reali derivati da esperienze precedenti per ottenere soluzioni migliori rispetto a partire da zero ogni volta. Il processo di apprendimento iterativo del modello, noto come banditi contestuali, una forma di apprendimento per rinforzo, comporta la scelta di una soluzione potenziale, ricevendo feedback sulla sua efficacia e poi tentando nuovamente di trovare una soluzione migliore.
Questo approccio basato sui dati ha accelerato i risolutori MILP tra il 30 e il 70 percento senza alcuna perdita di accuratezza. Inoltre, l’accelerazione è stata simile quando applicata sia a un risolutore open-source più semplice che a un risolutore commerciale più potente.
In futuro, i ricercatori intendono applicare questo approccio a problemi MILP ancora più complessi, dove la raccolta di dati etichettati per addestrare il modello potrebbe essere particolarmente impegnativa. Potrebbero addestrare il modello su un dataset più piccolo e poi adattarlo per affrontare un problema di ottimizzazione molto più grande. Inoltre, sono interessati a interpretare il modello appreso per comprendere meglio l’efficacia dei diversi algoritmi separatori.