Problema dello zaino 0/1 (KP)¶
Definizione 1: Problema dello zaino 0/1
Dati:
-
uno zaino di capacità \(c \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}\) e un peso \(w_j \in \Z_{\ge 1}\),
il problema dello zaino 0/1 (KP) chiede di decidere quali oggetti inserire nello zaino, in modo che il peso totale degli oggetti selezionati non superi la capacità dello zaino e il profitto totale degli oggetti selezionati sia massimo.
Ipotesi
-
Facciamo le seguenti ipotesi:
-
Il peso totale di tutti gli oggetti supera la capacità dello zaino (altrimenti si potrebbero selezionare tutti gli oggetti). Formalmente:
\[ \sum_{j \in \mathscr{I}} w_j > c \] -
Ogni oggetto, da solo, entra nello zaino (altrimenti non può essere selezionato). Formalmente:
\[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]
-
Che cosa fa il corso su questo problema¶
Proprietà¶
-
NP-difficile in senso debole: la programmazione dinamica lo risolve in \(\Theta(nc)\) passi, un tempo pseudo-polinomiale (Cap. 1).
-
Bound di cardinalità: se entrano al più \(\bar k\) oggetti, \(z(I)\) è al più la somma dei \(\bar k\) profitti più grandi (Cap. 2).
-
Ordinare per efficienza non basta: sull'istanza del Cap. 2 si ottiene profitto \(11\), mentre l'ottimo è \(15\) (Cap. 2).
Formulazioni¶
-
Il modello \(\ILP_{\KP}\) ha una variabile binaria per oggetto e un vincolo di capacità (Cap. 9).
-
Il rilassamento \(\LP_{\KP}\) si risolve ordinando gli oggetti per efficienza: si prendono gli oggetti prima dell'oggetto critico \(s\), e \(s\) solo in parte (Cap. 9).
-
\(z(\LP_{\KP}) \le 2\, z(\ILP_{\KP})\), e il rapporto \(2\) è raggiunto al limite (Cap. 9).
-
Arrotondando per difetto \(z(\LP_{\KP})\) si ottiene il bound di Dantzig \(\UB_{\mathrm{D}}\); il bound di Martello–Toth \(\UB_{\mathrm{MT}}\) considera l'oggetto critico fuori e dentro lo zaino (Cap. 9).
Programmazione dinamica¶
-
La ricorrenza \(v(j,k)\) su oggetti e capacità richiede \(\Theta(nc)\) passi (Cap. 17).
-
Le liste degli stati non dominati tengono solo gli stati raggiungibili, al più \(\min\{2^j, c+1\}\) per stadio (Cap. 17).
-
La PD sui profitti richiede \(\Theta(nP)\) passi; è il nucleo dell'FPTAS (Cap. 17).
-
Così anche l'SSP, l'MCKP e il KPS, in \(\Theta(nc)\) passi; per l'MDKP e l'MKP la tabella cresce esponenzialmente con il numero di capacità (Cap. 20, Cap. 21, Cap. 22, Cap. 23, Cap. 24).
Euristiche¶
-
Greedy per profitto, per peso e per efficienza: sull'istanza a quattro oggetti del Cap. 29 (ottimo \(17\)) danno \(17\), \(10\) e \(16\) (Cap. 30).
-
Ricerca locale con flip e swap: first improvement e best improvement raggiungono \(17\) per strade diverse (Cap. 31).
-
Una penalità sul peso in eccesso permette alla ricerca di attraversare soluzioni non ammissibili; con \(\alpha>\max_j p_j\) i suoi ottimi locali sono ammissibili (Cap. 31).
-
Simulated annealing, GRASP, algoritmi genetici e memetici; su KP20 l'algoritmo memetico raggiunge l'ottimo \(521\) in ogni esecuzione (Cap. 32).
Euristiche MIP¶
-
Arrotondare per difetto la soluzione del rilassamento lineare dà sempre una soluzione ammissibile, perché il modello ha un solo vincolo di packing (Cap. 33).
-
Sull'istanza del Cap. 29 il diving frazionario si ferma a \(16\) e RINS fallisce, mentre local branching e proximity search raggiungono l'ottimo \(17\) e ne dimostrano l'ottimalità (Cap. 33).
Approssimazione¶
-
L'algoritmo greedy non ha una garanzia costante; Ext-Greedy è un algoritmo \(2\)-approssimato, e il bound è tight (Cap. 35).
-
\(H^{\ell}\) garantisce \(\frac{\ell+2}{\ell+1}\) in tempo \(O(n^{\ell+1})\), e quindi dà un PTAS (Cap. 35).
-
Il Basic-FPTAS scala i profitti e garantisce \(\frac{1}{1-\varepsilon}\) in tempo \(O(n^2/\varepsilon)\) (Cap. 35).
-
Nessun algoritmo polinomiale ha una garanzia assoluta fissata, a meno che non risolva il KP in modo esatto (Cap. 35).
Algoritmi ad hoc¶
- Il rilassamento lineare di un nodo si risolve con le formule di Dantzig, senza il simplesso, e ha una sola variabile frazionaria: l'oggetto critico, su cui si fa branching (Cap. 41).