Problema del bin packing (BPP)¶
Definizione 1: Problema del bin packing
Dati:
-
un numero infinito di contenitori, ciascuno 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 peso \(w_j \in \Z_{\ge 1}\),
il problema del bin packing (BPP) chiede di decidere in quale contenitore sistemare ogni oggetto, in modo che il peso totale degli oggetti in ogni contenitore non superi la capacità del contenitore e il numero totale di contenitori usati sia minimo.
Ipotesi
-
Facciamo le seguenti ipotesi:
-
Il peso totale di tutti gli oggetti supera la capacità di un contenitore (altrimenti tutti gli oggetti entrerebbero in un solo contenitore). Formalmente:
\[ \sum_{j \in \mathscr{I}} w_j > c \] -
Ogni oggetto, da solo, entra in un contenitore (altrimenti non può essere impaccato). Formalmente:
\[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]
-
Che cosa fa il corso su questo problema¶
| Tecnica | Dove |
|---|---|
| Definizione | Cap. 3 «Problemi di packing» |
| Formulazioni | Cap. 10 «Formulazioni dei problemi di packing» |
| Euristiche | Cap. 29 «Algoritmi euristici: definizioni»; Cap. 30 «Euristiche costruttive»; Cap. 31 «Ricerca locale»; Cap. 32 «Metaeuristiche» |
| Euristiche MIP | Cap. 33 «Euristiche MIP per i problemi classici» |
| Approssimazione | Cap. 36 «Algoritmi di approssimazione per il bin packing» |
| Esercizi | Cap. 3 (6 esercizi); Esercizio 7.5; Cap. 10 (5 esercizi); Esercizio 29.2; Cap. 30 (3 esercizi); Cap. 31 (3 esercizi); Cap. 32 (2 esercizi); Esercizio 34.3; Cap. 36 (12 esercizi) |
Proprietà¶
-
NP-difficile in senso forte: non esiste un algoritmo pseudo-polinomiale, a meno che \(P=NP\) (Cap. 1).
-
Bound sui pesi \(\LB = \lceil \sum_j w_j / c \rceil\); non è sempre stretto: tre oggetti di peso \(6\) con \(c=10\) richiedono \(3\) contenitori, non \(2\) (Cap. 3).
Formulazioni¶
-
Il modello \(\ILP_{\BPP}\) ha \(mn\) variabili di assegnamento \(x_{jb}\) e \(m\) variabili di attivazione \(y_b\) (Cap. 10).
-
Entrambi i rilassamenti lineari valgono \(\sum_j w_j/c\): arrotondato per eccesso, è di nuovo il bound sui pesi (Cap. 10).
-
Il rapporto fra il bound del rilassamento lineare e l'ottimo è almeno \(\frac12\), e \(\frac12\) è raggiunto al limite (Cap. 10).
Euristiche¶
-
First Fit Decreasing e Best Fit Decreasing trovano l'ottimo \(3\) sull'istanza del Cap. 29; \(FFD(I) \le \frac{11}{9}\, z(I) + \frac{6}{9}\), tight (Cap. 30).
-
Il numero di contenitori è piatto, quindi la ricerca locale con move e swap usa l'obiettivo ausiliario \(\max \sum_b L_b^2\) (Cap. 31).
-
La VND con move e swap raggiunge l'ottimo in \(89\) esecuzioni su \(100\) su un'istanza con \(n=12\) (Cap. 31).
-
Large neighbourhood search: su BPP24 la riparazione esatta con \(q\ge 3\) raggiunge l'ottimo \(9\) in ogni esecuzione (Cap. 32).
Euristiche MIP¶
-
L'arrotondamento e il diving frazionario falliscono sull'istanza del Cap. 29: il rilassamento lineare distribuisce un oggetto su più contenitori (Cap. 33).
-
La feasibility pump trova sempre una soluzione ammissibile, ma può lasciare aperti contenitori vuoti (Cap. 33).
-
Su un'istanza con \(n=60\) tutta la difficoltà è primale: le euristiche di Gurobi decidono il tempo di soluzione (Cap. 33).