[ad_1]
Mentre Babbo Natale può avere una slitta magica e nove coraggiose renne per aiutarlo a consegnare i regali, per aziende come FedEx, il problema di ottimizzazione dell’instradamento efficiente dei pacchetti vacanza è così complicato che spesso utilizzano software specializzati per trovare una soluzione.
Questo software, chiamato risolutore di programmazione lineare mista intera (MILP), divide un enorme problema di ottimizzazione in parti più piccole e utilizza algoritmi generici per cercare di trovare la soluzione migliore. Tuttavia, il risolutore potrebbe impiegare ore – o addirittura giorni – per arrivare a una soluzione.
Il processo è così oneroso che un’azienda spesso è costretta a fermare il software in corso d’opera, accettando una soluzione che non è l’ideale ma la migliore che potrebbe essere generata in un determinato periodo di tempo.
I ricercatori del MIT e dell’ETH di Zurigo hanno utilizzato l’apprendimento automatico per accelerare i tempi.
Hanno identificato un passaggio intermedio chiave nei solutori MILP che ha così tante soluzioni potenziali che richiede un’enorme quantità di tempo per essere risolto, il che rallenta l’intero processo. I ricercatori hanno utilizzato una tecnica di filtraggio per semplificare questo passaggio, quindi hanno utilizzato l’apprendimento automatico per trovare la soluzione ottimale per un tipo specifico di problema.
Il loro approccio basato sui dati consente a un’azienda di utilizzare i propri dati per adattare un risolutore MILP generico al problema in questione.
Questa nuova tecnica ha accelerato i solutori MILP tra il 30 e il 70%, senza alcun calo di precisione. Si potrebbe utilizzare questo metodo per ottenere una soluzione ottimale più rapidamente o, per problemi particolarmente complessi, una soluzione migliore in un lasso di tempo trattabile.
Questo approccio potrebbe essere utilizzato ovunque siano impiegati risolutori MILP, ad esempio servizi di ride-hailing, operatori di rete elettrica, distributori di vaccini o qualsiasi entità che si trovi ad affrontare uno spinoso problema di allocazione delle risorse.
“A volte, in un campo come l’ottimizzazione, è molto comune pensare alle soluzioni come puramente basate sull’apprendimento automatico o puramente classiche. Sono fermamente convinto che vogliamo ottenere il meglio da entrambi i mondi, e questo è un esempio davvero forte di questo approccio ibrido”, afferma l’autrice senior Cathy Wu, professoressa assistente per lo sviluppo della carriera di Gilbert W. Winslow in ingegneria civile e ambientale ( CEE) e membro del Laboratorio per i sistemi informativi e decisionali (LIDS) e dell’Istituto per dati, sistemi e società (IDSS).
Wu ha scritto l’articolo con gli autori principali Sirui Li, uno studente laureato dell’IDSS, e Wenbin Ouyang, uno studente laureato della CEE; così come Max Paulus, studente laureato all’ETH di Zurigo. La ricerca sarà presentata alla Conferenza sui sistemi di elaborazione delle informazioni neurali.
Difficile da risolvere
I problemi MILP hanno un numero esponenziale di potenziali soluzioni. Ad esempio, supponiamo che un venditore ambulante voglia trovare il percorso più breve per visitare diverse città e poi tornare nella città di origine. Se ci fossero molte città che potrebbero essere visitate in qualsiasi ordine, il numero di soluzioni potenziali potrebbe essere maggiore del numero di atomi nell’universo.
“Questi problemi sono chiamati NP-hard, il che significa che è molto improbabile che esista un algoritmo efficiente per risolverli. Quando il problema è abbastanza grande, possiamo solo sperare di ottenere prestazioni subottimali”, spiega Wu.
Un risolutore MILP impiega una serie di tecniche e trucchi pratici che possono ottenere soluzioni ragionevoli in un periodo di tempo trattabile.
Un tipico risolutore utilizza un approccio divide et impera, suddividendo innanzitutto lo spazio delle potenziali soluzioni in parti più piccole con una tecnica chiamata ramificazione. Quindi, il risolutore utilizza una tecnica chiamata taglio per restringere questi pezzi più piccoli in modo che possano essere cercati più velocemente.
Il taglio utilizza una serie di regole che restringono lo spazio di ricerca senza eliminare alcuna soluzione fattibile. Queste regole sono generate da alcune dozzine di algoritmi, noti come separatori, creati per diversi tipi di problemi MILP.
Wu e il suo team hanno scoperto che il processo di identificazione della combinazione ideale di algoritmi di separazione da utilizzare è, di per sé, un problema con un numero esponenziale di soluzioni.
“La gestione dei separatori è una parte fondamentale di ogni risolutore, ma questo è un aspetto sottovalutato dello spazio problematico. Uno dei contributi di questo lavoro è identificare il problema della gestione dei separatori come un compito di apprendimento automatico con cui iniziare”, afferma.
Riduzione dello spazio delle soluzioni
Lei e i suoi collaboratori hanno ideato un meccanismo di filtraggio che riduce lo spazio di ricerca dei separatori da oltre 130.000 potenziali combinazioni a circa 20 opzioni. Questo meccanismo di filtraggio si basa sul principio dei rendimenti marginali decrescenti, secondo cui il massimo beneficio deriverebbe da un piccolo insieme di algoritmi e l’aggiunta di ulteriori algoritmi non porterà molti miglioramenti aggiuntivi.
Quindi utilizzano un modello di apprendimento automatico per scegliere la migliore combinazione di algoritmi tra le 20 opzioni rimanenti.
Questo modello viene addestrato con un set di dati specifico per il problema di ottimizzazione dell’utente, quindi impara a scegliere gli algoritmi che meglio si adattano al compito particolare dell’utente. Dal momento che un’azienda come FedEx ha risolto i problemi di routing molte volte in passato, l’utilizzo di dati reali raccolti dall’esperienza passata dovrebbe portare a soluzioni migliori rispetto a ricominciare ogni volta da zero.
Il processo di apprendimento iterativo del modello, noto come banditi contestuali, una forma di apprendimento per rinforzo, prevede la scelta di una potenziale soluzione, l’ottenimento di feedback su quanto fosse buona e quindi il tentativo di trovare una soluzione migliore.
Questo approccio basato sui dati ha accelerato i risolutori MILP tra il 30 e il 70% senza alcun calo di precisione. Inoltre, l’accelerazione è stata simile quando l’hanno applicata a un solutore open source più semplice e a un solutore commerciale più potente.
In futuro, Wu e i suoi collaboratori vogliono applicare questo approccio a problemi MILP ancora più complessi, dove la raccolta di dati etichettati per addestrare il modello potrebbe essere particolarmente impegnativa. Forse potrebbero addestrare il modello su un set di dati più piccolo e poi modificarlo per affrontare un problema di ottimizzazione molto più ampio, dice. I ricercatori sono anche interessati a interpretare il modello appreso per comprendere meglio l’efficacia dei diversi algoritmi di separazione.
Questa ricerca è supportata, in parte, da Mathworks, dalla National Science Foundation (NSF), dall’Amazon Science Hub del MIT e dal Research Support Committee del MIT.
[ad_2]
Source link
