Ottimizzazione combinatoria¶
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online: i problemi di zaino, di packing, di colorazione, di clique, di routing, di scheduling e di lot sizing, studiati attraverso formulazioni e loro proprietà, programmazione dinamica, algoritmi euristici, di approssimazione e ad hoc; con definizioni, risultati con dimostrazione, esempi svolti passo per passo, esercizi con le soluzioni, notebook Colab e app interattive.
Per gli studenti della laurea magistrale in Ingegneria gestionale della Sapienza, e per chi vuole imparare a risolvere i problemi di ottimizzazione combinatoria. Prerequisiti: Programmazione lineare intera per le formulazioni e Algoritmi per gli algoritmi.
Le parti del corso¶
Le stesse voci del menu: ogni scheda dice a quale parte e a quali capitoli della dispensa corrisponde.
-
Ottimizzazione combinatoria
Parte 1 · Capitolo 1
Che cos'è un problema di ottimizzazione combinatoria: categorie, conteggio delle soluzioni, esplosione combinatoria, bound e gap, complessità.
-
Problemi scelti
Parte 1 · Capitoli 2–8
Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling · Problemi di lot sizing
-
Formulazioni
Parte 2 · Capitoli 9–15
Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling · Problemi di lot sizing
-
Programmazione dinamica
Parte 3 · Capitoli 16–28
Principi · Problemi di zaino · Problemi di lot sizing · Problemi misti
-
Euristiche
Parte 4 · Capitoli 29–33
Definizioni · Euristiche costruttive · Ricerca locale · Metaeuristiche · Euristiche MIP
-
Approssimazione
Parte 5 · Capitoli 34–40
Principi · Problemi di zaino · Problemi di packing · Problemi di colorazione · Problemi di clique · Problemi di routing · Problemi di scheduling
-
Algoritmi ad hoc
Parte 6 · Capitoli 41–42
Problemi di zaino · Problemi di colorazione
-
Catalogo
Tutti i problemi
Una pagina per problema, per famiglia: definizione, ipotesi e che cosa fa il corso sul problema.
-
Laboratorio
App interattive
Gli algoritmi del corso passo per passo, sulle istanze di riferimento o su istanze tue.
-
Notebook Colab
Python · C++
Il codice degli algoritmi dei capitoli, da eseguire in Google Colab sugli esempi e sugli esercizi.
Come usare queste dispense¶
- Sito e PDF. Ogni capitolo del sito è un capitolo della dispensa, con gli stessi numeri e gli stessi colori; i capitoli lunghi sono divisi in una pagina per sezione o per problema.
- In testa a ogni capitolo la barra con la parte, il PDF del volume, gli esercizi e le app del capitolo; in fondo, il link agli esercizi.
- Per problema. Il catalogo ha una pagina per ogni problema: la definizione e i capitoli che lo trattano, tecnica per tecnica.
- Il codice. Nelle pagine gli algoritmi sono in pseudocodice; i pulsanti «Esegui in Colab» aprono il notebook con il codice in Python e C++.
I box hanno gli stessi colori della dispensa:
Definizione
Il significato preciso di un concetto nuovo.
Teorema, proposizione, osservazione
Un risultato da ricordare, con le sue ipotesi.
Esempio
Un calcolo svolto per intero, un passo alla volta.
Formula
In rosa le formule da avere sempre sotto mano (per esempio le ricorrenze della programmazione dinamica).
Algoritmo
Lo pseudocodice, passo per passo come nella dispensa.
In verde il punto chiave da portare a casa.
Dimostrazione: si apre con un clic
Le dimostrazioni ci sono tutte, ma chiuse: prima leggi l'enunciato, poi apri la dimostrazione quando vuoi studiarla. Lo stesso vale per le soluzioni degli esercizi.
Dello stesso autore:
- Programmazione lineare — poliedri, algoritmo del simplesso, dualità e simplesso duale, con il laboratorio interattivo;
- Ottimizzazione convessa — insiemi e funzioni convesse, problemi di ottimizzazione convessa, con grafici interattivi;
- Algoritmi — rappresentazione dei numeri, pseudocodice, ordinamento e ricerca, analisi e algoritmi ricorsivi;
- Programmazione lineare intera — rilassamento continuo, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut;
- Ottimizzazione su reti — grafi, alberi ricoprenti, cammini minimi, flussi su reti, simplesso su reti e gestione dei progetti;
- Modellazione MIP — modelli di programmazione lineare a variabili intere, dalla formulazione alla soluzione con i solver;
- Laboratorio di Ricerca Operativa — modellazione e risoluzione di problemi di ottimizzazione con Python e i solver;
- Analisi Matematica 1 — numeri reali, funzioni, limiti, derivate e serie, con i grafici interattivi;
- Algebra lineare — vettori, matrici, determinanti, sistemi lineari e autovalori, con il laboratorio di calcolo.
Materiale didattico di Fabio Furini — DIAG, Sapienza Università di Roma.
Questo sito è disponibile anche in inglese.