Che cos'è la riottimizzazione

Che cos'è la riottimizzazione

Quando si parla di processi di ottimizzazione, la riottimizzazione copre un ruolo particolare. Scopriamo insieme cosa vuol dire.

Introduzione

Partiamo dalle basi e diciamo che risolvere un problema di ottimizzazione è la migliore risposta ad un problema del tipo: “Qual è il modo migliore per fare una certa cosa?

Facciamo un esempio. Qual è il modo migliore per andare da Palermo a Bolzano, nel più breve tempo possibile, passando da 100 diverse località sparse per l’Italia? Forse in tanti hanno riconosciuto il problema del cammino di costo minimo: come visitare un grafo partendo da un nodo origine per arrivare ad un nodo destinazione minimizzando la somma dei costi, che vengono pagati ad ogni arco attraversato.

A parte la difficoltà di descrivere in termini matematici il problema da risolvere e trascrivere tutto in un software funzionante, ci sono due aspetti specifici da tenere in considerazione:

1. il tempo di esecuzione speso dal programma per trovare la migliore soluzione;
2. la qualità della migliore soluzione trovata che indica in maniera numerica quanto questa sia preferibile rispetto ad un’altra soluzione.

In linea di massima, una soluzione di buona qualità si ottiene impiegando un adeguato tempo di esecuzione.

Quando usciamo da un esempio molto accademico, come quello appena descritto, spesso ci dobbiamo confrontare con il fatto che il nostro problema di ottimizzazione si trova incastrato in un flusso di lavoro. Per cui dal momento in cui conosciamo l’ultimo pezzo di informazione necessaria alla completa descrizione del problema di ottimizzazione, al momento in cui dobbiamo materialmente conoscerne la migliore soluzione, possano passare anche solo pochi minuti. E come abbiamo visto prima, limitare il tempo di risoluzione può voler dire minore qualità della soluzione ottenuta. Che in un contesto importante, può voler dire anche una perdita d’efficienza non trascurabile in termini operativi ed economici.

La riottimizzazione

L’approccio classico per trovare il miglior bilanciamento tra qualità della miglior soluzione e il tempo di esecuzione è quello di scrivere un algoritmo di risoluzione che sia il più efficiente possibile. Ma se il flusso di lavoro lo permette possiamo applicare anche altri approcci basati sulla riottimizzazione.

Da un punto di vista prettamente tecnico, la riottimizzazione consiste nell'applicazione di particolari accorgimenti per permettono di risolvere un problema “grande” N e mantenere l’algoritmo in “pressione”, cioè con tutte le informazioni note fino a quel momento ancora pronte per l’uso. In questo modo, quando arriva un pezzo di informazione in più, il problema grande N+1 può essere risolto in maniera efficace ed efficiente.

L’analogia del puzzle

A quanti piacciono i puzzle? Io non sono molto bravo, per cui per montare i primi 900 pezzi di una scatola da mille impiego 16 ore e molta pazienza. Quando devo decidere però dove montare il pezzo numero 901, vado più o meno per ispezione controllando i bordi della tessera, il suo colore e gli spazi vuoti presenti sul mosaico non ancora completo. Riesco a trovare il posto giusto in meno di un minuto. Se invece, quando devo montare il pezzo numero 901, decido di smontare il mosaico incompleto e di ricominciare d’accapo, purtroppo non posso che impiegare ancora le 16 ore già impiegate per i primi 900 pezzi.

Andando quindi per analogia, possiamo dire che la scelta di smontare il mosaico è equivalente ad una ottimizzazione completa del problema con 901 tessere. Mentre l’ispezione per determinare la collocazione del pezzo 901 è equivalente alla riottimizzazione.

Un esempio

Pianificazione di un viaggio

Riprendiamo l’esempio della pianificazione di un viaggio che parte da Palermo ed arriva a Bolzano, passando da cento città diverse, minimizzando il tempo totale di percorrenza.

Se questo fosse un problema reale, magari associato alla attività di un corriere o di un trasportatore professionale, la pianificazione delle operazioni di trasporto potrebbe avere delle caratteristiche particolari, quali:

• la raccolta delle richieste di trasporto sono confinate in una finestra temporale;
• la finestra temporale si apre qualche giorno prima e si chiude poco prima della partenza del mezzo;
• all'interno della finestra temporale, i clienti trasmettono le proprie richieste andando a specificare, nel nostro caso, una nuova città che il mezzo dovrà toccare;
• alla chiusura della finestra temporale, il mezzo di trasporto ho soli 15 minuti prima di dover partire.

Applicando una tecnica di ottimizzazione, si avrebbero a disposizione solo 15 minuti per ottenere la migliore soluzione, che guiderà la spedizione da Palermo a Bolzano.

In alternativa, a partire dall'apertura della finestra temporale delle prenotazioni, un processo di riottimizzazione continua può partire all'arrivo del primo ordine e terminare alla chiusura della finestra temporale.

Conclusione

Ora ti invito a ripensare al tuo processo da ottimizzare e verificare se puoi trarre vantaggio dalla riottimizzazione. Se hai qualche dubbio contattami su poderico@gmail.com