Indice completo¶
Tutte le pagine del sito, nell'ordine del menu: i capitoli con le loro sezioni, il catalogo e le altre pagine.
Ottimizzazione combinatoria¶
Problemi scelti¶
- 2. Problemi di zaino · Esercizi
- 2.1 Panoramica della famiglia
- 2.2 Il problema dello zaino 0/1
- 2.3 Il problema del subset sum
- 2.4 Il problema dello zaino limitato
- 2.5 Il problema dello zaino illimitato
- 2.6 Il problema dello zaino multidimensionale
- 2.7 Il problema degli zaini multipli
- 2.8 Il problema dello zaino a scelta multipla
- 2.9 Il problema dello zaino con setup
- 2.10 Osservazioni
- 2.11 Errori tipici
- 2.12 In sintesi
- 3. Problemi di packing · Esercizi
- 4. Problemi di colorazione · Esercizi
- 5. Problemi di clique · Esercizi
- 6. Problemi di routing · Esercizi
- 7. Problemi di scheduling · Esercizi
- 8. Problemi di lot sizing · Esercizi
Formulazioni¶
- 9. Formulazioni dei problemi di zaino · Esercizi
- 9.1 Panoramica della famiglia
- 9.2 Un modello PLI per il problema dello zaino 0/1
- 9.3 Un primo rilassamento lineare
- 9.4 Un secondo rilassamento lineare
- 9.5 Upper bound per il problema dello zaino 0/1
- 9.6 Un modello PLI per il problema del subset sum
- 9.7 Un modello PLI per il problema dello zaino limitato
- 9.8 Un modello PLI per il problema dello zaino illimitato
- 9.9 Un modello PLI per il problema dello zaino multidimensionale
- 9.10 Un modello PLI per il problema degli zaini multipli
- 9.11 Un modello PLI per il problema dello zaino a scelta multipla
- 9.12 Un modello PLI per il problema dello zaino con setup
- 9.13 Errori tipici
- 9.14 In sintesi
- 10. Formulazioni dei problemi di packing · Esercizi
- 11. Formulazioni dei problemi di colorazione · Esercizi
- 12. Formulazioni dei problemi di clique · Esercizi
- 12.1 Panoramica della famiglia
- 12.2 Un modello PLI per il problema della clique massima: la formulazione sugli spigoli
- 12.3 Un primo rilassamento lineare
- 12.4 Un secondo rilassamento lineare
- 12.5 Disuguaglianze di clique: una formulazione più forte
- 12.6 La relazione con la colorazione dei vertici
- 12.7 Insiemi stabili sul grafo complementare
- 12.8 Modelli PLI per le varianti pesate
- 12.9 Errori tipici
- 12.10 In sintesi
- 13. Formulazioni dei problemi di routing · Esercizi
- 13.1 Panoramica della famiglia
- 13.2 Modelli PLI per il problema del commesso viaggiatore
- 13.3 Un modello con variabili di posizione (MTZ)
- 13.4 Un modello con vincoli di eliminazione dei sottogiri (DFJ)
- 13.5 Rilassamenti lineari
- 13.6 Modelli PLI per il TSP metrico e asimmetrico
- 13.7 Errori tipici
- 13.8 In sintesi
- 14. Formulazioni dei problemi di scheduling · Esercizi
- 15. Formulazioni dei problemi di lot sizing · Esercizi
- 15.1 Panoramica della famiglia
- 15.2 Modelli PLI per il problema di lot sizing capacitato
- 15.3 Una formulazione con un legame big-M
- 15.4 Il rilassamento lineare della formulazione big-M
- 15.5 Una formulazione a cammino minimo
- 15.6 Confronto fra le formulazioni
- 15.7 Modelli PLI per le varianti
- 15.8 Errori tipici
- 15.9 In sintesi
Programmazione dinamica¶
Problemi di zaino¶
- 17. PD per il problema dello zaino 0/1 · Esercizi
- 18. PD per il problema dello zaino illimitato · Esercizi
- 19. PD per il problema dello zaino limitato · Esercizi
- 20. PD per il problema del subset sum · Esercizi
- 21. PD per il problema dello zaino a scelta multipla · Esercizi
- 22. PD per il problema dello zaino multidimensionale · Esercizi
- 23. PD per il problema dello zaino con setup · Esercizi
- 24. PD per il problema degli zaini multipli · Esercizi
Problemi di lot sizing¶
- 25. PD per il problema del lot sizing senza capacità · Esercizi
- 26. PD per il problema del lot sizing capacitato · Esercizi
Problemi misti¶
- 27. PD per il problema del cambio monete · Esercizi
- 28. PD per il problema del taglio delle aste · Esercizi
Euristiche¶
- 29. Algoritmi euristici: definizioni · Esercizi
- 29.1 Algoritmi euristici
- 29.2 I problemi e le ipotesi
- 29.3 Bound primali e duali
- 29.4 Classificazione degli algoritmi euristici
- 29.5 Rappresentazione delle soluzioni e spazio di ricerca
- 29.6 Intorni e ottimi locali
- 29.7 Intensificazione e diversificazione
- 29.8 Come valutare un algoritmo euristico
- 29.9 Errori tipici
- 29.10 In sintesi
- 30. Euristiche costruttive · Esercizi
- 30.1 Euristiche costruttive
- 30.2 I problemi e le ipotesi
- 30.3 Il paradigma greedy
- 30.4 Il problema dello zaino 0/1: quale ordinamento?
- 30.5 Il problema del bin packing: prima ordinare, poi riempire
- 30.6 Scheduling su macchine parallele: prima i lavori più lunghi
- 30.7 Il problema del commesso viaggiatore: accodare o inserire?
- 30.8 Colorazione dei vertici: greedy e DSATUR
- 30.9 Costruzione randomizzata
- 30.10 Look-ahead e regret
- 30.11 Che cosa danno le euristiche costruttive, e che cosa non danno
- 30.12 Errori tipici
- 30.13 In sintesi
- 31. Ricerca locale · Esercizi
- 31.1 Ricerca locale
- 31.2 I problemi, le ipotesi e le soluzioni di partenza
- 31.3 Ricerca locale: lo schema
- 31.4 Intorni per i quattro problemi
- 31.5 First improvement e best improvement
- 31.6 Valutare una mossa in modo incrementale
- 31.7 TSP: 2-opt e Or-opt
- 31.8 \(P\,||\,C_{\max}\): move e swap
- 31.9 Paesaggi piatti e obiettivi ausiliari
- 31.10 KP: ammissibilità e penalità
- 31.11 Variable neighbourhood descent
- 31.12 Ricerca locale multi-start
- 31.13 Errori tipici
- 31.14 In sintesi
- 32. Metaeuristiche · Esercizi
- 32.1 Metaeuristiche
- 32.2 I problemi e le ipotesi
- 32.3 Come uscire da un ottimo locale
- 32.4 Simulated annealing
- 32.5 Tabu search
- 32.6 Iterated local search
- 32.7 Variable neighbourhood search
- 32.8 GRASP
- 32.9 Large neighbourhood search
- 32.10 Metodi basati su popolazioni: algoritmi genetici e memetici
- 32.11 Confronto e conclusioni
- 32.12 Errori tipici
- 32.13 In sintesi
- 33. Euristiche MIP per i problemi classici · Esercizi
- 33.1 Euristiche basate sulla PLI
- 33.2 I problemi e i loro modelli MIP
- 33.3 Arrotondamento
- 33.4 Diving
- 33.5 La feasibility pump
- 33.6 RINS, local branching e proximity search
- 33.7 Relax-and-fix e fix-and-optimize sul lot sizing
- 33.8 Le euristiche dentro il solver
- 33.9 Che cosa danno le euristiche basate sulla PLI
- 33.10 Errori tipici
- 33.11 In sintesi
Approssimazione¶
Problemi di zaino¶
Problemi di packing¶
Problemi di colorazione¶
Problemi di clique¶
Problemi di routing¶
Problemi di scheduling¶
Algoritmi ad hoc¶
Problemi di zaino¶
Problemi di colorazione¶
Catalogo¶
- I problemi in sintesi
- Problemi di zaino: Zaino 0/1 (KP) · Subset sum (SSP) · Zaino limitato (BKP) · Zaino illimitato (UKP) · Zaino multidimensionale (MDKP) · Zaini multipli (MKP) · Zaino a scelta multipla (MCKP) · Zaino con setup (KPS)
- Problemi di packing: Bin packing (BPP) · Cutting stock (CSP)
- Problemi di colorazione: Colorazione dei vertici (VCP)
- Problemi di cricca: Cricca massima (MCP) · Insieme stabile massimo (MSSP) · Cricca massima pesata sui vertici (VWMCP) · Cricca massima pesata sui lati (EWMCP)
- Problemi di routing: Commesso viaggiatore (TSP) · TSP metrico · TSP asimmetrico (ATSP) · Ciclo hamiltoniano (HCP)
- Problemi di scheduling: Macchine parallele identiche (P||Cmax) · Numero fissato di macchine identiche (Pm||Cmax) · Macchine parallele con velocità diverse (Q||Cmax) · Macchine parallele scorrelate (R||Cmax)
- Problemi di lot sizing: Lot sizing capacitato (CLS) · Lot sizing senza capacità (ULS) · Lot sizing capacitato con capacità costante (CLS-C) · Lot sizing con più prodotti e tempi di setup (MLS) · Lot sizing con scorta iniziale (LS-SI) · Lot sizing con straordinario (LS-OT) · Lot sizing con domanda non soddisfatta (LS-UD)
- Problemi misti: Taglio delle aste (RCP) · Cambio monete (CCP)