2.6 Il problema dello zaino multidimensionale¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 2 · Capitolo 2: Problemi di zaino · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di zaino · App: Forza bruta sul problema dello zaino 0/1
Definizione 2.6: problema dello zaino multidimensionale
Dati:
-
uno zaino \(k\)-dimensionale,
-
per ogni dimensione \(d \in \underbrace{\{1,2,\dots,k\}}_{=\mathscr{D}}\), una capacità \(c_d \in \Z_{\ge 1}\),
-
un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,
-
per ogni oggetto \(j \in \mathscr{I}\), un profitto \(p_j \in \Z_{\ge 1}\),
-
per ogni dimensione \(d \in \mathscr{D}\) e ogni oggetto \(j \in \mathscr{I}\), un peso \(w_{dj} \in \Z_{\ge 1}\),
il problema dello zaino multidimensionale (MDKP) chiede di decidere quali oggetti inserire nello zaino, in modo che per ogni dimensione il peso totale degli oggetti selezionati non superi la capacità corrispondente e il profitto totale degli oggetti selezionati sia massimo.
-
Un'istanza dell'MDKP è specificata da:
-
due numeri interi:
-
il numero di oggetti \(n \in \Z_{\ge 1}\),
-
il numero di dimensioni \(k \in \Z_{\ge 1}\),
-
-
un vettore di numeri interi di lunghezza \(n\):
- \(\vet{p} \in \Z_{\ge 1}^n\), che contiene i profitti degli oggetti,
-
un vettore di numeri interi di lunghezza \(k\):
- \(\vet{c} \in \Z_{\ge 1}^k\), che contiene le capacità dello zaino per ogni dimensione,
-
una matrice di numeri interi con \(k\) righe e \(n\) colonne:
- \(\vet{W} \in \Z_{\ge 1}^{k \times n}\), che contiene i pesi degli oggetti per ogni dimensione.
-
-
Una soluzione ammissibile dell'MDKP è un sottoinsieme di oggetti
\[ S \subseteq \mathscr{I} \]tale che i vincoli di capacità sono soddisfatti in ogni dimensione, ossia
\[ \sum_{j\in S} w_{dj} \le c_d \qquad \forall\, d\in \mathscr{D}. \]Di conseguenza, l'MDKP si può enunciare in modo equivalente come il problema di selezionare un sottoinsieme di oggetti il cui peso totale rispetta le capacità dello zaino in ogni dimensione e il cui profitto totale è massimo.
Data un'istanza dell'MDKP, l'MDKP si può enunciare formalmente come:
\[\begin{equation*} \label{MDKP} \tilde{S}\in \argmax_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} p_j \;\;:\;\; \sum_{j\in S} w_{dj} \le c_d \ \ \forall\, d\in \mathscr{D} ~~\right\}. \tag{2.8} \end{equation*}\]
Esempio 2.5: istanza dell'MDKP
Consideriamo uno zaino \(2\)-dimensionale (\(k=2\)) con capacità \(c_1 = 10\) e \(c_2 = 12\), e un insieme \(\mathscr{I} = \{1,2,3,4\}\) di \(4\) oggetti (\(n = 4\)), con i seguenti profitti e pesi:
| Oggetti | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | |
|---|---|---|---|---|---|
| Profitti | \(p_j\) | \(6\) | \(7\) | \(5\) | \(9\) |
| Pesi (dim. \(1\)) | \(w_{1j}\) | \(4\) | \(5\) | \(3\) | \(7\) |
| Pesi (dim. \(2\)) | \(w_{2j}\) | \(6\) | \(4\) | \(5\) | \(3\) |
Il disegno ha una scatola per dimensione, di lunghezza \(c_1=10\) e \(c_2=12\): un oggetto selezionato occupa un blocco di lunghezza \(w_{1j}\) nella prima scatola e uno di lunghezza \(w_{2j}\) nella seconda. La soluzione ottima \(\{3,4\}\) riempie la prima dimensione e usa \(8\) unità della seconda, con profitto \(5+9=14\).
2.6.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
L'insieme di tutti gli oggetti non entra nello zaino (altrimenti selezionare tutti gli oggetti è ammissibile e ottimo). Formalmente,
\[ \exists\, d\in \mathscr{D} \ \text{tale che}\ \sum_{j\in \mathscr{I}} w_{dj} \;>\; c_d . \] -
Ogni oggetto, da solo, entra nello zaino in ogni dimensione (altrimenti non può mai essere selezionato). Formalmente,
\[ w_{dj} \le c_d, \qquad \forall\, d\in \mathscr{D},\ \forall\, j\in \mathscr{I}. \]
-