Programmazione lineare intera¶
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online: programmazione lineare intera e mista, rilassamento lineare e bound, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut, solver MIP ed euristiche, con definizioni, esempi svolti passo per passo ed esercizi con soluzioni.
Comincia dai capitoli Gli esercizi Scarica le dispense (PDF)
Come è organizzato ogni capitolo¶
Ogni capitolo è una delle note del corso, con gli stessi numeri e gli stessi colori della dispensa: sul sito e nel PDF trovi tutto allo stesso posto.
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.
In verde il punto chiave da portare a casa.
Algoritmo
Lo pseudocodice di un metodo, in rosso.
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.
Le parti del corso¶
-
I · Modelli e bound
Che cos'è un problema di programmazione lineare intera (MIP, ILP, BIP), le sue soluzioni e i suoi esiti; bound primali e duali, gap e rilassamento lineare.
1. La programmazione lineare intera · 2. Bound primali e duali
-
II · Rafforzare la formulazione
Formulazioni ideali, disuguaglianze valide e disuguaglianze di cover: come rafforzare una formulazione.
3. Formulazioni ideali · 4. Disuguaglianze valide · 5. Disuguaglianze di cover
-
III · Metodi esatti
L'algoritmo dei piani di taglio con i tagli frazionari di Gomory, il branch-and-bound basato sulla programmazione lineare e il branch-and-cut. Esempi svolti passo per passo ed esercizi con la soluzione completa.
6. L'algoritmo dei piani di taglio con i tagli frazionari di Gomory · 7. Il branch-and-bound basato sulla programmazione lineare · 8. Il branch-and-cut
-
IV · I solver MIP
Che cosa fa un solver MIP (presolve, tagli, euristiche primali, strategie dell'albero, tolleranze) e come si legge il suo log, con esempi reali.
9. I solver MIP: che cosa fanno
-
V · Euristiche MIP
Arrotondamento, diving, feasibility pump, RINS, local branching, relax-and-fix e fix-and-optimize. Esempi ed esercizi con la soluzione completa.
10. Euristiche MIP
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;
- Ottimizzazione combinatoria — zaino, bin packing, colorazione, TSP, scheduling e lot sizing, risolti in tutti i modi;
- 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.