Ottimizzazione Combinatoria

1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3


1.1 Enumerazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4


1.2 Tempo di esecuzione degli algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . 7


1.3 Problemi di ottimizzazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . 11


1.4 Ordinamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15


2 Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17


2.1 Definizioni fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17


2.2 Alberi, cicuiti, e tagli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21


2.3 Connettività . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28


2.4 Grafi di Eulero e grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35


2.5 Planarità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38


2.6 Dualità Planare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51


3 Programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55


3.1 Poliedri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56


3.2 Algoritmo del simplesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60


3.3 Implementazione dell’algoritmo del simplesso . . . . . . . . . . . . . . . . . 63


3.4 Dualità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66


3.5 Inviluppi convessi and politopi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74


4 Algoritmi di programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . 77


4.1 Dimensione dei vertici e delle facce . . . . . . . . . . . . . . . . . . . . . . . . . 77


4.2 Frazioni continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80


4.3 Eliminazione di Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83


4.4 Il metodo dell’elissoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86


4.5 Il Teorema di Khachiyan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92


4.6 Separazione ed ottimizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102


5 Programmazione intera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105


5.1 Inviluppo convesso di un poliedro . . . . . . . . . . . . . . . . . . . . . . . . . . . 107


5.2 Trasformazioni unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111


5.3 Integralità totalmente duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113


5.4 Matrici totalmente unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116


5.5 Piani di taglio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121


5.6 Rilassamento lagrangiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131


6 Alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135


6.1 Alberi di supporto minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135


6.2 Arborescenze di peso minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142


6.3 Descrizioni poliedrali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146


6.4 Packing alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . 149


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156


7 Cammini minimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159


7.1 Cammini minimi da una singola sorgente . . . . . . . . . . . . . . . . . . . . . 160


7.2 Cammini minimi tra tutte le coppie di vertici . . . . . . . . . . . . . . . . . 164


7.3 Circuiti di peso medio minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171


8 Reti di flusso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173


8.1 Il Teorema di massimo flusso–minimo taglio . . . . . . . . . . . . . . . . . . 174


8.2 Teorema di Menger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178


8.3 Algoritmo di Edmonds-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180


8.4 Flussi bloccanti e il teorema di Fujishige . . . . . . . . . . . . . . . . . . . . . . 182


8.5 L’algoritmo di Goldberg-Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184


8.6 Alberi di Gomory-Hu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188


8.7 Taglio di capacità minima in grafo non-orientato . . . . . . . . . . . . . . 195


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203


9 Flussi di costo minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207


9.1 Formulazione del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207


9.2 Un criterio di ottimalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209


9.3 Algoritmo di cancellazione di cicli di peso medio minimo . . . . . . 211


9.4 Algoritmo di Ford-Fulkerson scmcfpath . . . . . . . . . . . . . . . . . . . . . . . 215


9.5 Algortimo di Orlin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219


9.6 Algoritmo del simplesso per le reti di flusso scnetworksimplex . . . 223


9.7 Flussi temporali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232


10 Accoppiamenti di peso massimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235


10.1 Accoppiamento bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236


10.2 La matrice di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238


10.3 Il teorema di Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240


10.4 Ear-Decomposizione di grafi Factor-Critical . . . . . . . . . . . . . . . . . . . 243


10.5 Algoritmo di accopiamento di Edmonds . . . . . . . . . . . . . . . . . . . . . . . 249


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262


11 Matching Pesato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265


11.1 Il problema di assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266


11.2 Schema dell’algoritmo di accoppiamento di peso massimo . . . . . . 267


11.3 Implementazione dell’algoritmo di matching pesato massimo . . . . 270


11.4 Postottimalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283


11.5 Il politopo di matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289


12 b-Matchings e T -Joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291


12.1 b-Accoppiamenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291


12.2 T -Joins di peso minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295


12.3 T -Joins e T -Tagli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299


12.4 Il teorema di Padberg-Rao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307


13 Matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311


13.1 Sistemi di indipendenza e matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . 311


13.2 Altri assiomi sui matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315


13.3 Dualità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319


13.4 L’algoritmo greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323


13.5 Intersezione di matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328


13.6 Partizione di matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333


13.7 Intersezione di matroidi pesata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340


14 Generalizzazioni di matroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343


14.1 Greedoidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343


14.2 Polimatroidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347


14.3 Minimizzazione di funzioni submodulari . . . . . . . . . . . . . . . . . . . . . 351


14.4 Algoritmo di Schrijver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353


14.5 Funzioni submodulari simmetriche . . . . . . . . . . . . . . . . . . . . . . . . . . . 357


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362


15 NP-Completezza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365


15.1 Macchine di Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365


15.2 L’ipotesi di Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368


15.3 P e NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373


15.4 Il teorema di Cook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377


15.5 Alcuni problemi NP-Completi fondamentali . . . . . . . . . . . . . . . . . . . 381


15.6 La classe coNP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388


15.7 Problemi NP-Difficili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398


16 Algoritmi approssimati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401


16.1 Set Covering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402


16.2 Il problema del taglio-massimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407


16.3 Colorazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413


16.4 Schemi di approssimazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421


16.5 Soddisfacibilità massima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423


16.6 Il teorema PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428


16.7 L-Riduzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442


17 Il problema dello zaino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447


17.1 Zaino frazionario e il problema del mediano pesato . . . . . . . . . . . . 447


17.2 Un algoritmo pseudopolinomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450


17.3 Uno schema di approssimazione pienamente polinomiale . . . . . . . 452


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456


18 Bin-Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457


18.1 Euristiche Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457


18.2 Uno schema di approssimazione asintotico . . . . . . . . . . . . . . . . . . . . 463


18.3 Algoritmo di Karmarkar-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472


19 Flussi multi-prodotto e cammini disgiunti per archi . . . . . . . . . . . . . 475


19.1 Flussi multi-prodotto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476


19.2 Algoritmi per flussi multi-prodotto . . . . . . . . . . . . . . . . . . . . . . . . . . . 480


19.3 Il problema di cammini diretti disgiunti per archi . . . . . . . . . . . . . . 484


19.4 Il problema di cammini non-diretti disgiunti per archi . . . . . . . . . . 488


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497


20 Problemi di progettazione di reti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501


20.1 Alberi di Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502


20.2 L’algoritmo di Robins-Zelikovsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507


20.3 Progettazione di reti affidabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512


20.4 Un algoritmo di approssimazione primale-duale . . . . . . . . . . . . . . . 515


20.5 L’algoritmo di Jain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533


21 Il problema del commesso viaggiatore . . . . . . . . . . . . . . . . . . . . . . . . . 537


21.1 Algoritmi di approssimazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537


21.2 Il problema del commesso viaggiatore euclideo . . . . . . . . . . . . . . . . 542


21.3 Ricerca locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549


21.4 Il politopo del commesso viaggiatore . . . . . . . . . . . . . . . . . . . . . . . . 555


21.5 Stime per difetto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561


21.6 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569


22 Localizzazione di impianti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573


22.1 Localizzazione di impianti senza limiti di capacit`a . . . . . . . . . . . . . 573


22.2 Arrotondamento di soluzioni di programmazione lineare . . . . . . . . 575


22.3 Algoritmi primali-duali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577


22.4 Scaling e Greedy Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583


22.5 Stima sul numero di impianti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586


22.6 Ricerca locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589


22.7 Localizzazione di impianti con limiti di capacità . . . . . . . . . . . . . . . 595


22.8 Localizzazione di impianti generale . . . . . . . . . . . . . . . . . . . . . . . . . . 598


Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604


Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606