9.2 Un modello PLI per il problema dello zaino 0/1¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 9 · Capitolo 9: Problemi di zaino · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di zaino · App: Rilassamento continuo e upper bound per lo zaino 0/1
Il problema dello zaino 0/1 e la sua istanza di riferimento (Esempio 2.1) sono definiti nel Capitolo 2 «Problemi di zaino», Sezione 2.2.
-
Introduciamo le seguenti \(n\) variabili binarie:
\[\begin{equation*} \label{BIN_VAR} x_j = \left\{ \begin{array}{ll} 1 & \textrm{se l'oggetto $j$ è selezionato nello zaino}\\[1.5ex] 0 & \textrm{altrimenti} \end{array} \qquad \forall j \in \underbrace{\{1,2,\dots,n\}}_{=\mathscr{I}}. \right. \tag{9.1} \end{equation*}\]
Con queste variabili, un modello di programmazione lineare intera (PLI) per il problema dello zaino 0/1 (KP) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{\mathrm{KP}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{\mathrm{KP}}\):
-
la funzione obiettivo lineare \(\eqref{obj_KP}\) massimizza il profitto totale degli oggetti selezionati nello zaino;
-
il vincolo \(\eqref{cons1_KP}\) garantisce che il peso totale degli oggetti selezionati non superi la capacità dello zaino (un vincolo lineare);
-
infine, i vincoli \(\eqref{cons2_KP}\) definiscono le variabili del modello PLI.
-
Esempio 9.1: modello \(\mathrm{ILP}_{\mathrm{KP}}\)
Consideriamo uno zaino di capacità \(c = 9\) e un insieme \(\mathscr{I} = \{1,2,3,4,5,6\}\) di \(6\) oggetti (\(n = 6\)), con i seguenti profitti e pesi:
Questa è l'istanza del KP dell'Esempio 2.1, e la chiamiamo Esempio 9.1. Il modello \(\mathrm{ILP}_{\mathrm{KP}}\) per questa istanza è:
Una soluzione ottima \(~{\tilde{\vet x}}(\mathrm{ILP}_{\mathrm{KP}})\) è:
Il valore ottimo \(z(\mathrm{ILP}_{\mathrm{KP}})\) è \(15\). La soluzione ottima associata del KP è \(\tilde{S} =\{1,4\}\), ed è l'unica soluzione ottima.
9.3 Un primo rilassamento lineare¶
Per ottenere un rilassamento lineare del modello \(\mathrm{ILP}_{\mathrm{KP}}\), rilassiamo i vincoli \(\eqref{cons2_KP}\) con i seguenti:
Questo modello PL si chiama modello \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\).
Esempio 9.2: modello \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\)
Il modello \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\) per l'istanza del KP dell'Esempio 9.1 è:
Una soluzione ottima \(~{\tilde{\vet x}}(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) è:
Il valore ottimo \(z(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) è \(27\).
Di conseguenza, abbiamo l'upper bound:
Con una variabile duale non negativa \(\pi\) per il vincolo \(\eqref{cons1_KP}\), il modello duale del modello \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\) è:
Questo modello PL si chiama modello \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\).
Esempio 9.3: modello \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\)
Il modello duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) per l'istanza del KP dell'Esempio 9.1 è:
Una soluzione ottima \(~{\tilde{\pi}}(D(\mathrm{LP}\text{-}0_{\mathrm{KP}}))\) è:
Il valore ottimo \(z(D(\mathrm{LP}\text{-}0_{\mathrm{KP}}))\) è \(27\).
- La seguente proposizione fornisce le formule per calcolare una soluzione ottima del modello primale \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\) e del modello duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\).
Proposizione 9.1
Se il primo oggetto \(j=1\) ha l'efficienza massima, una soluzione ottima del modello primale \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\) è:
e una soluzione ottima del modello duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) è:
Corollario 9.2
Il valore ottimo dei modelli primale \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\) e duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) è:
-
La dimostrazione procede in tre passi:
-
mostriamo che \(\eqref{PP_0}\) è una soluzione ammissibile del modello primale \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\);
-
mostriamo che \(\eqref{DD_0}\) è una soluzione ammissibile del modello duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\);
-
mostriamo che le due soluzioni ammissibili hanno lo stesso valore della funzione obiettivo.
Quindi, per la dualità forte della PL, \(\eqref{PP_0}\) e \(\eqref{DD_0}\) sono una coppia di soluzioni ottime primale e duale.
-
Dimostrazione
-
1. Abbiamo:
\[ \sum_{j \in \mathscr{I}} w_j \, \tilde{x}_j = w_1 \; \frac{c}{w_1} = c \]quindi il vincolo \(\eqref{cons1_KP}\) è soddisfatto.
Poiché \(\tilde{x}_j \ge 0\), per ogni \(j \in \mathscr{I}\), i vincoli \(\eqref{cons2_KP_LP}\) sono soddisfatti.
Quindi \(\eqref{PP_0}\) è una soluzione ammissibile del modello primale \(\mathrm{LP}\text{-}0_{\mathrm{KP}}\).
-
2. Per ogni \(j \in \mathscr{I}\), abbiamo:
\[ w_j \, \tilde{\pi} = w_j \; \frac{p_1}{w_1} \ge p_j \qquad \text{poiché} \qquad \frac{p_1}{w_1} \ge \frac{p_j}{w_j} \]quindi i vincoli \(\eqref{eq:KP-cap_LP_D_0}\) sono soddisfatti.
Abbiamo \(\tilde{\pi} \ge 0\), quindi il vincolo \(\eqref{eq:KP-cont1_LP_D_0}\) è soddisfatto.
Quindi \(\eqref{DD_0}\) è una soluzione ammissibile del modello duale \(D(\mathrm{LP}\text{-}0_{\mathrm{KP}})\).
-
3. Per le funzioni obiettivo abbiamo:
\[ \sum_{j \in \mathscr{I}} p_j \, \tilde{x}_j = p_1 \; \frac{c}{w_1} = c \, \tilde{\pi} \]quindi i valori delle funzioni obiettivo primale e duale coincidono.
Quindi, per la dualità forte della PL, \(\eqref{PP_0}\) e \(\eqref{DD_0}\) sono una coppia di soluzioni ottime primale e duale. □
9.4 Un secondo rilassamento lineare¶
Per ottenere un rilassamento lineare del modello \(\mathrm{ILP}_{\mathrm{KP}}\), rilassiamo i vincoli \(\eqref{cons2_KP}\) con i seguenti:
Questo modello PL si chiama modello \(\mathrm{LP}_{\mathrm{KP}}\).
Esempio 9.4: modello \(\mathrm{LP}_{\mathrm{KP}}\)
Il modello \(\mathrm{LP}_{\mathrm{KP}}\) per l'istanza del KP dell'Esempio 9.1 è:
Una soluzione ottima \(~{\tilde{\vet x}}(\mathrm{LP}_{\mathrm{KP}})\) è:
Il valore ottimo \(z(\mathrm{LP}_{\mathrm{KP}})\) è \(\frac{49}{3}\).
Di conseguenza, abbiamo l'upper bound:
Con una variabile duale non negativa \(\pi\) per il vincolo \(\eqref{cons1_KP}\) e una variabile duale non negativa \(\mu_j\) per ogni vincolo \(\eqref{cons2_KP_LP_bis}\), il modello duale del modello \(\mathrm{LP}_{\mathrm{KP}}\) è:
Questo modello PL si chiama modello \(D(\mathrm{LP}_{\mathrm{KP}})\).
Esempio 9.5: modello \(D(\mathrm{LP}_{\mathrm{KP}})\)
Il modello duale \(D(\mathrm{LP}_{\mathrm{KP}})\) per l'istanza del KP dell'Esempio 9.1 è:
Una soluzione ottima \((\tilde{\pi},\tilde{\vet \mu})(D(\mathrm{LP}_{\mathrm{KP}}))\) è:
Il valore ottimo \(z(D(\mathrm{LP}_{\mathrm{KP}}))\) è \(\frac{49}{3}\).
9.4.1 Efficienza degli oggetti¶
Definizione 9.3: efficienza
L'efficienza di un oggetto \(j \in \mathscr{I}\) è il rapporto fra il suo profitto e il suo peso:
- L'efficienza di un oggetto misura la sua redditività per unità di peso: indica quanto profitto si ottiene per ogni unità di peso.
Esempio 9.6: efficienze degli oggetti
Consideriamo l'istanza del KP dell'Esempio 9.1. Abbiamo:
| Oggetti | \(j=1\) | \(j=2\) | \(j=3\) | \(j=4\) | \(j=5\) | \(j=6\) | |
|---|---|---|---|---|---|---|---|
| Profitti | \(p_j\) | \(6\) | \(5\) | \(8\) | \(9\) | \(6\) | \(7\) |
| Pesi | \(w_j\) | \(2\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
| Efficienze | \(\frac{p_j}{w_j}\) | \(3\) | \(\frac{5}{3}\) | \(\frac{4}{3}\) | \(\frac{9}{7}\) | \(\frac{6}{5}\) | \(\frac{7}{9}\) |
Gli oggetti sono ordinati per efficienza non crescente, poiché:
Ordinare gli oggetti per efficienza non crescente richiede un algoritmo di ordinamento con tempo di calcolo \(O(n \log n)\), che è una funzione polinomiale del numero \(n\) di oggetti.
9.4.2 Oggetto critico e capacità residua¶
Definizione 9.4: oggetto critico e capacità residua
Dato un insieme \(\mathscr{I}=\{1,2,\dots,n\}\) di \(n\) oggetti ordinati per efficienza non crescente, l'oggetto critico è l'oggetto
e la capacità residua è
-
L'oggetto critico è il primo che non entra per intero nello zaino se tutti i precedenti sono selezionati. In inglese si chiama split item, break item o critical item, e si può scrivere come
\[\begin{equation*} s = \min \left\{ j \in \mathscr{I} : \sum_{k=1}^{j} w_k > c \right\} \end{equation*}\] -
La capacità residua è la capacità dello zaino che resta quando tutti gli oggetti che precedono l'oggetto critico sono selezionati. Soddisfa \(0 \le \mathit{rc} < w_s\).
Esempio 9.7: oggetto critico e capacità residua
Per l'istanza del KP dell'Esempio 9.1, l'oggetto critico è \(s=3\) poiché:
e la capacità residua è:
- La seguente proposizione fornisce le formule per calcolare una soluzione ottima del modello primale \(\mathrm{LP}_{\mathrm{KP}}\) e del modello duale \(D(\mathrm{LP}_{\mathrm{KP}})\).
Proposizione 9.5
Se gli oggetti sono ordinati per efficienza non crescente, una soluzione ottima del modello primale \(\mathrm{LP}_{\mathrm{KP}}\) è:
e una soluzione ottima del modello duale \(D(\mathrm{LP}_{\mathrm{KP}})\) è:
Corollario 9.6
Il valore ottimo dei modelli primale \(\mathrm{LP}_{\mathrm{KP}}\) e duale \(D(\mathrm{LP}_{\mathrm{KP}})\) è:
-
La dimostrazione procede in tre passi:
-
mostriamo che \(\eqref{PP}\) è una soluzione ammissibile del modello primale \(\mathrm{LP}_{\mathrm{KP}}\);
-
mostriamo che \(\eqref{DD}\) è una soluzione ammissibile del modello duale \(D(\mathrm{LP}_{\mathrm{KP}})\);
-
mostriamo che le due soluzioni ammissibili hanno lo stesso valore della funzione obiettivo.
Quindi, per la dualità forte della PL, \(\eqref{PP}\) e \(\eqref{DD}\) sono una coppia di soluzioni ottime primale e duale.
-
Dimostrazione
-
1. Abbiamo:
\[ {\sum_{j \in \mathscr{I}} w_j \, \tilde{x}_j} = \sum_{j=1}^{s-1} w_j + w_s \frac{\mathit{rc}}{w_s} = \sum_{j=1}^{s-1} w_j + c - \sum_{j=1}^{s-1} w_j = c \]quindi il vincolo \(\eqref{cons1_KP}\) è soddisfatto.
Poiché \(\mathit{rc} < w_s\), abbiamo \(0 \le \tilde{x}_j \le 1\), per ogni \(j \in \mathscr{I}\). Di conseguenza, i vincoli \(\eqref{cons2_KP_LP_bis}\) e \(\eqref{cons2_KP_LP_tris}\) sono soddisfatti.
Quindi \(\eqref{PP}\) è una soluzione ammissibile del modello primale \(\mathrm{LP}_{\mathrm{KP}}\).
□
Dimostrazione
-
2. Per ogni \(j \in \{1,2,\dots, s-1\}\), abbiamo:
\[ w_j \, \tilde{\pi} + \tilde{\mu}_j = w_j \; \frac{p_s}{w_s } + \bigg(p_j - w_j \; \frac{p_s}{w_s }\bigg) = p_j \]e, per ogni \(j \in \{s,s+1\dots, n\}\), abbiamo:
\[ w_j \, \tilde{\pi} + \tilde{\mu}_j = w_j \; \frac{p_s}{w_s } \ge p_j \text{ poiché } \frac{p_s}{w_s } \ge \frac{p_j}{w_j} \]quindi i vincoli \(\eqref{eq:KP-cap_LP_D}\) sono soddisfatti.
Abbiamo \(\tilde{\pi} \ge 0\). Per ogni \(j \in \{1,2,\dots, s - 1\}\), abbiamo:
\[ p_j - w_j \; \frac{p_s}{w_s} \ge 0 \text{ poiché } \frac{p_j}{w_j} \ge \frac{p_s}{w_s } \]di conseguenza, \(\tilde{\mu}_j \ge 0\) per ogni \(j \in \mathscr{I}\). Quindi il vincolo \(\eqref{eq:KP-cont1_LP_D}\) e i vincoli \(\eqref{eq:KP-cont2_LP_D}\) sono soddisfatti.
Quindi \(\eqref{DD}\) è una soluzione ammissibile del modello duale \(D(\mathrm{LP}_{\mathrm{KP}})\).
-
3. Per le funzioni obiettivo abbiamo:
\[\begin{align*} {\sum_{j \in \mathscr{I}} p_j \, \tilde{x}_j} & = \sum_{j=1}^{s-1} p_j + p_s \; \frac{\mathit{rc}}{w_s}\\[1.5ex] &= \sum_{j=1}^{s-1} p_j + \frac{p_s}{w_s} \; \left(c - \sum_{j=1}^{s-1} w_j \right)\\[1.5ex] &= c \; \frac{p_s}{w_s} + \sum_{j=1}^{s-1} \left( p_j - w_j \; \frac{p_s}{w_s} \right) \\[1.5ex] &=c \, \tilde{\pi} + \;\;{\sum_{j \in \mathscr{I}} \tilde{\mu}_j} \end{align*}\]quindi i valori delle funzioni obiettivo primale e duale coincidono.
Quindi, per la dualità forte della PL, \(\eqref{PP}\) e \(\eqref{DD}\) sono una coppia di soluzioni ottime primale e duale. □
Nella maggior parte delle istanze del KP il rapporto fra \(z(\mathrm{LP}_{\mathrm{KP}})\) e \(z(\mathrm{ILP}_{\mathrm{KP}})\) supera di poco uno: \(z(\mathrm{LP}_{\mathrm{KP}})\) è tipicamente un upper bound stretto per \(z(\mathrm{ILP}_{\mathrm{KP}})\).
-
Riportiamo una dimostrazione alternativa delle formule \(\eqref{PP}\). Procediamo per assurdo, dimostrando che una soluzione diversa non può essere ottima.
-
In questa dimostrazione supponiamo che gli oggetti con la stessa efficienza siano fusi in un unico oggetto. Poiché possiamo scegliere qualunque frazione di un oggetto, questo non cambia il problema, ed evitiamo di discutere le soluzioni simmetriche.
Dimostrazione
Supponiamo che \(\bar{\vet x}=(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)\) sia una soluzione ottima di \(\mathrm{LP}_{\mathrm{KP}}\) diversa da \(\tilde{\vet x}= (\tilde{x}_1,\tilde{x}_2,\dots,\tilde{x}_n)\) determinata con le formule \(\eqref{PP}\). Ogni soluzione ottima di \(\mathrm{LP}_{\mathrm{KP}}\) ha peso totale pari a \(c\), cioè il vincolo \(\eqref{cons1_KP}\) è soddisfatto all'uguaglianza (altrimenti si può migliorare).
Supponiamo che non esista una coppia di oggetti \(h<k\) con \(\bar{x}_h<1\) e \(\bar{x}_k>0\). Allora \(\bar{\vet x}\) seleziona gli oggetti in ordine di efficienza, riempiendo lo zaino oggetto per oggetto fino al peso \(c\): questa è esattamente \(\tilde{\vet x}\), assurdo. Quindi una tale coppia di oggetti \(h<k\) esiste (il caso \(k=s\) è incluso).
Sia:
Costruiamo una nuova soluzione ammissibile \(\hat{\vet x} = (\hat{x}_1,\hat{x}_2,\dots, \hat{x}_n)\) identica a \(\bar{\vet x}\) tranne che:
Per la definizione di \(d\), abbiamo \(\hat{x}_k \ge 0\) e \(\hat{x}_h \le 1\), e \(\hat{\vet x}\) è una soluzione ammissibile poiché:
Il valore della funzione obiettivo di \(\hat{\vet x}\) è:
Allora il valore della funzione obiettivo di \(\hat{\vet x}\) è maggiore del valore della funzione obiettivo di \(\bar{\vet x}\), contro il fatto che \(\bar{\vet x}\) è una soluzione ottima.
La disuguaglianza stretta \(p_h/w_h > p_k/w_k\) vale per ogni \(h<k\), poiché gli oggetti con la stessa efficienza sono stati fusi. □
Esempio 9.8: soluzioni primale e duale dei modelli PL
Per l'istanza del KP dell'Esempio 9.1, abbiamo \(s=3\) e \(\mathit{rc} = 4\).
Con le formule \(\eqref{PP}\), calcoliamo la seguente soluzione ottima del modello \(\mathrm{LP}_{\mathrm{KP}}\):
Con le formule \(\eqref{DD}\), calcoliamo la seguente soluzione ottima del modello \(D(\mathrm{LP}_{\mathrm{KP}})\):
Con la formula \(\eqref{VAL}\), il valore ottimo di entrambi i modelli PL, primale e duale, è:
9.4.3 Alcune proprietà teoriche importanti¶
- Le due proposizioni seguenti mostrano che il rapporto fra \(z(\mathrm{LP}_{\mathrm{KP}})\) e \(z(\mathrm{ILP}_{\mathrm{KP}})\) è al più due per tutte le istanze del KP. Inoltre, esistono istanze per cui il valore due si raggiunge asintoticamente quando la capacità \(c \to +\infty\).
Proposizione 9.7
Per ogni istanza del KP abbiamo:
Dimostrazione
Consideriamo due soluzioni ammissibili del modello \(\mathrm{ILP}_{\mathrm{KP}}\):
-
La soluzione che seleziona tutti gli oggetti che precedono l'oggetto critico:
\[ \bar{x}_j = 1, \quad \forall j \in \{1,2,\dots, s-1\} \quad \text{e} \quad \bar{x}_j = 0, \quad \forall j \in \{s, s+1, \dots, n\} \]che è ammissibile per definizione di oggetto critico, e fornisce il lower bound valido:
\[ \sum_{j=1}^{s-1} p_j \le z(\mathrm{ILP}_{\mathrm{KP}}) \] -
La soluzione che seleziona solo l'oggetto critico:
\[ \bar{x}_j = 0, \quad \forall j \in \mathscr{I} \setminus \{s\} \quad \text{e} \quad \bar{x}_s = 1 \]che è ammissibile per l'ipotesi \(w_s \le c\), e fornisce il lower bound valido:
\[ p_s \le z(\mathrm{ILP}_{\mathrm{KP}}) \]
Sommando le due disuguaglianze otteniamo:
e quindi:
□
Proposizione 9.8
Esistono istanze del KP tali che:
Dimostrazione
Dato \(\vartheta \in \Z_{\ge 1}\), consideriamo l'istanza del KP con capacità dello zaino \(c = 2\vartheta\) e \(n = 2\) oggetti con i seguenti profitti e pesi:
Poiché si può selezionare un solo oggetto, una soluzione ottima \({\tilde{\vet x}}(\mathrm{ILP}_{\mathrm{KP}})\) del modello \(\mathrm{ILP}_{\mathrm{KP}}\) è:
L'oggetto critico è \(s = 2\), e la capacità residua è:
Di conseguenza, una soluzione ottima \({\tilde{\vet x}}(\mathrm{LP}_{\mathrm{KP}})\) del modello \(\mathrm{LP}_{\mathrm{KP}}\) è:
Ne segue che:
Di conseguenza, concludiamo che:
□
9.5 Upper bound per il problema dello zaino 0/1¶
- Le due proposizioni seguenti richiedono che gli oggetti siano ordinati per efficienza non crescente.
Proposizione 9.9: upper bound di Dantzig
Per ogni istanza del KP abbiamo:
e \(\UB_{\mathrm{D}}\) si chiama upper bound di Dantzig per il KP.
Dimostrazione
Abbiamo:
che è un upper bound valido per \(z(\mathrm{ILP}_{\mathrm{KP}})\) poiché \(p_j \in \Z_{\ge 1}\), per ogni \(j \in \mathscr{I}\). □
- Il bound di Martello-Toth usa gli oggetti \(s-1\) e \(s+1\). Poiché \(w_1 \le c\) e \(\sum_{j} w_j > c\) abbiamo \(s \ge 2\), quindi l'oggetto \(s-1\) esiste sempre. Se \(s = n\) l'oggetto \(s+1\) non esiste, e poniamo \(p_{n+1}/w_{n+1} := 0\): in questo caso \(\UB_0 = \sum_{j=1}^{s-1} p_j\).
Proposizione 9.10: upper bound di Martello-Toth
Per ogni istanza del KP abbiamo:
dove
e \(\UB_{\mathrm{MT}}\) si chiama upper bound di Martello-Toth per il KP.
Dimostrazione
Poiché \(x_s\) non può assumere un valore frazionario, una soluzione ottima \({\tilde{\vet x}}(\mathrm{ILP}_{\mathrm{KP}})\) si ottiene da una soluzione ottima \({\tilde{\vet x}}(\mathrm{LP}_{\mathrm{KP}})\) o senza l'oggetto critico \(s\) o con l'oggetto critico \(s\), e quindi togliendo almeno uno dei primi \(s-1\) oggetti.
-
Se l'oggetto critico è escluso, abbiamo \(z(\mathrm{ILP}_{\mathrm{KP}}) \le \UB_0\) poiché la capacità residua \(\mathit{rc}\) si riempie con oggetti di efficienza massima possibile \(\frac{p_{s+1}}{w_{s+1}}\)
-
Se l'oggetto critico è incluso, abbiamo \(z(\mathrm{ILP}_{\mathrm{KP}}) \le \UB_1\) poiché supponiamo che l'oggetto da togliere abbia esattamente il peso minimo necessario \(w_s- \mathit{rc}\) e l'efficienza minima possibile \(\frac{p_{s-1}}{w_{s-1}}\) □
Esempio 9.9: upper bound di Dantzig e di Martello-Toth
Per l'istanza del KP dell'Esempio 9.1, con la formula \(\eqref{DANTZIG}\) calcoliamo l'upper bound di Dantzig:
Con la formula \(\eqref{boundMT}\) calcoliamo l'upper bound di Martello-Toth:
Per questa istanza del KP, l'upper bound di Martello-Toth è forte quanto l'upper bound di Dantzig.