Formulazioni dei problemi e loro proprietà¶
Parte 2 del corso, volume 2 delle dispense: capitoli 9–15.
I modelli di programmazione lineare intera dei problemi del volume 1, i loro rilassamenti lineari e i duali, i bound che ne derivano e il confronto fra formulazioni più deboli e più forti.
-
9. Formulazioni dei problemi di zaino
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)
-
10. Formulazioni dei problemi di packing
Bin packing (BPP) · Cutting stock (CSP)
-
11. Formulazioni dei problemi di colorazione
Colorazione dei vertici (VCP)
-
12. Formulazioni dei problemi di clique
Clique massima (MCP) · Clique massima pesata
-
13. Formulazioni dei problemi di routing
Commesso viaggiatore (TSP) · TSP metrico e asimmetrico (ATSP)
-
14. Formulazioni dei problemi di scheduling
Macchine parallele identiche (P||Cmax)
-
15. Formulazioni dei problemi di lot sizing
Lot sizing capacitato (CLS) · Varianti del lot sizing