Vai al contenuto

Formulazioni dei problemi di zaino

Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 9 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di zaino · App: Rilassamento continuo e upper bound per lo zaino 0/1

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • scrivere il modello PLI del problema dello zaino 0/1 e spiegare ciascuno dei suoi vincoli;

  • scrivere i modelli PLI del SSP, del BKP, dell'UKP, del MDKP, del MKP, del MCKP e del KPS, e scriverli su un'istanza numerica;

  • scrivere i due rilassamenti lineari e i loro duali, e calcolarne le soluzioni ottime con formule chiuse;

  • calcolare l'oggetto critico, la capacità residua e il valore \(z(\mathrm{LP}_{\mathrm{KP}})\);

  • calcolare gli upper bound di Dantzig e di Martello-Toth, arrotondandoli correttamente;

  • spiegare perché \(z(\mathrm{LP}_{\mathrm{KP}})\) non supera mai il doppio di \(z(\mathrm{ILP}_{\mathrm{KP}})\).

9.1 Panoramica della famiglia

  • I modelli PLI dei problemi di zaino usano una variabile \(x_j\) per ogni oggetto \(j \in \mathscr{I}\): una variabile binaria quando l'oggetto è selezionato o no, una variabile intera quando conta le copie selezionate dell'oggetto.

  • Ogni capacità dà un vincolo di zaino sul peso totale degli oggetti selezionati, e la funzione obiettivo ne massimizza il profitto totale.

  • I membri della famiglia aggiungono un indice alle variabili (lo zaino \(k\) dell'oggetto \(j\) nel MKP), alcuni vincoli sulle classi di oggetti (MCKP, KPS) o variabili binarie di setup \(y_h\) (KPS).

Lo schema comune dei modelli di zaino è

\[ \max \Big\{ \sum_{j \in \mathscr{I}} p_j \, x_j \;:\; \sum_{j \in \mathscr{I}} w_j \, x_j \le c,~~ x_j \in D_j~~ \forall j \in \mathscr{I} \Big\}, \]

dove il dominio \(D_j\) è \(\{0,1\}\), \(\{0,1,\dots,b_j\}\) o \(\Z_{\ge 0}\). I membri della famiglia cambiano i domini e aggiungono capacità, zaini o classi.

  • La tabella elenca i membri della famiglia, con il nome del loro modello PLI e la sezione che lo scrive.
Problema Modello Variabili Sezione
KP \(\mathrm{ILP}_{\mathrm{KP}}\) binarie \(x_j\) 9.2
SSP \(\mathrm{ILP}_{\mathrm{SSP}}\) binarie \(x_j\) 9.6
BKP \(\mathrm{ILP}_{\mathrm{BKP}}\) intere \(x_j \in \{0,1,\dots,b_j\}\) 9.7
UKP \(\mathrm{ILP}_{\mathrm{UKP}}\) intere \(x_j \in \Z_{\ge 0}\) 9.8
MDKP \(\mathrm{ILP}_{\mathrm{MDKP}}\) binarie \(x_j\), un vincolo per capacità 9.9
MKP \(\mathrm{ILP}_{\mathrm{MKP}}\) binarie \(x_{jk}\), oggetto \(j\) nello zaino \(k\) 9.10
MCKP \(\mathrm{ILP}_{\mathrm{MCKP}}\) binarie \(x_j\), un oggetto per classe 9.11
KPS \(\mathrm{ILP}_{\mathrm{KPS}}\) binarie \(x_j\) e variabili di setup \(y_h\) 9.12

  • Panoramica

    Panoramica della famiglia

    Apri

  • 9.2 Un modello PLI per il problema dello zaino 0/1

    Efficienza degli oggetti · Oggetto critico e capacità residua · Alcune proprietà teoriche importanti

    Apri

  • 9.6 Un modello PLI per il problema del subset sum

    Apri

  • 9.7 Un modello PLI per il problema dello zaino limitato

    Apri

  • 9.8 Un modello PLI per il problema dello zaino illimitato

    Apri

  • 9.9 Un modello PLI per il problema dello zaino multidimensionale

    Apri

  • 9.10 Un modello PLI per il problema degli zaini multipli

    Apri

  • 9.11 Un modello PLI per il problema dello zaino a scelta multipla

    Apri

  • 9.12 Un modello PLI per il problema dello zaino con setup

    In sintesi

    Apri

Avanti: 9.2 Un modello PLI per il problema dello zaino 0/1

Esercizi su questo capitolo: Problemi di zaino

Nel laboratorio interattivo: Rilassamento continuo e upper bound per lo zaino 0/1.