Problemi di ottimizzazione combinatoria¶

1.1 Problemi di ottimizzazione combinatoria

Apri
1.2 Categorie di problemi di ottimizzazione combinatoria

Aree applicative · I problemi del corso per categoria

Apri
1.3 Contare le soluzioni

Ordinamenti e ordinamenti ciclici · Partizioni e numeri di Bell

Apri
1.4 Esplosione combinatoria e forza bruta

Tempi di calcolo

Apri
1.5 Bound primali, bound duali e gap

Apri
Cenni di complessità computazionale

Algoritmi pseudo-polinomiali e problemi NP-hard in senso forte

Apri

Prerequisiti

Dai Preliminari: problemi di ottimizzazione (regione ammissibile, funzione obiettivo, soluzione ottima e valore ottimo), coefficienti binomiali e partizioni di un insieme finito.
Non serve alcuna conoscenza di programmazione intera: i bound di questo capitolo vengono da argomenti combinatori.

Obiettivi

Al termine di questo capitolo saremo in grado di:

riconoscere un problema di ottimizzazione combinatoria, la categoria delle sue decisioni e l'oggetto combinatorio delle sue soluzioni (un sottoinsieme, un ordinamento, una partizione, un assegnamento);
contare le soluzioni candidate (\(2^n\) sottoinsiemi, \(n!\) ordinamenti, \((n-1)!/2\) ordinamenti ciclici, numeri di Bell per le partizioni) e stimare il tempo di calcolo di un'enumerazione a forza bruta;
definire bound primali, bound duali e gap, e usarli per certificare che una soluzione è ottima;
collocare un problema nelle classi P, NP e NP-hard, e distinguere un algoritmo pseudo-polinomiale da uno polinomiale.

Avanti: 1.1 Problemi di ottimizzazione combinatoria

Esercizi su questo capitolo: Ottimizzazione combinatoria