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 flussö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