Problema Bin-Packing

uni
Questo è un Problema di Programmazione Lineare Intera (PLI).
Ho un numero di oggetti di cui conosco il peso e ho un indeterminato numero di contenitori (Bin) di cui conosco la capienza.
Trovare l’assegnamento che porti all’utilizzo del minor numero possibile di contenitori.

Modello

$n$ oggetti, $m$ contenitori
Variabili:

• $x_{ij}=(j\grave{e}dentroi)?1:0$
• $y_i=(i\grave{e}usato)?1:0$

$$\{\begin{array}{l}\min {\sum }_{i=1}^m{y}_i\\ {\sum }_{i=1}^m{x}_{ij}=1\forall j\in [i;n]\\ {\sum }_{j=1}^n{p}_j{x}_{ij}\le C{y}_i\forall i\in [i;m]\\ x_{ij}\in \{0,1\}\\ y_i\in \{0,1\}\end{array}$$

$A$ è di dimensioni: $(n+m)\times (n\cdot m+m)$

Risoluzione

Essendo questo un problema di PLI, troviamo una $V_S$, una $V_I$, e applichiamo un algoritmo di riduzione del gap.
Il più adatto, per la natura binaria del problema, è l’Algoritmo di Riduzione del Gap Branch and Bound.
Abbiamo bisogno di una approssimazione del numero di bin necessari, meno ne mettiamo nel modello e più velocizziamo. Alla peggio dovremo utilizzare $n$ contenitori (numero di oggetti).

Algoritmi per la Vs

Per trovare la soluzione ottimale abbiamo 3 algoritmi, in ordine di accuratezza:
decreasing = ordinare oggetti per peso decrescente

1. next-fit-decreasing:
   Il primo contenitore é il contenitore corrente.
   Se possibile, assegna un oggetto al contenitore corrente;
   altrimenti assegnalo ad un nuovo contenitore, che diventa quello corrente.
2. first-fit-decreasing:
   Assegna ogni oggetto al primo contenitore usato che puó contenerlo.
   Se nessuno di essi puó contenerlo, assegna l’oggetto ad un nuovo contenitore.
3. best-fit-decreasing:
   ordino i bin per capienza rimanente decrescente
   prendo un oggetto, lo metto nel bin con minore capienza rimanente, se non entra, in quello dopo
   ripeto: riordino i bin, metto un oggetto, riordino ecc

Vi

La valutazione inferiore di questo problema è particolarmente semplice, è l’approssimazione per eccesso del valore associato alla soluzione del rilassato continuo del problema:

$$V_I=\lceil \frac{{\sum }_{j=1}^n{p}_j}{C}\rceil$$

Comando Matlab

Bisogna usare Intlinprog, la difficoltà è scrivere $b$ poiché è in funzione di un’altra variabile, le $y$.
Semplicemente porto le b, che sono $P{y}_i$, a sinistra dell’uguale, come fossero una ulteriore $x_{ij}$

# Nvariabili = Noggetti x Ncontenitori + Ncontenitori = Ncontenitori(Noggetti + 1)
# Aeq è Noggetti x Nvariabili, esempio 6x28
Aeq=[1000001000001000001000000000 ; 0100000100000100000100000000 ; 0010000010000010000010000000 ; ecc]
beq=[1 ; 1 ; 1 ; 1 ; 1 ; 1]
b=[0 ; 0 ; 0 ; 0]
A=[1riga ; 2riga ; 000000 000000 p1p2p3p4p5p6 000000 00 -P 0]