Catalogo dei problemi di ottimizzazione combinatoria¶
Tutti i problemi definiti nel corso, per famiglia. Ogni problema ha la sua pagina: la definizione, le ipotesi e che cosa fa il corso sul problema, tecnica per tecnica.
Catalogo (PDF) I problemi in sintesi
-
Problemi di zaino
Selezionare un sottoinsieme o un multiinsieme di oggetti di massimo profitto totale nel rispetto di vincoli di capacità.
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)
-
Problemi di packing
Sistemare gli oggetti nel minimo numero di contenitori di uguale capacità.
-
Problemi di colorazione
Colorare i vertici di un grafo con il minimo numero di colori.
-
Problemi di cricca
Trovare un insieme di vertici a due a due adiacenti di massima cardinalità o di massimo peso.
Cricca massima (MCP) · Insieme stabile massimo (MSSP) · Cricca massima pesata sui vertici (VWMCP) · Cricca massima pesata sui lati (EWMCP)
-
Problemi di routing
Trovare un giro di lunghezza minima che visita ogni città esattamente una volta.
Commesso viaggiatore (TSP) · TSP metrico · TSP asimmetrico (ATSP) · Ciclo hamiltoniano (HCP)
-
Problemi di scheduling
Assegnare lavori a macchine parallele in modo da minimizzare il makespan.
Macchine parallele identiche (P||Cmax) · Numero fissato di macchine identiche (Pm||Cmax) · Macchine parallele con velocità diverse (Q||Cmax) · Macchine parallele scorrelate (R||Cmax)
-
Problemi di lot sizing
Pianificare la produzione su un orizzonte di periodi al minimo costo.
Lot sizing capacitato (CLS) · Lot sizing senza capacità (ULS) · Lot sizing capacitato con capacità costante (CLS-C) · Lot sizing con più prodotti e tempi di setup (MLS) · Lot sizing con scorta iniziale (LS-SI) · Lot sizing con straordinario (LS-OT) · Lot sizing con domanda non soddisfatta (LS-UD)
-
Problemi misti
Problemi con una lunghezza o un ammontare totale esatto, risolti con la programmazione dinamica.