Problema dello zaino con setup (KPS)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di zaino · Catalogo (PDF)

Definizione 1: Problema dello zaino con setup

Dati:

1. uno zaino di capacità \(c \in \Z_{\ge 1}\),

2. un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,

3. una partizione dell'insieme degli oggetti in \(q \in \Z_{\ge 2}\) classi,

4. per ogni classe \(h \in \{1,2,\dots,q\}\), il sottoinsieme \(\mathscr{J}_h \subseteq \mathscr{I}\) degli oggetti di quella classe, con un costo di setup \(f_h \in \Z_{\ge 1}\) e un peso di setup \(s_h \in \Z_{\ge 1}\) associati,

5. per ogni oggetto \(j \in \mathscr{I}\), un ricavo \(p_j \in \Z_{\ge 1}\) e un peso \(w_j \in \Z_{\ge 1}\),

il problema dello zaino con setup (KPS) chiede di decidere quali oggetti inserire nello zaino, in modo che il peso totale degli oggetti selezionati più i pesi di setup delle loro classi non superi la capacità dello zaino e il ricavo totale degli oggetti selezionati meno i costi di setup delle loro classi sia massimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. Ogni classe contiene almeno un oggetto. Formalmente:

     \[ \mathscr{J}_h \neq \emptyset \qquad \forall\, h\in\{1,2,\dots,q\}. \]

  2. Ogni oggetto entra nello zaino insieme al peso di setup della sua classe (altrimenti non può mai essere selezionato). Formalmente:

     \[ w_j + s_h \le c \qquad \forall\, h\in\{1,2,\dots,q\},\ \forall\, j\in \mathscr{J}_h. \]

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Cap. 2 «Problemi di zaino»
Formulazioni	Cap. 9 «Formulazioni dei problemi di zaino»
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 23 «PD per il problema dello zaino con setup»
Esercizi	Esercizio 9.12; Cap. 23 (5 esercizi)