Problemi scelti¶
Parte 1 del corso, volume 1 delle dispense: capitoli 2–8.
Le famiglie di problemi su cui si concentra tutto il corso: ogni famiglia si apre con una panoramica, poi una pagina per problema con la definizione, le ipotesi e un primo esempio.
Dispensa (PDF) Esercizi (PDF) I problemi in sintesi
-
2. Problemi di zaino
Scegliere oggetti di massimo profitto totale entro la capacità: il problema dello zaino 0/1, il subset sum, i problemi dello zaino limitato e illimitato, e altri.
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)
-
3. Problemi di packing
Sistemare oggetti di peso dato nel minimo numero di contenitori di capacità \(c\): bin packing e cutting stock.
-
4. Problemi di colorazione
Colorare i vertici di un grafo in modo che vertici adiacenti abbiano colori diversi, usando il minimo numero di colori: la colorazione dei vertici.
-
5. Problemi di clique
Trovare un insieme di cardinalità massima di vertici a due a due adiacenti di un grafo: cricca massima, insieme stabile massimo e le varianti pesate.
-
6. Problemi di routing
Trovare un percorso chiuso di lunghezza minima che visita ogni città una volta: il problema del commesso viaggiatore, il TSP metrico e il TSP asimmetrico.
Commesso viaggiatore (TSP) · TSP metrico e asimmetrico (ATSP)
-
7. Problemi di scheduling
Assegnare lavori a macchine parallele in modo che il makespan sia minimo: macchine identiche, uniformi e scorrelate.
-
8. Problemi di lot sizing
Pianificare la produzione di ogni periodo al minimo costo totale: lot sizing capacitato e senza capacità, e le loro varianti.