Ottimizzazione Latente
L’ottimizzazione latente è un paradigma di ottimizzazione ideato da Lokad che mira a risolvere problemi combinatori complessi e difficili. Gestisce anche problemi stocastici, che emergono ogni volta che è presente l’incertezza. L’ottimizzazione latente rappresenta una svolta per sfide come l’allocazione programmata delle risorse. A differenza dei solutori classici, che operano nello spazio delle soluzioni, l’ottimizzazione latente opera nello spazio della strategia. Questo approccio consente una rapida riottimizzazione man mano che le condizioni evolvono.
Panoramica della tecnologia
L’ottimizzazione latente, introdotta nel 2024, è la seconda generazione di tecnologie di ottimizzazione generale sviluppate da Lokad. Affronta problemi combinatori più difficili rispetto a quelli affrontati da discesa discreta stocastica, anche se presenta un livello leggermente ridotto di scalabilità.
Concettualmente, i Scienziati della Supply Chain presso Lokad progettano un flusso di elaborazione dati che include i seguenti passaggi:
- Preparare i dati storici.
- Generare previsioni probabilistiche.
- Produrre una strategia robusta per la presa di decisioni.
- Riottimizzare all’ultimo minuto, in condizioni modificate.
I dati storici vengono preparati utilizzando le capacità di ingegneria dati generali di Envision; Envision è il linguaggio specifico del dominio di Lokad. Le previsioni probabilistiche vengono quindi prodotte utilizzando programmazione differenziabile, un paradigma ideale per la modellazione probabilistica e trattato come un cittadino di prima classe in Envision.
Successivamente, viene impiegata l’ottimizzazione latente per generare una strategia decisionale. In sostanza, l’esito dell’ottimizzazione latente è un solutore specializzato attentamente progettato per il problema specifico. Infine, questa strategia può essere eseguita - e eventualmente ri-eseguita - nelle condizioni finali, leggermente mutevoli, per produrre le decisioni richieste. Poiché la strategia viene eseguita rapidamente, può essere utilizzata interattivamente dalle persone coinvolte.
Tutti e quattro i passaggi - (1), (2), (3) e (4) - vengono eseguiti all’interno di Envision.
Limiti dei solutori tradizionali
L’ottimizzazione matematica è un segmento maturo dell’informatica. Sul mercato sono disponibili una vasta gamma di solutori, sia proprietari che open-source. Purtroppo, nessuna di queste tecnologie esistenti soddisfa i nostri requisiti, in particolare quando si tratta di problemi di pianificazione stretti.
Gli algoritmi di branch-and-bound (e tutte le loro varianti) si basano sulla suddivisione della regione ammissibile in problemi più piccoli (branching) e sull’utilizzo di rilassamenti (bounding) per potare ampie sezioni dello spazio di ricerca. Questo approccio funziona male per i problemi della supply chain perché rimangono troppo aperti. Anche se lo spazio delle soluzioni è strettamente vincolato, è comunque enorme. Soddisfare semplicemente i vincoli è ben lungi dall’essere sufficiente per produrre una buona soluzione, il che mina la premessa fondamentale della suddivisione.
Gli algoritmi di ricerca locale (e tutte le loro varianti) ruotano attorno all’iterazione su una o più soluzioni attuali, esaminando varianti vicine. Purtroppo, anche questo metodo si comporta male perché il concetto di “località” non è ben definito in questi problemi. Date le strette limitazioni di questi scenari, la maggior parte degli aggiustamenti locali a una soluzione viola così tanti vincoli che il processo di ricerca non può recuperare una soluzione migliorata.
Da Lokad, ci siamo posti un obiettivo di scalabilità di alcuni milioni di variabili per problemi combinatori complessi, insieme alla capacità di riottimizzare entro pochi secondi quando le condizioni cambiano - anche se tali cambiamenti invalidano completamente la soluzione originale attraverso effetti a cascata.
Sotto il cofano
Lokad utilizza un approccio non convenzionale all’ottimizzazione combinatoria. Piuttosto che offrire un solutore standard, affrontiamo il problema attraverso un paradigma di programmazione specializzato chiamato ottimizzazione latente. Questo metodo è fondamentale per integrare le conoscenze e l’esperienza dei nostri Scienziati della Supply Chain.
La ottimizzazione latente introduce una rappresentazione alternativa del problema originale. Questa rappresentazione alternativa è una parametrizzazione ad alta dimensione di un solutore semplice su misura per il problema in questione. Questi parametri vengono quindi appresi applicando iterativamente il solutore parametrizzato sul problema originale (che può includere varianti stocastiche). Al suo nucleo, l’ottimizzazione latente è un processo di apprendimento.
L’output dell’ottimizzazione latente è un solutore semplice ben parametrizzato che produce soluzioni di alta qualità per il problema originale e per le sue varianti.
Esempio: Pianificazione di un sito di produzione aeronautica
Consideriamo un produttore aeronautico e uno dei suoi siti di produzione. Questo sito assembla un componente critico per aeromobili. L’obiettivo generale è massimizzare il throughput del sito dati le risorse disponibili (persone e asset industriali).
Questo processo di assemblaggio coinvolge circa 100 operazioni distinte. Ci sono anche circa 20 slot disponibili per svolgere queste operazioni, ciascuno con attributi diversi. Alcune operazioni possono essere eseguite solo in slot specifici. Un grafo di dipendenza complesso collega le operazioni, ma a differenza di una linea di produzione automobilistica, questo grafo non forma una sequenza lineare; c’è una notevole flessibilità nell’ordinamento finale dei compiti.
Inoltre, alcune operazioni richiedono specifici pezzi di attrezzatura, che esistono in quantità limitate sul sito. Molte operazioni dipendono anche dall’avere l’inventario necessario a portata di mano; a volte le parti essenziali vengono ritardate. Le operazioni variano nel numero di persone che possono lavorarci contemporaneamente per accelerare il completamento, variando da 1 fino a 5 individui.
Un team di circa 100 tecnici opera il sito in turni di 20-30 persone. Ogni tecnico ha uno dei tre livelli di qualifica per ogni operazione. Il livello più alto consente al tecnico di eseguire un’operazione e verificare il lavoro svolto da altri. Il livello intermedio consente a un tecnico di eseguire e verificare autonomamente il proprio lavoro. Il livello più basso consente a un tecnico di eseguire un’operazione, ma richiede la verifica da parte di un collega con la qualifica più alta.
La direzione del sito di produzione desidera un programma di lavoro minuto per minuto per le prossime settimane, specificando esattamente quale tecnico lavorerà su ciascuna operazione per ciascun componente (con ciascun componente identificato individualmente per numero di serie). Questo livello di dettaglio è essenziale per garantire la solidità del programma.
Tuttavia, le condizioni possono evolvere all’inizio di ogni turno. Un dipendente potrebbe essere assente a causa di malattia, o una parte potrebbe essere ritardata e quindi non disponibile. Se questi problemi non vengono affrontati prontamente, si trasformano rapidamente in una serie di inefficienze, lasciando tecnici e asset inattivi mentre vengono risolti i problemi.
Con l’ottimizzazione latente, la direzione del sito può produrre un programma di lavoro dettagliato che comprende decine di migliaia di compiti per le prossime settimane. Possono anche eseguire nuovamente lo strumento all’ultimo momento per tener conto di cambiamenti imprevisti. Inoltre, la soluzione appena generata non è una rimescolatura casuale massiccia del piano originale, ma un programma che assomiglia molto alla versione iniziale, richiedendo solo piccoli aggiustamenti per adattarsi alle condizioni più recenti.