Vai al contenuto

Problemi di packing

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

  • Ogni oggetto \(j\) ha un peso \(w_j\); una soluzione è una partizione degli oggetti in contenitori di capacità \(c\), tale che il peso totale degli oggetti in ogni contenitore sia al più \(c\).

  • L'obiettivo è minimizzare il numero di contenitori; nel problema del cutting stock gli oggetti sono raggruppati in tipi con una domanda \(d_j\).

Problema Sigla Differenza
Problema del bin packing BPP Il problema centrale della famiglia.
Problema del cutting stock CSP Il CSP è il BPP con \(d_j\) copie identiche di ogni oggetto \(j\), e il BPP è il caso \(d_j = 1\) per ogni \(j\in\Ioggetti\).