Formulazioni dei problemi di packing¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 10 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di packing
Prerequisiti
-
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità»: il duale di un problema LP, dualità debole e forte.
-
Dal modulo Programmazione lineare intera, Capitolo 1 «Programmazione lineare intera» e Capitolo 2 «Bound primali e duali»: problemi PLI, rilassamenti lineari e bound.
-
Da questo modulo, Capitolo 3 «Problemi di packing»: il problema e le sue ipotesi.
Obiettivi
Al termine di questo capitolo saremo in grado di:
-
scrivere il modello PLI del problema del bin packing e spiegare il legame fra le variabili di assegnamento e le variabili di attivazione;
-
scrivere i due rilassamenti lineari e i loro duali, e dimostrare che il loro valore ottimo è \(\sum_{j} w_j / c\);
-
arrotondare per eccesso il bound del rilassamento per ottenere un lower bound sul numero di contenitori;
-
dimostrare che il bound del rilassamento è almeno la metà del valore ottimo, e che il fattore è tight;
-
scrivere il modello PLI del problema del cutting stock, con variabili intere per le copie degli oggetti.
10.1 Panoramica della famiglia¶
-
I modelli PLI dei problemi di packing usano un upper bound \(m\) sul numero di contenitori e l'insieme \(\mathscr{B} = \{1,2,\dots,m\}\) dei contenitori che si possono usare.
-
Le variabili di assegnamento \(x_{jb}\) mettono gli oggetti \(j \in \mathscr{I}\) nei contenitori \(b \in \mathscr{B}\), e le variabili di attivazione binarie \(y_b\) dicono se il contenitore \(b\) è usato.
-
Ogni contenitore dà un vincolo di capacità, che collega anche i due tipi di variabili, e la funzione obiettivo minimizza il numero \(\sum_{b \in \mathscr{B}} y_b\) di contenitori usati.
I modelli di packing sono modelli di assegnamento: ogni oggetto, o ogni copia di un oggetto, è assegnato a un contenitore usato, e gli oggetti assegnati a un contenitore ne rispettano la capacità. I membri della famiglia cambiano il dominio delle variabili di assegnamento.
- La tabella elenca i membri della famiglia, con il nome del loro modello PLI e la sezione che lo scrive.
| Problema | Modello | Variabili di assegnamento | Sezione |
|---|---|---|---|
| BPP | \(\mathrm{ILP}_{\mathrm{BPP}}\) | binarie \(x_{jb}\) | 10.2 |
| CSP | \(\mathrm{ILP}_{\mathrm{CSP}}\) | intere \(x_{jb}\), le copie dell'oggetto \(j\) nel contenitore \(b\) | 10.5 |
Avanti: 10.2 Un modello PLI per il problema del bin packing
Esercizi su questo capitolo: Problemi di packing