Indice completo¶
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.
- In testa a ogni capitolo la barra con il PDF della dispensa, le slide, gli esercizi e le app del capitolo; in fondo, il link agli esercizi.
- I problemi. Definizioni, istanze e formulazioni dei problemi stanno nel corso Problemi di ottimizzazione combinatoria: i capitoli vi rimandano con un link.
- 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.
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.
Tutte le pagine del sito, nell'ordine del menu: i capitoli con le loro sezioni e le altre pagine.
Algoritmi euristici¶
- 1. Algoritmi euristici: definizioni · Esercizi
- 1.1 Algoritmi euristici
- 1.2 I problemi e le ipotesi
- 1.3 Bound primali e duali
- 1.4 Classificazione degli algoritmi euristici
- 1.5 Rappresentazione delle soluzioni e spazio di ricerca
- 1.6 Intorni e ottimi locali
- 1.7 Intensificazione e diversificazione
- 1.8 Come valutare un algoritmo euristico
- 1.9 Errori tipici
- 1.10 In sintesi
- 2. Euristiche costruttive · Esercizi
- 2.1 Euristiche costruttive
- 2.2 I problemi e le ipotesi
- 2.3 Il paradigma greedy
- 2.4 Il problema dello zaino 0/1: quale ordinamento?
- 2.5 Il problema del bin packing: prima ordinare, poi riempire
- 2.6 Scheduling su macchine parallele: prima i lavori più lunghi
- 2.7 Il problema del commesso viaggiatore: accodare o inserire?
- 2.8 Colorazione dei vertici: greedy e DSATUR
- 2.9 Costruzione randomizzata
- 2.10 Look-ahead e regret
- 2.11 Che cosa danno le euristiche costruttive, e che cosa non danno
- 2.12 Errori tipici
- 2.13 In sintesi
- 3. Ricerca locale · Esercizi
- 3.1 Ricerca locale
- 3.2 I problemi, le ipotesi e le soluzioni di partenza
- 3.3 Ricerca locale: lo schema
- 3.4 Intorni per i quattro problemi
- 3.5 First improvement e best improvement
- 3.6 Valutare una mossa in modo incrementale
- 3.7 TSP: 2-opt e Or-opt
- 3.8 \(P\,||\,C_{\max}\): move e swap
- 3.9 Paesaggi piatti e obiettivi ausiliari
- 3.10 KP: ammissibilità e penalità
- 3.11 Variable neighbourhood descent
- 3.12 Ricerca locale multi-start
- 3.13 Errori tipici
- 3.14 In sintesi
- 4. Metaeuristiche · Esercizi
- 4.1 Metaeuristiche
- 4.2 I problemi e le ipotesi
- 4.3 Come uscire da un ottimo locale
- 4.4 Simulated annealing
- 4.5 Tabu search
- 4.6 Iterated local search
- 4.7 Variable neighbourhood search
- 4.8 GRASP
- 4.9 Large neighbourhood search
- 4.10 Metodi basati su popolazioni: algoritmi genetici e memetici
- 4.11 Confronto e conclusioni
- 4.12 Errori tipici
- 4.13 In sintesi
- 5. Euristiche MIP per i problemi classici · Esercizi
- 5.1 Euristiche basate sulla PLI
- 5.2 I problemi e i loro modelli MIP
- 5.3 Arrotondamento
- 5.4 Diving
- 5.5 La feasibility pump
- 5.6 RINS, local branching e proximity search
- 5.7 Relax-and-fix e fix-and-optimize sul lot sizing
- 5.8 Le euristiche dentro il solver
- 5.9 Che cosa danno le euristiche basate sulla PLI
- 5.10 Errori tipici
- 5.11 In sintesi