Passa ai contenuti principali

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

Commenti

Post popolari in questo blog

PuLP – Un valido strumento per la didattica

L'insegnamento dei concetti di base della ricerca operativa, ovvero la programmazione lineare, ha trovato nel corso degli ultimi anni diversi strumenti di supporto. Sono ormai parecchi i software gratuiti e open source che permettono agli studenti e agli insegnanti di toccare con mano le nozioni e i concetti spiegati e studiati sui banchi. Ricordiamo, ad esempio, glpk che con il suoi linguaggio di modellazione MathProg permettete di scrivere e risolvere anche complessi modelli di programmazione lineare intera. Oppure citiamo anche lp_solve che con il suo ambiente impropriamente chiamato lp_solve IDE permette di scrivere e risolvere modelli di programmazione lineare direttamente nella formulazione matematica. A mio avviso però le proposte appena citate sono limitate nella potenza espressiva e nelle capacità di integrarsi con altri software o moduli esterni. Queste limitazioni sono egregiamente risolte da PuLP : un modellatore di problemi di programmazione lineare intera basato

Ci arricchiremo con la ricerca operativa?

A questa domanda forse possiamo rispondere sì :-) , rimandando al lavoro molto fresco ed interessante di Giancarlo Volpe dal titolo " Scommesse sportive: un modello di Ricerca Operativa che descrive la “vincita perfetta” " E' possibile scaricare il documento da scribd.com . Dall'apprezzabile contenuto didattico la parte entrale, dove si illustra passo passo come è possibile usare il risolutore di excel per applicarlo al modello descritto. Buona lettura e giocate con moderazione. Un Modello di Ricerca Operativa per Scommesse Sportive

Dispense di ricerca operativa

Ho trovato sulla home page del prof. Agnetis, delle interessanti dispense di ricerca operativa. I temi trattati sono tutti molto interessanti: Appunti sul duale del problema del massimo flusso Appunti sui problemi di matching Appunti su classi di complessità e problemi NP-completi Appunti sul problema del TSP euclideo Appunti sulla generazione di colonne Appunti sui modelli di lot sizing: Wagner-Whitin, Zangwill, Florian-Klein Appunti sui problemi di scheduling Appunti sui metodi metaeuristici di ricerca Introduzione all'ottimizzazione non vincolata   Introduzione all'ottimizzazione vincolata Esercizi di ottimizzazione non vincolata  Condizioni di KKT e Programmazione Lineare  Esercizi di ottimizzazione vincolata   Raccolta di esercizi di PL svolti  Esercizi di esame di PL svolti Esercizi di PLI svolti Appunti sui metodi basati sul rilassamento Lagrangiano Esercizi d'esame (R.O.) di ottimizzazione non vincolata e vincolata Ottimizzazione nella Gestione