Problema dello Zaino

Sia un insieme di oggetti.

Ad ogni oggetto si associano un profitto e un peso , entrambi interi positivi.

Sia la capacità.

Problema dello Zaino

Consiste nello scegliere quali oggetti inserire nello zaino in modo da massimizzare il profitto, rispettando il vincolo sulla capacità.

Definizione Formale

Il problema fa parte dei problemi di riempimento.

Problema di Riempimento

Siano sottoinsiemi di e sia il profitto associato ad ogni .

Il problema di riempimento consiste nel determinare la sottofamiglia degli insiemi che sia di profitto massimo e tale che ogni elemento di appartenga al più ad un solo sottoinsieme di .

Approccio Euristico

Si costruisce una soluzione inserendo nello zaino per primi gli elementi migliori secondo un certo criterio.

Ci sono tre criteri:

1. Peso non decrescente (inseriamo molti oggetti)
2. Profitto non decrescente (inseriamo oggetti di maggior valore)
3. Rapporto profitto/peso decrescente (più efficace)

Comunque con questo approccio non si arriva all’ottimo

Metodo (esatto) Branch and Bound per lo zaino

Per applicare il Metodo del Branch and Bound dobbiamo specificare:

• Come ottenere l’upper bound
• Come fare branching
• Come ottenere un lower bound

Per l’operazione di bounding adottiamo l’eliminazione del vincolo di interezza (RL|), perciò risolviamo il problema di PL:

Si potrebbe usare il simplesso ma è più efficace un altro metodo.

Si sceglie il criterio di ordinamento decrescente.

Si ordinano gli oggetti secondo questo criterio e si inizia l’inserimento. Supponiamo che si possano inserire i primi oggetti, ma non l’oggetto

e

Inseriamo per intero i primi oggetti:

Mentre l’oggetto sarà inserito frazionalmente (in parte):

Lo zaino è pieno

Il valore ottimo è

infatti è detta variabile critica ed è la variabile di branch, che effettua la partizione.

Un Lower Bound si ottiene considerando come Soluzione Intera Ammissibile l’arrotondamento per difetto della soluzione del rilassamento lineare .

• Soluzione

• L’arrotondamento è:

• e il lower bound:

Come strategia si usa in genere il best bound.

Esempio (WIP)