Problemi di zaino

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

• Ogni oggetto \(j\) ha un profitto \(p_j\) e un peso \(w_j\); una soluzione seleziona un sottoinsieme, o un multiinsieme, degli oggetti i cui pesi soddisfano uno o più vincoli di capacità.

• L'obiettivo è massimizzare il profitto totale degli oggetti selezionati; nel problema del subset sum il peso totale deve essere uguale a un valore dato.

• I membri della famiglia differiscono per il numero di copie di ogni oggetto, per il numero di capacità e di zaini, e per vincoli aggiuntivi sugli oggetti selezionati.

Problema	Sigla	Differenza
Problema dello zaino 0/1	KP	Il problema centrale della famiglia.
Problema del subset sum	SSP	L'SSP si risolve come il KP con \(p_j = w_j\) per ogni \(j\in\Ioggetti\): la risposta è sì se e solo se il valore ottimo di questo KP è uguale a \(c\).
Problema dello zaino limitato	BKP	Il BKP si riduce al KP quando \(b_j=1\) per ogni oggetto, e all'UKP quando ogni limite \(b_j\) è abbastanza grande da non essere vincolante.
Problema dello zaino illimitato	UKP	L'UKP è il BKP con \(b_j = \hat b_j = \lfloor c/w_j \rfloor\): ogni oggetto si può prendere tante volte quante entra nello zaino.
Problema dello zaino multidimensionale	MDKP	L'MDKP è il KP con \(k\) vincoli di capacità, uno per ogni risorsa; con \(k=1\) è il KP.
Problema degli zaini multipli	MKP	L'MKP è il KP con \(m\) zaini; ogni soluzione ammissibile dell'MKP è ammissibile per il KP con capacità \(\sum_{k\in\mathscr{K}} c_k\), e questo dà un bound duale.
Problema dello zaino a scelta multipla	MCKP	L'MCKP è il KP con il vincolo aggiuntivo di scegliere esattamente un oggetto per ogni classe, quindi un'istanza può essere non ammissibile.
Problema dello zaino con setup	KPS	Il KPS è il KP in cui scegliere il primo oggetto di una classe costa il setup \(f_h\) e consuma il peso di setup \(s_h\); una classe senza oggetti scelti non costa nulla.