Vai al contenuto

Problemi di packing

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 3 · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di packing

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • enunciare la definizione del problema del bin packing e del problema del cutting stock, con istanze e soluzioni ammissibili;

  • spiegare le ipotesi sui dati;

  • contare le soluzioni candidate di una piccola istanza e riconoscere che sono partizioni;

  • trovare a mano una soluzione ammissibile e calcolare il bound sul peso;

  • usare i due bound per certificare che una soluzione è ottima.

3.1 Panoramica della famiglia

  • I problemi di packing hanno gli stessi dati: un numero infinito di contenitori identici di capacità \(c \in \Z_{\ge 1}\), un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti e, per ogni oggetto \(j \in \mathscr{I}\), un peso \(w_j \in \Z_{\ge 1}\).

  • Una soluzione assegna ogni oggetto, o ogni copia richiesta di un oggetto, a un contenitore: il peso totale degli oggetti in un contenitore non deve superare la capacità \(c\).

  • L'obiettivo è minimizzare il numero di contenitori usati.

Un problema di packing sistema tutti gli oggetti nel minor numero di contenitori di capacità \(c\). I membri della famiglia differiscono nel numero di copie di ogni oggetto da impaccare.

  • La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
Problema Sigla Oggetti da impaccare Sezione
problema del bin packing BPP una copia di ogni oggetto 3.2
problema del cutting stock CSP \(d_j\) copie dell'oggetto \(j\) 3.3

  • Panoramica

    Panoramica della famiglia

    Apri

  • 3.2 Il problema del bin packing

    Contare le soluzioni, una prima soluzione e un bound semplice

    Apri

  • 3.3 Il problema del cutting stock

    Contare le soluzioni, una prima soluzione e un bound semplice · Osservazioni · Errori tipici · In sintesi

    Apri

Avanti: 3.2 Il problema del bin packing

Esercizi su questo capitolo: Problemi di packing

Approfondimento: che cosa fa il corso su questo problema