insegnamento

LOGISTICA (cod. 272AA)

corso di studi

IAP-L - INFORMATICA APPLICATA

responsabile

Antonio Frangioni

docenti

Antonio Frangioni , Marco Antonio Boschetti

totale ore

93
( esercitazione: 44 ore , lezione: 49 ore )

    Dettaglio ore

Lezioni

1. Mer 21/09/2011 11:00-13:00 (2:0 h) lezione: Introduzione al corso di Logistica. Introduzione al modulo di Modelli ed Algoritmi per la Logistica. Primi richiami alla struttura e funzionamento dei Sistemi Logistici. (Antonio Frangioni)
2. Gio 22/09/2011 11:00-13:00 (2:0 h) lezione: La catena logistica: flussi, nodi. Classificazione dei Sistemi Logistici. Principali trends nell'evoluzione dei Sistemi Logistici. (Antonio Frangioni)
3. Mer 28/09/2011 11:00-13:00 (2:0 h) lezione: Obiettivi di gestione dei Sistemi Logistici: costi vs prestazioni, posizionamento strategico. Accenni all'ottimizzazione multi-obiettivo. Classificazione temporale dei problemi relativi ai Sistemi Logistici (strategici, tattici e operativi), conseguenze sui dati e sulla modalità di soluzione (DSS). Problemi di decisione nei Sistemi Logistici studiati nel corso e loro classificazione. (Antonio Frangioni)
4. Gio 29/09/2011 11:00-12:00 (1:0 h) lezione: Introduzione ai problemi di localizzazione di nodi logistici. Caratteristica principale: bilanciamento tra costi infrastrutturali e (riduzione dei) costi di trasporto. (Antonio Frangioni)
5. Gio 29/09/2011 12:00-13:00 (1:0 h) esercitazione: Un semplice modello di problema di localizzazione di nodi logistici (monolivello, monoprodotto, monoperiodo, ...). Il caso lineare: localizzazione = flusso di costo minimo. (Antonio Frangioni)
6. Mer 05/10/2011 11:00-13:00 (2:0 h) esercitazione: Una semplice istanza di problema di localizzazione di nodi logistici (mono-tutto). Formulazione come programmazione lineare. Formulazione come flusso di costo minimo. Introduzione all'uso di solutori general-purpose di problemi di ottimizzazione: istanza, modello, solutore, versione semplificata (istanza = solutore). Esemplificazione con MCFClass. (Antonio Frangioni)
7. Gio 06/10/2011 11:00-12:00 (1:0 h) lezione: Utilizzo di solutori general-purpose e relative problematiche. Condizioni di ottimo, approssimazioni numeriche, diversi algoritmi producono "soluzioni" diverse. Problemi vuoti ed illimitati. Parametri algoritmici, tuning, risorse computazionali (tempo, iterazioni, …). Casi speciali dei problemi, tipi dei dati. Cambiamento dei dati, "proprietà" dell'istanza, riottimizzazione. (Antonio Frangioni)
8. Gio 06/10/2011 12:00-13:00 (1:0 h) esercitazione: Esemplificazione dei concetti su MCFClass. (Antonio Frangioni)
9. Mer 12/10/2011 11:00-12:00 (1:0 h) lezione: Varianti del modello base del problema di localizzazione di nodi logistici esprimibili come MCF: funzioni costo lineari a tratti convesse, domanda non frazionabile e domande unitarie. (Antonio Frangioni)
10. Mer 12/10/2011 12:00-13:00 (1:0 h) esercitazione: Primo caso difficile di problema di localizzazione di nodi logistici: funzioni costo alle origini con carico fisso. Interpretazione (costo di infrastruttura vs. costo di trasporto), formulazioni PLI (tre diverse, con discussione), breve richiamo agli algoritmi risolutivi ed al perchè il problema è difficile (debolezza del rilassamento continuo). (Antonio Frangioni)
11. Gio 13/10/2011 11:00-12:00 (1:0 h) lezione: Ulteriori varianti di problema di localizzazione di nodi logistici: una volta introdotte le variabili binarie, si possono usare in molti modi. (Antonio Frangioni)
12. Gio 13/10/2011 12:00-13:00 (1:0 h) esercitazione: Funzioni costo di magazzino e di trasporto nonlineari: interpretazione (opzioni nei magazzini, diverse modalità di trasporto) e forme algebriche (lineare a tratti generica, concava, ...). (Antonio Frangioni)
13. Mer 19/10/2011 11:00-12:00 (1:0 h) lezione: Solutori general-purpose di problemi di Programmazione Lineare e Programmazione Lineare Intera. OSISolverInterface, CLP, CBC: funzionalità, interfaccia. (Antonio Frangioni)
14. Mer 19/10/2011 12:00-13:00 (1:0 h) esercitazione: Modellazione e soluzione di problemi di localizzazione di nodi logistici mediante solutori general-purpose. Soluzione del rilassamanto: uso di MCFClass, uso di OsiSolverInterface, confronti. Diverse modalità di costruzione del modello (uso di CoinModel), impatto sulle prestazioni. (Antonio Frangioni)
15. Gio 20/10/2011 11:00-12:00 (1:0 h) lezione: Debugging di modelli: formati MPS ed LP, nomi di righe e colonne. Linguaggi algebrici di modellazione: introduzione pratica a FlopC++. Modellazione di problemi di localizzazione di nodi logistici in FlopC++. (Antonio Frangioni)
16. Gio 20/10/2011 12:00-13:00 (1:0 h) esercitazione: Soluzione esatta di problemi difficili di localizzazione di nodi logistici mediante solutori general-purpose. Difficoltà computazionali: valutazioni inferiori e superiori. Introduzione al concetto di Branch & Cut. (Antonio Frangioni)
17. Mer 26/10/2011 11:00-12:00 (1:0 h) lezione: Diseguaglianze valide. Richiami, il caso delle minimal cover inequalities per lo zaino: derivazione, formulazioni del problema di separazione, separazione esatta ed euristica. (Antonio Frangioni)
18. Mer 26/10/2011 12:00-13:00 (1:0 h) esercitazione: Effetto delle disuguaglianze valide nei solutori general-purpose: il caso del problema di localizzazione di nodi logistici. Separazione delle minimal cover inequalities per lo zaino: aspetti implementativi, effetto pratico. (Antonio Frangioni)
19. Gio 27/10/2011 11:00-13:00 (2:0 h) esercitazione: Modelli di localizzazione di nodi logistici multiprodotto; formulazioni, diversi casi (magazzini condivisi e non, capacità di trasporto individuali e mutue, domanda non frazionabile individuale o collettiva). Modelli di localizzazione di nodi logistici multilivello. Formulazione a tre indici: vantaggi (rilassamento continuo migliore), svantaggi (dimensioni). Localizzazione di nodi logistici multiprodotto/multilivello = problema di progetto di rete multicommodity. Idea: alle volte è più facile studiare/scrivere un modello generale che un suo caso particolare. (Antonio Frangioni)
20. Mer 09/11/2011 11:00-13:00 (2:0 h) lezione: Problema critico nei modelli di localizzazione di nodi logistici: decisioni di lungo periodo = incertezza nei dati. Distinzione tra decisioni "here and now" e decisioni "aggiustabili" (di ricorso). Modello multiperiodo deterministico. Modello multiperiodo stocastico, albero degli scenari, "curse of dimensionality". Semplice versione robusta (poliedro delle domande stile zaino), derivazione della controparte deterministica compatta via dualità. (Antonio Frangioni)
21. Gio 10/11/2011 11:00-12:00 (1:0 h) lezione: Introduzione ai problemi di (progettazione e) gestione dei nodi logistici: dimensionamento ed attrezzaggio di impianti e magazzini, dimensionamento di lotti, allocazione ottima di spazi, impaccamento, schedulazione di risorse, routing. Discussione generale, esempi, un semplice modello di allocazione degli spazi. (Antonio Frangioni)
22. Gio 10/11/2011 12:00-13:00 (1:0 h) lezione: Problemi nella soluzione delle formulazioni: dimensioni, gap del rilassamento continuo. Principio generale: esistono formulazioni diverse con un diverso bilanciamento tra i due aspetti. Richiamo di teoria: esiste una formulazione "perfetta" a gap zero, ma tipicamente è troppo grande (e sconosciuta). Casi noti in cui ciò non avviene: flussi, assegnamento, cammini. Un caso meno noto: zaino con pesi interi (e "piccoli"). Formulazione pesudopolinomiale alternativa, esempio numerico. Estensione al cammino minimo vincolato con esempio numerico. (Antonio Frangioni)
23. Mer 16/11/2011 11:00-12:00 (1:0 h) esercitazione: Aspetti implementativi degli algoritmi di programmazione dinamica (formulazioni pesudopolinomiali). Il caso dello zaino: discussione del codice, confronto numerico con un solutore PLI general-purpose. (Antonio Frangioni)
24. Mer 16/11/2011 12:00-13:00 (1:0 h) lezione: Estensioni: PTAS e FPTAS per lo zaino. Generalizzazione: problemi NP-hard "facili", relazione tra programmazione dinamica e FPTAS. Accenno ai risultati di non approssimabilità. (Antonio Frangioni)
25. Gio 17/11/2011 11:00-12:00 (1:0 h) lezione: Problemi di impaccamento/schedulazione/taglio: i mille volti del bin packing/cutting stock. Formulazione compatta, debolezza del rilassamento continuo. Accenni ai problemi di impaccamento/taglio 2/3-dimensionale (estensione delle valutazioni inferiori, euristiche). Bounds combinatori (deboli) + euristiche Greedy + branching nonstandard = Branch&Bound non basati sulla PL. (Antonio Frangioni)
26. Gio 17/11/2011 12:00-13:00 (1:0 h) esercitazione: Risoluzione della formulazione di Kantorovich del bin packing mediante un solutore general-purpose. Discussione del codice (compresa euristica greedy per determinare un numero ammissibile di bins), problemi nella soluzione. Il problema della simmetria nella formulazione, alcuni banali tentativi per mitigarlo, loro effetti. (Antonio Frangioni)
27. Gio 24/11/2011 11:00-12:00 (1:0 h) lezione: Applicazione dell'idea base: trovare una formulazione migliore. Formulazione di Gilmore e Gomory del Cutting Stock. Problema (master) primale e duale, generazione di colonne. (Antonio Frangioni)
28. Gio 24/11/2011 12:00-13:00 (1:0 h) esercitazione: Implementazione della generazione di colonne. Uso dei solutori general-purpose. Inizializzazione, scelta del master problem, generazione delle colonne. Prestazioni su esempi sintetici ed istanze realistiche: confronto con la formulazione di Kantorovich. Risoluzione euristica mediante la formulazione "congelata". Accenno al Branch&Price. (Antonio Frangioni)
29. Mer 30/11/2011 11:00-12:00 (1:0 h) lezione: Come generare in modo sistematico formulazioni "grandi ma forti": rilassamento combinatorio, rilassamento Lagrangiano, duale Lagrangiano. Dualità Lagrangiana e dualità lineare. Teorema di equivalenza col rilassamento convessificato e sue conseguenze: confronto di rilassamenti Lagrangiani diversi. (Antonio Frangioni)
30. Mer 30/11/2011 12:00-13:00 (1:0 h) esercitazione: Applicazione dei concetti (rilassamento combinatori, rilassamenti Lagrangiani confronto di duali Lagrangiani diversi) al problema del Bin Packing. (Antonio Frangioni)
31. Gio 01/12/2011 11:00-12:00 (1:0 h) lezione: Risolvere il duale Lagrangiano I. Funzione lagrangiana, forma e proprietà. Gradienti e subgradienti (accenni). Metodo del subgradiente, varianti principali, proprietà di convergenza (accenni). Aspetti pratici. (Antonio Frangioni)
32. Gio 01/12/2011 12:00-13:00 (1:0 h) esercitazione: Aspetti implementativi dei metodi Lagrangiani I. Risoluzione (approssimata) del duale lagrangiano di un semplice problema di localizzazione di nodi logistici col metodo del subgradiente. Aspetti implementativi: determinazione dell'upper bound, warm-start, differenze tra il caso splittable e unsplittable. Esecuzione su alcune istanze, confronto con il solutore MIP, commenti. (Antonio Frangioni)
33. Mer 07/12/2011 11:00-12:00 (1:0 h) lezione: Risolvere il duale Lagrangiano II. Alternativa più evoluta: l'algoritmo del piano di taglio e la sua visione primale = decomposizione di Dantzig-Wolfe = generazione di colonne. Morale: risolvere il duale Lagrangiano = risolvere il rilassamento convessificato. Estensione: decomposizione Lagrangiana. (Antonio Frangioni)
34. Mer 07/12/2011 12:00-13:00 (1:0 h) esercitazione: Aspetti implementativi dei metodi Lagrangiani II. Risoluzione del duale lagrangiano di un semplice problema di localizzazione di nodi logistici con l'algoritmo del piano di taglio. Aspetti implementativi: fase 0 e fase 1, rimozione delle colonne. Euristiche di arrotondamento basate sulla soluzione convessificata. Esecuzione su alcune istanze, confronto con il solutore MIP ed il subgradiente. Problemi computazionali in entrambi gli approcci, uso di versioni stabilizzate (senza spiegazione), commenti. (Antonio Frangioni)
35. Mer 14/12/2011 11:00-13:00 (2:0 h) lezione: Introduzione ai problemi di trasporto long- e short-haul. Problemi short-haul: il TSP. Formulazioni compatte: versione con flusso, versione con variabili indicatrici di ordine (estensione alle finestre temporali). Formulazioni esponenziali: cutset inequalities (separatore polinomiale, generazione di righe) e formulazione derivante dal rilassamento Lagrangiano (accenni). Il VRP: descrizione del problema, estensioni dei modelli di TSP. (Antonio Frangioni)
36. Gio 15/12/2011 11:00-12:00 (1:0 h) lezione: Problemi di trasporto long-haul. Idea base: grafo spazio-tempo, tutto ciò che viaggia (merci, veicoli, equipaggi) è un flusso sul grafo spazio-tempo. Conseguenza: qualsiasi prolema di trasporto long-haul è (circa) un flusso multicommodity sul grafo spazio-tempo. Commenti finali sul modulo. (Antonio Frangioni)
37. Gio 15/12/2011 12:00-13:00 (1:0 h) esercitazione: Esempio di grafo spazio-tempo, versione "banale" e semplificazioni. Esempi realistici di problemi long-haul: schedulazione del trasporto su rete ferroviaria, selezione di una flotta di aerei, schedulazione del personale, problema combinato di schedulazione e trasporto (viaggi non schedulati). (Antonio Frangioni)
38. Lun 27/02/2012 11:00-13:00 (2:0 h) lezione: Problemi di Packing: descrizione dei problemi in ambito logistico. (Marco Antonio Boschetti)
39. Lun 27/02/2012 14:00-16:00 (2:0 h) lezione: Problemi di Packing: analisi dei diversi problemi. Due problemi "base": il Knapsack Problem e il Bin Packing Problem. Applicazioni ed estensioni. (Marco Antonio Boschetti)
40. Lun 05/03/2012 11:00-13:00 (2:0 h) lezione: Problemi di packing: il knapsack problem. Definizione di algoritmi esatti ed euristici e approfondimento di alcune varianti. (Marco Antonio Boschetti)
41. Lun 05/03/2012 14:00-17:00 (3:0 h) esercitazione: Implentazione algoritmi di base per il Knapsack Problem (da usare per risolvere altri problemi di packing). Analisi con gli studenti delle diverse opzioni, delle strutture dati, etc. (Marco Antonio Boschetti)
42. Lun 12/03/2012 11:00-13:00 (2:0 h) esercitazione: Implentazione algoritmi di base per il Knapsack Problem: algoritmo di programmazione dinamica. Debug e test. Definizione delle modalità di test: principi e metodi. (Marco Antonio Boschetti)
43. Lun 12/03/2012 14:00-17:00 (3:0 h) esercitazione: Implentazione algoritmi di base per il Knapsack Problem: upper e lower bound. Debug, test e discussione varianti. Introduzione all'implementazione di algoritmi per il bin packing. (Marco Antonio Boschetti)
44. Lun 26/03/2012 11:00-13:00 (2:0 h) esercitazione: Implementazione di algoritmi euristici (greedy) per il Bin Packing Problem. Analisi con gli studenti delle diverse varianti, strutture dati, etc. (Marco Antonio Boschetti)
45. Lun 26/03/2012 14:00-17:00 (3:0 h) esercitazione: Implementazione di algoritmi euristici e lower bound per il Bin Packing Problem. (Marco Antonio Boschetti)
46. Lun 16/04/2012 11:00-13:00 (2:0 h) lezione: Lower bound combinatorici: continuos bound e dual feasible functions. Vantaggi e limiti dei bound combinatorici. (Marco Antonio Boschetti)
47. Lun 16/04/2012 14:00-17:00 (3:0 h) esercitazione: Lower bound combinatorici: implementazione delle dual feasible functions. Generazione delle istanze di prova e test. (Marco Antonio Boschetti)
48. Lun 23/04/2012 11:00-13:00 (2:0 h) lezione: Introduzione alle metaeuristiche. (Marco Antonio Boschetti)
49. Lun 23/04/2012 14:00-17:00 (3:0 h) lezione: Metaeuristiche: Simulated Annealing, Algoritmi Genetici e Tabu Search. Esempi di applicazioni al Set Covering e al Vehicle Routing Problem. (Marco Antonio Boschetti)
50. Lun 30/04/2012 11:00-13:00 (2:0 h) esercitazione: Implementazione algoritmi greedy per il Set Covering. Analisi con gli studenti delle diverse opzioni, strutture dati, etc. (Marco Antonio Boschetti)
51. Lun 30/04/2012 14:00-17:00 (3:0 h) esercitazione: Implementazione algoritmo genetico per il Set Covering. Analisi con gli studenti delle diverse opzioni, strutture dati, etc. (Marco Antonio Boschetti)
52. Lun 07/05/2012 11:00-13:00 (2:0 h) esercitazione: Implementazione del Genetico per il Set Covering: implementazione varianti, debug e test. (Marco Antonio Boschetti)
53. Lun 07/05/2012 14:00-17:00 (3:0 h) esercitazione: Implementazione del Genetico per il Set Covering: implementazione varianti, debug e test. (Marco Antonio Boschetti)
54. Lun 14/05/2012 11:00-13:00 (2:0 h) lezione: Metodi esatti: valid iniequalities, Branch and Cut. Esempi di applicazione: Two-Dimensional Knapsack Problem (Marco Antonio Boschetti)
55. Lun 14/05/2012 14:00-17:00 (3:0 h) lezione: Metodi esatti: valid iniequalities, Branch and Cut. Esempi di applicazione: Two-Dimensional Knapsack Problem e Crew Scheduling. (Marco Antonio Boschetti)
56. Lun 21/05/2012 11:00-13:00 (2:0 h) lezione: Algoritmi per lo strip packing: un esempio di branch and bound non supportato da un modello. (Marco Antonio Boschetti)
57. Lun 21/05/2012 14:00-17:00 (3:0 h) lezione: Algoritmi esatti per il crew/vehicle scheduling: cutting plane (branch & cut) e column generation (branch & price). (Marco Antonio Boschetti)

    Dettaglio ore