Vai al contenuto

I problemi in sintesi

Il corso risolve 7 problemi di ottimizzazione combinatoria in tutti i modi: le loro caratteristiche, che cosa fa il corso su ciascuno e la sua pagina del catalogo.

Caratteristiche

Problema Una soluzione è Obiettivo Vincoli Complessità
Zaino 0/1 (KP) un sottoinsieme di oggetti massimo profitto totale peso totale al più \(c\) NP-difficile in senso debole, PD pseudo-polinomiale \(O(nc)\)
Bin packing (BPP) una partizione degli oggetti nei contenitori minimo numero di contenitori carico di ogni contenitore al più \(c\) NP-difficile in senso forte
Colorazione dei vertici (VCP) una partizione dei vertici in insiemi stabili minimo numero di colori \(\chi(G)\) vertici adiacenti con colori diversi NP-difficile in senso forte
Clique massima (MCP) un sottoinsieme di vertici massima cardinalità \(\omega(G)\) vertici a due a due adiacenti NP-difficile
Commesso viaggiatore (TSP) un ordinamento ciclico delle città minima lunghezza del giro ogni città visitata una volta NP-difficile in senso forte
Scheduling su macchine parallele (P||Cmax) un assegnamento dei lavori alle macchine minimo makespan \(C_{\max}\) ogni lavoro su una macchina, senza interruzioni NP-difficile in senso forte (\(m\) nell'input)
Lot sizing capacitato (CLS) periodi di setup e quantità prodotte minimo costo di setup, produzione e giacenza domanda soddisfatta, capacità rispettate NP-difficile (il caso non capacitato è polinomiale)

Che cosa fa il corso su ogni problema

Ogni cella porta al capitolo.

Problema Definizione Formulazioni PD Euristiche Euristiche MIP Approssimazione Algoritmi ad hoc Esercizi
KP Cap. 2 Cap. 9 Cap. 17, 18, 19, 20, 21, 22, 23, 24 Cap. 30, 31, 32 Cap. 33 Cap. 34, 35 Cap. 41 Cap. 2, 9, 16, 17, 29, 30, 31, 32, 33, 34, 35, 41
BPP Cap. 3 Cap. 10 — Cap. 30, 31, 32 Cap. 33 Cap. 30, 36 — Cap. 1, 3, 10, 29, 30, 31, 32, 34, 36
VCP Cap. 4 Cap. 11 — Cap. 30 — non approssimabile Cap. 42 Cap. 4, 11, 30, 37, 42
MCP Cap. 5 Cap. 12 — Cap. 5 — non approssimabile — Cap. 4, 5, 12, 38
TSP Cap. 6 Cap. 13 — Cap. 6, 30, 31, 32 Cap. 33 Cap. 39 — Cap. 1, 6, 13, 29, 30, 31, 32, 39
P Cmax Cap. 7 Cap. 14 — Cap. 30, 31, 32 Cap. 33 Cap. 34, 40
CLS Cap. 8 Cap. 15 Cap. 26 Cap. 8, 33 Cap. 33 — — Cap. 8, 15, 26