Registri a.a. 2011/2012
| 21/02/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Presentazione del corso. Introduzione generale: cos'è un modello matematico, modelli ed algoritmi, il processo decisionale. | ANTONIO FRANGIONI |
| 23/02/2012 | 11:00 | 13:00 | 2:0 hh | esercitazione | Esempio di processo decisionale: il problema della Pintel. Modellazione, riformulazioni algebriche e geometriche, risoluzone grafica, discussione della soluzione ottenuta. | ANTONIO FRANGIONI |
| 23/02/2012 | 14:00 | 16:00 | 2:0 hh | lezione | Definizioni generali: problema, istanza, soluzioni ammissibili/ottime, valore ottimo, problema vuoto/illimitato. Relazione tra problemi di ottimizzazione e problemi decisionali, versione decisionale di problemi di ottimizzazione, problemi NP-hard. Esemplificazioni su problemi vari (Pintel, equipartizione). | ANTONIO FRANGIONI |
| 24/02/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Il problema del cammino minimo: definizioni e prime proprietà. Casi facili e difficili: cicli negativi, riduzione di Hamilton Circuit a SP con vincolo di "semplicità" sui cammini. | ANTONIO FRANGIONI |
| 24/02/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Illustrazione delle definizioni generali col problema del cammino minimo. Certificato di non ammissibilità: algoritmi di visita, non raggiungibilità. Problema non limitato inferiormente: il caso dei cicli negativi. Prima introduzione intuitiva alle condizioni di (non)ottimalità. | ANTONIO FRANGIONI |
| 28/02/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Il problema dei cammini minimi. Varianti e proprietà (SPT). . Condizioni di ottimo: alberi ed etichetthe, teorema di Bellman. Conseguenza: algoritmo SPT-naive. Pseudocodice, motivazione, correttezza, terminazione (caso senza cicli negativi). | ANTONIO FRANGIONI |
| 28/02/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Algoritmo SPT-naive su un esempio. | ANTONIO FRANGIONI |
| 01/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Dove e perche' SPT-naive è inefficiente, come migliorarlo. Algoritmo SPT: pseudocodice, motivazione, "tre visite in una", aggiornamento differito delle etichette. Algoritmo SPT.L.Queue: correttezza, terminazione, complessità. Conseguenze: rilevazione di cicli negativi. Implementazioni performanti: Stack, Deque, 2-Queue, Threshold. | ANTONIO FRANGIONI |
| 01/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Esempi di esecuzione di SPT.L con diverse implementazioni di Q. | ANTONIO FRANGIONI |
| 01/03/2012 | 14:00 | 15:00 | 1:0 hh | lezione | Algoritmi SPT.S e loro proprietà: teorema di Dijkstra, complessità, implementazioni standard (lista non ordinata ed heap binario), implementazioni sofisticate (buckets, …). Conseguenze: il problema del cammino minimo da s a t nel caso di costi non negativi è "un po' più facile". | ANTONIO FRANGIONI |
| 01/03/2012 | 15:00 | 16:00 | 1:0 hh | esercitazione | Esempi di esecuzione di SPT.S. | ANTONIO FRANGIONI |
| 02/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Casi speciali di cammino minimo. SPT con radici multiple. SPT su grafi aciclici: pseudocodice, proprietà, buona numerazione di un grafo, conseguenze (cammini massimi). | ANTONIO FRANGIONI |
| 02/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | SPT.S con radici multiple. SPT-Acyclic e buona numerazione. | ANTONIO FRANGIONI |
| 06/03/2012 | 11:00 | 12:00 | 1:0 hh | esercitazione | Il problema dell'invasione, algoritmo "intuitivo" per la sua soluzione (con e senza fucilazione). | ANTONIO FRANGIONI |
| 06/03/2012 | 12:00 | 13:00 | 1:0 hh | lezione | Problema del Flusso Massimo: formulazione generale, prime proprietà. | ANTONIO FRANGIONI |
| 08/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Flusso Massimo: cammini aumentanti, operazione di composizione. Esistenza di un cammino aumentante = condizione sufficiente per la non ottimalità di un flusso. Trovare cammini aumentanti = visita sul grafo residuo. Algoritmo generico per cammini aumentanti: pseudocodice. | ANTONIO FRANGIONI |
| 08/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Cammini aumentanti (e non). Algoritmo per cammini aumentanti su un'istanza. | ANTONIO FRANGIONI |
| 08/03/2012 | 14:00 | 16:00 | 2:0 hh | lezione | Algoritmo per cammini aumentanti: terminazione (integralità della soluzione), correttezza (Teorema Max-Flow/Min-Cut). Conseguenza: l'algoritmo per cammini aumentanti risolve anche il problema del taglio di capacità minima (applicazioni ai problemi di interdizione ottima). Complessità, implementazioni efficienti dell'algoritmo per cammini aumentanti: selezione opportuna dei cammini. Algoritmi capacity scaling. Algoritmo di Edmons e Karp e sue proprietà. | ANTONIO FRANGIONI |
| 09/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Estensione dell'esempio dell'invasione: sorgenti multiple, destinazioni multiple, capacita' di sorgenti/destinazioni, capacità dei nodi, costo del flusso. Il problema del flusso di costo minimo: definizioni, cammini minimi e flusso massimo come casi particolari. | ANTONIO FRANGIONI |
| 09/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Espressività del flusso di costo minimo: problema dei panettoni (lot sizing), problema di schedulazione degli autobus, trasformazioni equivalenti (capacità inferiori sugli archi). | ANTONIO FRANGIONI |
| 13/03/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Il problema del flusso di costo minimo. Definizioni e proprietà: pseudoflussi, sbilanciamenti, cammini e cicli aumentanti (con costo). Cicli aumentanti di costo negativo ed ottimalità del flusso. Algoritmo per cancellazione di cicli: pseudocodice, prima discussione (algoritmo per cammini aumentanti per il flusso massimo come caso particolare). Determinazione dei cicli aumentanti di costo negativo. | ANTONIO FRANGIONI |
| 15/03/2012 | 11:00 | 12:00 | 1:0 hh | esercitazione | Algoritmo per cancellazione di cicli su un'istanza. | ANTONIO FRANGIONI |
| 15/03/2012 | 12:00 | 13:00 | 1:0 hh | lezione | Algoritmo per cancellazione di cicli: caso vuoto e illimitato, determinazione di una soluzione ammissibile, correttezza (teorema di decomposizione dei flussi), terminazione e complessità. Accenni ad implementazioni più teoricamente performanti (minimum mean cycle, cost/capacity scaling). | ANTONIO FRANGIONI |
| 15/03/2012 | 14:00 | 15:00 | 1:0 hh | esercitazione | Introduzione su un esempio dell'algoritmo dei cammini minimi successivi (versione a due fasi). | ANTONIO FRANGIONI |
| 15/03/2012 | 15:00 | 16:00 | 1:0 hh | lezione | Algoritmo dei cammini minimi successivi: derivazione intuitiva (fase uno "furba" dell'algoritmo per cancellazione di cicli) pseudocodice, proprietà teoriche (correttezza, terminazione, complessità). Importanza dell'invariante di minimalità. | ANTONIO FRANGIONI |
| 16/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Algoritmi per cammini aumentanti e cammini minimi successivi: esempio nel caso dei problemi di accoppiamento di massima cardinalità, assegnamento di costo minimo ed accoppiamento di massima cardinalità e costo minimo. Cammini alternanti aumentanti, operazione di composizione tra accoppiamenti e cammini. Discussione: complessità migliore, proprietà speciali (costi sempre positivi). | ANTONIO FRANGIONI |
| 16/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Algoritmo per cammini alternanti aumentanti ed algoritmo per cammini alternanti minimi successivi su due istanze di problemi di accoppiamento/assegnamento. | ANTONIO FRANGIONI |
| 20/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Introduzione alla PL. Definizioni, caratterizzazioni di un'istanza. Forme normali, trasformazioni equivalenti. | ANTONIO FRANGIONI |
| 20/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Istanze di PL: un'istanza di cammino minimo, il problema della Pintel. Trasformazioni equivalenti nella PL: esemplificazioni sulle istanze presentate e su un'istanza "casuale". | ANTONIO FRANGIONI |
| 22/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Geometria della PL: iperpiani, semispazi, poliedri. Nozioni intuitive di faccia, vertice, spigolo. Rapporto intuitivo tra facce e vincoli, vincoli ridondanti. Definizione formale di faccia e faccetta. | ANTONIO FRANGIONI |
| 22/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Geometria della PL: esempi in 2 e 3 dimensioni. Rappresentazione geometrica di un poliedro dato. Poliedri vuoti, degeneri, limitati, illimitati. Facce, faccette, vertici, spigoli. | ANTONIO FRANGIONI |
| 22/03/2012 | 14:00 | 15:00 | 1:0 hh | lezione | Geometria della PL: facce, vertici, basi. Insiemi convessi, inviluppo convesso. Coni convessi, cono finitamente generato. Teorema di decomposizione dei poliedri. Conseguenze del teorema di decomposizione dei poliedri: la PL sarebbe facile *se* l'input fosse dato sotto forma di lista dei vertici. Dimensionalità relativa delle due diverse descrizioni dei poliedri ("poche" facce e "tanti" vertici e viceversa). | ANTONIO FRANGIONI |
| 22/03/2012 | 15:00 | 16:00 | 1:0 hh | esercitazione | Geometria della PL e teorema di decomposizione dei poliedri su esempi in 2D e 3D. Determinazione della soluzione ottima di un problema di PL utilizzando il teorema di decomposizione dei poliedri su esempi in 2D e 3D. | ANTONIO FRANGIONI |
| 23/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Ancora sui vertici e sulle basi. Algoritmo risolutivo "naive" basato sull'enumerazione delle basi (caso non vuoto e non illimitato): correttezza, completezza, (non)efficienza. Esistenza dei vertici e rango di A. Trattamento di problemi con rango < n: teorema, conseguenze (si può sempre assumere rango di colonna pieno, m > n). | ANTONIO FRANGIONI |
| 23/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Applicazione dell'algoritmo di enumerazione delle basi su un esempio 3D. Esempi in 3D di poliedri con e senza vertici. Applicazione del metodo per risolvere un problema di PL quando A non ha rango pieno su un esempio 3D. | ANTONIO FRANGIONI |
| 27/03/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Ottimalità di una soluzione: direzioni ammissibili, condizioni necessarie e sufficienti. Cono delle direzioni ammissibili (in generale). Coni simpliciali e direzioni ammissibili per un vertice non degenere; rappresentazione per facce e per direzioni. Conseguenza: certificato di ottimalità per vertici non degeneri. | ANTONIO FRANGIONI |
| 29/03/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Proprietà dei raggi estremi dei coni simpliciali. Movimento lungo queste direzioni, massimo passo, cambio di base. Algoritmo del Simplesso (Primale) nel caso non degenere: pseudo-codice dell'algoritmo, correttezza, terminazione. | ANTONIO FRANGIONI |
| 29/03/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Simplesso (Primale) algebrico e geometrico nel caso non degenere. | ANTONIO FRANGIONI |
| 29/03/2012 | 14:00 | 15:00 | 1:0 hh | esercitazione | Simplesso (Primale) algebrico e geometrico nel caso degenere. Morale: funziona ugualmente. | ANTONIO FRANGIONI |
| 29/03/2012 | 15:00 | 16:00 | 1:0 hh | lezione | Algoritmo del Simplesso (Primale) nel caso degenere: modifiche allo pseudo-codice, terminazione (regola anticiclo di Bland). | ANTONIO FRANGIONI |
| 30/03/2012 | 11:00 | 13:00 | 2:0 hh | esercitazione | Preparazione al primo compitino. | ANTONIO FRANGIONI |
| 12/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Algoritmo del Simplesso (Primale): complessità, efficienza in pratica, dettagli implementativi (accenni). Determinazione di una base (primale) ammissibile: problema ausiliario, presimplesso (primale). | ANTONIO FRANGIONI |
| 12/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Presimplesso (primale): un esempio in 2 (3) dimensioni. | ANTONIO FRANGIONI |
| 12/04/2012 | 14:00 | 15:00 | 1:0 hh | lezione | Problema Duale. Motivazione: dimostrare l'ottimalità della soluzione in modo semplice. Soluzione ottima di base, disuguaglianze valide per il valore ottimo, definizione del problema duale. Il teorema debole della dualità. Le diverse definizioni di dualità e loro equivalenza; il duale del duale nella forma asimmetrica. Tabella P-D. | ANTONIO FRANGIONI |
| 12/04/2012 | 15:00 | 16:00 | 1:0 hh | esercitazione | Duale di un'istanza (Pintel). Uso del duale per dimostrare l'ottimalità. Determinazione del duale utilizzando la Tabella P-D. | ANTONIO FRANGIONI |
| 13/04/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Teoria della dualità: il Teorema forte della dualità, il Teorema degli scarti complementari e le loro conseguenze. Soluzioni complementari e basi. Nomenclatura delle basi. | ANTONIO FRANGIONI |
| 17/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Ancora teoria della dualità: uso del teorema degli scarti complementari, Lemma di Farkas, interpretazione economica del duale e degli scarti complementari. | ANTONIO FRANGIONI |
| 17/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Uso del teorema degli scarti complementari, Lemma di Farkas, ed interpretazione economica del duale e degli scarti complementari su esempi. | ANTONIO FRANGIONI |
| 19/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Derivazione e giustificazione del simplesso duale. Pseudo-codice dell'algoritmo, correttezza, terminazione e complessità. | ANTONIO FRANGIONI |
| 19/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Simplesso duale algebrico e geometrico: un esempio (soluzione ottima finita). | ANTONIO FRANGIONI |
| 19/04/2012 | 14:00 | 15:00 | 1:0 hh | esercitazione | Simplesso duale algebrico e geometrico: un esempio (duale illimitato). | ANTONIO FRANGIONI |
| 19/04/2012 | 15:00 | 16:00 | 1:0 hh | lezione | Simplesso duale: Determinazione di una base duale ammissibile. Relazione con l'analisi di sensitività. | ANTONIO FRANGIONI |
| 20/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Riottimizzazione ed analisi di sensitività nella Programmazione Lineare: cambiamento di costi e lato destro, aggiunta/rimozione di righe/colonne. Relazioni con la determinazione di una base duale ammissibile per il simplesso duale. | ANTONIO FRANGIONI |
| 20/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Riottimizzazione ed analisi di sensitività su esempi. Relazioni con l'interpretazione economica delle variabili duali. | ANTONIO FRANGIONI |
| 24/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Introduziona alla PLI. Motivazione: fallimento del rilassamento continuo. Variabili binarie e variabili logiche. PLI e calcolo logico: espressioni logiche come vincoli, il problema SAT. NP-completezza della PLI. | ANTONIO FRANGIONI |
| 24/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Primo esempio di problema di PLI: caricamento di nave (zaino). Trasformazione di formule del calcolo dei predicati in vincoli lineari. | ANTONIO FRANGIONI |
| 26/04/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Tecniche di modellazione. Modelli = LEGO = strutture standard + "pezzetti di connessione". Problemi "puramente combinatori". Richiamo alle strutture note: zaino, cammini, alberi, accoppiamenti, relazioni logiche. Applicazioni: cammino minimo vincolato (cammino + zaino), arborescenza orientata (albero + costo fisso), albero di copertura (idem + formulazione per tagli = due modelli molto diversi dello stesso problema). | ANTONIO FRANGIONI |
| 26/04/2012 | 14:00 | 16:00 | 2:0 hh | lezione | Tecniche di modellazione. TSP orientato: intersezione di modelli noti, ciascuno con varianti. Assegnamento di lavori a macchine con minimizzazione del numero di macchine: semiassegnamento + zaino + vincoli logici e/o di costo fisso (modelli diversi per lo stesso problema). Assegnamento di lavori a macchine con minimizzazione del tempo di completamento (modelli simili per problemi simili). Assegnamento di lavori a macchine con minimizzazione del numero di macchine e vincoli di incompatibilità (semiassegnamento + due tipi di vincoli logici). Assegnamento di frequenze (stesso modello per problemi diversi). Generalizzazioni di zaino ed assegnamento: Weighted Vertex Cover, set covering/partitioning/packing. | ANTONIO FRANGIONI |
| 27/04/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Tecniche di modellazione. Problemi "misti interi". Problema di progetto di rete: costi fissi e minima quantità positiva prefissata. Generalizzazioni: variabili a valori discreti, funzioni costo lineari a tratti. Casi particolari: funzione lineare a tratti convessa, massimo di funzioni lineari, valore assoluto. Vincoli disgiuntivi. | ANTONIO FRANGIONI |
| 27/04/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Esempi di funzioni costo lineari a tratti (convesse e non) e vincoli disgiuntivi. | ANTONIO FRANGIONI |
| 03/05/2012 | 11:00 | 13:00 | 2:0 hh | lezione | PL Mista-Intera e sua difficoltà (dipendente dal numero di variabili intere). Relazioni geometriche tra PL e PLI. Perchè la PLI è difficile (1): non convessità e direzioni di crescita, minimi locali e globali di una funzione nonconvessa. Perchè la PLI è difficile (2): formulazioni diverse, inviluppo convesso vs rilassamento continuo. | ANTONIO FRANGIONI |
| 03/05/2012 | 14:00 | 16:00 | 2:0 hh | lezione | Perchè la PLI è difficile (2, continua): proprietà di integralità, definizione generale e casi specifici (flusso). Esempio non banale di formulazione "esatta ma maneggiabile": MST. Definizione di "formulazione utilizzabile": oracoli di separazione, algoritmo del simplesso (duale) con "mechanized pricing". Conseguenza: la separazione dell'inviluppo convesso di problemi difficili è difficile. Esempio con il caso dello zaino: diseguaglianze valide (cover inequalities) e loro separazione, il separatore è difficile quanto il problema originario. Accenno alle tecniche poliedrali. | ANTONIO FRANGIONI |
| 04/05/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Perchè la PLI è difficile (3): determinazione del valore ottimo della funzione obiettivo, auto-riducibilità (esempio: zaino). Definizioni generali: algoritmi esatti ed euristici, rilassamenti. Preludio alle tecniche di enumerazione: cosa significa risolvere un problema di ottimizzazione (difficile), euristiche, rilassamenti e gaps. | ANTONIO FRANGIONI |
| 08/05/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Brevi richiami sulle euristiche. Euristiche di arrotondamento basate sulla PL: (pochi) successi e (molti) fallimenti. Esempio di euristiche di arrotondamento basate sulla PL "smart": Set-Covering con arrotondamento a soglia. Euristiche combinatorie per zaino e set packing: diversi algoritmi greedy (diversi ordinamenti). | ANTONIO FRANGIONI |
| 10/05/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Le euristiche combinatorie possono in realtà derivare da un rilassamento, e questo ha dei vantaggi: esempio Greedy CUD per lo zaino. Morale: per costruire algoritmi greedy efficaci farsi guidare da un rilassamento ==> garanzia sulle prestazioni a posteriori (e magari a priori). I rilassamenti non sono necessariamente quello continuo: euristica "twice around MST" per (TSP). Le garanzie sulle prestazioni richiedono un rilassamento, ma questo non necessariamente guida l'euristica: esempio (MMMS). | ANTONIO FRANGIONI |
| 10/05/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Esecuzione dell'euristica "twice around MST" per (TSP) e delle euristiche SPT ed LPT per (MMMS). | ANTONIO FRANGIONI |
| 10/05/2012 | 14:00 | 15:00 | 1:0 hh | lezione | L'interazione tra euristica e rilassamento può essere "profonda": esempio euristica primale-duale per il (WVC). Introduzione alla ricerca locale: idee di base, intorni, problemi principali (bilanciamento tra dimensione e costo di esplorazione degli intorni, minimi locali). | ANTONIO FRANGIONI |
| 10/05/2012 | 15:00 | 16:00 | 1:0 hh | esercitazione | Esecuzione dell'euristica primale-duale per (WVC). Esempio di euristica costruttiva (Greedy CUD) + ricerca locale (2-scambio) per lo zaino. | ANTONIO FRANGIONI |
| 11/05/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Ricerca locale. Proprietà generali degli intorni, intorni esatti, algoritmi per problemi "facili" come ricerca locale (casi di (SPT), (MF), (MCF), (PL)). Come si costruiscono intorni: il caso dei 2-scambi. Esempi con (MMMS), (TSP) e (CMST). Strategie di globalizzazione. Uso di intorni diversi: esempio di k-scambio per (MMMS) e (TSP). Ripartenza utilizzando euristiche greedy randomizzate. Accenno alle tecniche di risalita: Taboo Search, Simulated Annealling, algoritmi genetici. | ANTONIO FRANGIONI |
| 15/05/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Introduzione ai rilassamenti. Il rilassamento continuo: casi "buoni" ((MMMS), (WVC)) e "cattivi" (graph coloring). Vantaggio: si può usare tutta la teoria della PL, ed in particolare la dualità. Esempio: fissaggio basato sui costi ridotti. Cosa si fa quando il rilassamento continuo va male: rilassamenti combinatori (per eliminazione di vincoli). | ANTONIO FRANGIONI |
| 15/05/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Fissaggio basato sui costi ridotti per un'istanza del problema dello zaino. Rilassamenti per eliminazione di vincoli: (SPT) per (CSPT), (MST) per CMST, (MS1T) per (TSP). | ANTONIO FRANGIONI |
| 17/05/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Introduzione alle tecniche di enumerazione. Idea base: valutazioni inferiori e superiori per sottoproblemi e loro combinazione (divide et impera). Alberi delle decisoni. | ANTONIO FRANGIONI |
| 17/05/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | Esempi di alberi delle decisoni: zaino e (TSP). | ANTONIO FRANGIONI |
| 17/05/2012 | 14:00 | 16:00 | 2:0 hh | lezione | Pseudo-codice dell'algoritmo B&B. Discussione del B&B: ruolo del rilassamento, problemi vuoti, vari modi di potare un nodo (per la volutazione superiore, per ottimalità, per inammissibilità). Proprietà teoriche: complessità, terminazione, correttezza (valutazione superiore globale). | ANTONIO FRANGIONI |
| 18/05/2012 | 11:00 | 12:00 | 1:0 hh | lezione | Primi accenni agli elementi dell'implementazione del B&B: rilassamenti ed euristiche, branghing, strategia di visita dell'albero delle decisioni. Esempi "facili" sullo zaino, regola di branching "giusta" e "sbagliata". Come si costruisce una regola di branching: rendere inammissibile la soluzione del rilassamento. Relazioni tra branching e fissaggio basato sui costi ridotti. | ANTONIO FRANGIONI |
| 18/05/2012 | 12:00 | 13:00 | 1:0 hh | esercitazione | B&B per un'istanza del problema dello zaino con regola di branching "giusta" e "sbagliata". Potatura dei nodi per valutazione superiore, ottimalità, inammissibilità. Determinazione della valutazione superiore globale. | ANTONIO FRANGIONI |
| 22/05/2012 | 11:00 | 13:00 | 2:0 hh | lezione | Elementi dell'implementazione del B&B: rilassamenti ed euristiche, branching, strategia di visita dell'albero delle decisioni. B&B generici basati sulla PLI: elementi di forza e debolezza. | ANTONIO FRANGIONI |
| 24/05/2012 | 11:00 | 13:00 | 2:0 hh | esercitazione | Esempio di B&B basato su rilassamenti combinatori: TSP. Rilassamento = 1MST, euristica = 2-around-MST (o nessuna). Esempi di regole di branching per TSP (3 diverse, con discussione). Discussione delle strategie di visita. Esempio di B&B basato su rilassamenti combinatori: CSP. Rilassamento = SP, euristica = BFS, regole di branching "sbagliate" e "giuste" (compatibilità col rilassamento) con discussione. | ANTONIO FRANGIONI |
| 24/05/2012 | 14:00 | 16:00 | 2:0 hh | esercitazione | Preparazione al secondo compitino. | ANTONIO FRANGIONI |
| docente | ore effettuate | tipo didattica |
|---|---|---|
| ANTONIO FRANGIONI | 38 ore | esercitazione |
| ANTONIO FRANGIONI | 60 ore | lezione |