Materiale¶
Le dispense, gli eserciziari e il catalogo dei problemi in PDF, con la stessa numerazione di definizioni, teoremi, esempi ed esercizi del sito, e i notebook Colab con il codice degli algoritmi. Testo e figure sono rilasciati con licenza CC BY 4.0, il codice con licenza MIT.
Dispense¶
| Volume | Contenuto | Capitoli | File |
|---|---|---|---|
| 1. Problemi di ottimizzazione combinatoria | I problemi di ottimizzazione combinatoria e le loro famiglie: problemi di zaino, di packing, di colorazione, di clique, di routing, di scheduling e di lot sizing. Per ogni problema: definizione, ipotesi, istanze, conteggio delle soluzioni, una prima soluzione a mano e un bound semplice. | 1–8 | PDF (0.8 MB) |
| 2. Formulazioni dei problemi e loro proprietà | I modelli di programmazione lineare intera dei problemi del volume 1, i loro rilassamenti lineari e i duali, i bound che ne derivano e il confronto fra formulazioni più deboli e più forti. | 9–15 | PDF (1.0 MB) |
| 3. Programmazione dinamica | I principi della programmazione dinamica e gli algoritmi di PD per i problemi di zaino, il lot sizing, il cambio monete e il taglio delle aste: ricorrenze, pseudocodice, complessità e tabelle svolte. | 16–28 | PDF (1.4 MB) |
| 4. Algoritmi euristici | Algoritmi euristici: euristiche costruttive, ricerca locale, metaeuristiche ed euristiche basate sulla programmazione lineare intera, applicate ai problemi del corso. | 29–33 | PDF (1.7 MB) |
| 5. Algoritmi di approssimazione | Algoritmi di approssimazione: rapporti di prestazione e schemi di approssimazione, con algoritmi e analisi del caso peggiore per lo zaino, il bin packing, il TSP metrico e lo scheduling su macchine parallele, e i limiti dell'approssimazione per la colorazione dei vertici, la clique massima e il TSP generale. | 34–40 | PDF (1.1 MB) |
| 6. Algoritmi ad hoc | Algoritmi ad hoc: il branch-and-bound sull'elemento critico per il problema dello zaino 0/1 e il branch-and-bound DSATUR per la colorazione dei vertici. | 41–42 | PDF (0.5 MB) |
Eserciziari¶
| Volume | Contenuto | Capitoli | File |
|---|---|---|---|
| 1. Problemi di ottimizzazione combinatoria | Ottimizzazione combinatoria · Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling · Problemi di lot sizing | 1–8 | PDF (0.6 MB) |
| 2. Formulazioni dei problemi e loro proprietà | Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling · Problemi di lot sizing | 9–15 | PDF (0.6 MB) |
| 3. Programmazione dinamica | Principi · Problemi di zaino · Problemi di lot sizing · Problemi misti | 16–28 | PDF (1.0 MB) |
| 4. Algoritmi euristici | Definizioni · Euristiche costruttive · Ricerca locale · Metaeuristiche · Euristiche MIP | 29–33 | PDF (0.7 MB) |
| 5. Algoritmi di approssimazione | Principi · Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling | 34–40 | PDF (0.7 MB) |
| 6. Algoritmi ad hoc | Problemi di zaino · Problemi di colorazione | 41–42 | PDF (0.5 MB) |
Slide¶
Le slide delle lezioni, un PDF per capitolo, con le stesse definizioni ed esempi della dispensa.
Catalogo dei problemi¶
| Contenuto | File | |
|---|---|---|
| Catalogo dei problemi di ottimizzazione combinatoria | Tutti i problemi definiti nel corso, raggruppati per famiglia: per ciascuno la definizione, le ipotesi e che cosa fa il corso sul problema, tecnica per tecnica. | PDF (0.6 MB) |
Notebook Colab¶
Il codice dei capitoli sugli algoritmi, un notebook per capitolo e per linguaggio, da eseguire in Google Colab o da scaricare (link .ipynb). Come si usano: la pagina dei notebook.
