Università degli Studi di Bologna
Facoltà di Ingegneria
Corso di Laurea in Ingegneria Informatica
Ottimizzazione Combinatoria
ALGORITMI EURISTICI
PER PROBLEMI DI PACKING
di
Alberto Nuzzo
Relatore: Chiar.mo Prof. Ing.Paolo Toth
Correlatori: Prof. Ing. Alberto Caprara
Dott. Ing. Michele Monaci
Anno Accademico 2001-2002
Il Bin Packing Problem
Dati:
n oggetti (items) con peso wj > 0 (j =1,…,n)
m contenitori (bin) identici con capacità c
Obiettivo:
inserire tutti gli items nei bin in modo che:
in ogni bin la somma dei pesi degli items
inseriti non superi la capacità del bin
stesso
il numero dei bin utilizzati sia minimo
Il Bin Packing Problem
Applicazioni:
taglio di unità standard di materia prima;
imballaggio per problemi di
immagazzinamento e di trasporto;
impaginazione articoli nei giornali;
problemi di determinazione di layout.
Il Bin Packing Problem
Modello Matematico “tradizionale”:
Indicando con :
– n numero di oggetti da inserire
– m numero di contenitori a disposizione
– N = {1, .. ,n} insieme degli oggetti da considerare
– M = {1, ..,m} insieme dei contenitori disponibili
– wj peso dell’oggetto j con wj  1 ( j  N )
– c capacità dei contenitori posta pari a 1
1 se e solo se l'oggetto j è inserito nel bin i
x 
ij 0 altrimenti
i  M, j  N
1 se e solo se il bin i è utilizzato
y 
i 0 altrimenti
iM
Il Bin Packing Problem
Modello Matematico “tradizionale”:
m
min  yi
i 1
(1)
subject to
n
 xij = 1
jN
(2)
j 1
 wj xij  yi  i  M
yi  {0,1}  i  M
xij  {0,1}  i  M,  j  N
m
(3)
i 1
BPP Complessità:
NP-HARD
(4)
(5)
Il Bin Packing Problem
Modello Matematico di tipo Set-Covering:
Sia S la famiglia di tutti gli insiemi di oggetti costituenti
riempimenti massimali ammissibili, ovvero:
S = {S  N :

jS
wj  1 ,  wj > 1 i  N\S }
jS i 
risulta:
min SS S
subject to
 S  1  j  N
jS
S  0
SS
S intero  S  S
dove:
 1 se e solo se

S = 
l' insieme di oggetti S
è assegnato a un contenitore
 0 altrimenti

Il Bin Packing Problem
Modello Matematico di tipo Set-Covering:
min SS S
subject to
 S  1  j  N
jS
S  0
SS
S intero  S  S
dove:
 1 se e solo se
S =
l' insieme di oggetti S

 è assegnato a un contenitore
 0 altrimenti

Caratteristiche:
– |S| elevata
– Set Covering  NP-Hard
Il Two-Dimensional Vector Packing
Problem
Generalizzazione del BPP è l’m-Dimensional Vector Packing
Problem (m-DVPP) in cui:
ogni oggetto j ha m attributi
wj1,…,wjm ≥
m
0 (j=1,…,n) con  wji > 0
i 1
i contenitori hanno m capacità c1,…,cm > 0
Ogni attributo è indipendente dagli altri.
2-DVPP: caso particolare del m-DVPP dove:
gli attributi degli oggetti e dei relativi contenitori sono 2
Il Two-Dimensional Vector Packing
Problem
Modello Matematico “tradizionale”:
m
min
 yi
i 1
subject to
n
 xij = 1
j 1
n
 wjxij  yi
j 1
 vjxij  yi
n
j 1
yi  0,1
xij  0,1
jN
iM
iM
iM
 i  M,  j  N
dove:
wj  1 peso dell’oggetto j nella prima dimensione (j=1,…,n)
vj  1 peso dell’oggetto j nella seconda dimensione (j=1,…,n)
c = d = 1 capacità contenitori nelle due dimensioni
Il Two-Dimensional Vector Packing
Problem
Modello Matematico di tipo set-covering:
Tale modello risulta
ridefinizione di S:
invariato
S=SN: 
wj  1 AND
jS
 w > 1 OR
j
jS i 
meno
 vj  1 ,
jS
 vj > 1  i  N\S 
jSi 
a
della
Il Two-Dimensional Bin
Packing Problem
Generalizzazione del BPP è l’m-Dimensional Bin Packing
Problem (m-DBPP) in cui:
ogni oggetto j ha m dimensioni wj1,…,wjm > 0 (j=1,…,n)
i contenitori hanno m capacità c1,…,cm > 0
Le varie dimensioni sono tra loro correlate.
2-DBPP: caso particolare dell’m-DBPP dove:
le dimensioni degli oggetti e dei relativi contenitori sono 2
Il Two-Dimensional Bin
Packing Problem
Applicazioni:
Problemi di impaccamento e caricamento
veicoli;
problemi di gestioni risorse;
problemi di taglio di unità standard di
materia prima.
w1
Il Two-Dimensional Bin
Packing Problem
h1
1
y
2
3
4
5
6
7
W
6
7
H
1
2
Bin 1
x
3
4
5
Bin 2
Items
Il Set Covering Problem
Definiamo:
A = (aij) matrice binaria di m righe ed n colonne
se aij = 1 si dice che la colonna j copre la riga i
c = (cj) vettore n-dimensionale dei costi dove cj
rappresenta il costo della colonna j ( j  S )
Obiettivo:
determinare un sottoinsieme di colonne S  N, di costo
minimo, tale che ogni riga i  M sia coperta come
minimo da almeno una colonna j  S
Il Set Covering Problem
Modello Matematico è il seguente:
min
subject to
 cjxj
jN

jN
aijxj  1
iM
xj  0,1  j  N
(1)
(2)
(3)
dove:
 1 se la colonna j è selezionat a nella soluzione
xj = 
 0 altrimenti
Nel caso dei problemi in esame si considera:
cj = 1  j  N
(j  S)
Algoritmo Proposto
Calcolo Lower Bound
Algoritmi Euristici
R
I
E
M
P
I
M
E
N
T
I
Algoritmo Esatto
Soluzione Ottima
Fine Algoritmo
Algoritmi Euristici
Perturbati
Hashing
C
YF
KTI
MATRICE SCP
Algoritmo Proposto
Calcolo Lower Bound
Algoritmi Euristici
R
I
E
M
P
I
M
E
N
T
I
Fase 1
Algoritmo Esatto
Soluzione Ottima
Fine Algoritmo
Algoritmi Euristici
Perturbati
Hashing
YKI
MATRICE SCP
Sistema Utilizzato
Gli algoritmi presentati relativamente alla Fase 1 sono
implementati in FORTRAN 77, mentre l’algoritmo
YKI è implementato in C++ e sono stati testati nel
laboratorio di Ricerca Operativa su un calcolatore in
dotazione al dipartimento del D.E.I.S., con le seguenti
caratteristiche:
Processore: PIII
Frequenza: 700Mhz
Memoria: 128Mb di RAM.
Le Istanze per il 2-DVPP
10 Classi ( 1,...,3 Spieksma; 4,...,10 Caprara e Toth);
Per ogni Classe problemi con n oggetti, dove n assume i
valori di: 25, 50, 100, 200 ( 4 Dimensioni );
10 Istanze per ogni categoria Classe-Dimensione;
Classe 10 Numero n di oggetti multiplo di tre, dove n
assume i valori di: 24, 51, 99, 201.
Le Istanze per il 2-DBPP
10 Classi ( 1,...,6 Berkey e Wang, 7,...,10 Martello e Vigo);
Per ogni Classe problemi con n oggetti, dove n assume i
valori di: 20, 60, 80, 100 ( 5 Dimensioni );
10 Istanze per ogni categoria Classe-Dimensione.
Alberto Nuzzo:
2-DVPP
TFASE1 = 90 sec, TES = 9, TCFT = 90, TYKI = 600
Classe n
1
6
7
9
10
100
200
50
100
200
50
100
200
50
100
200
51
99
201
Istanze
5
10
3
10
10
4
7
8
6
10
10
7
10
10
110
LB*
125
503
63
405
803
75
276
638
86
257
503
119
330
670
LB
125
503
63
405
803
75
276
638
81
257
503
119
330
670
Fase 1
UB
T
130 90,05
525 90,21
66 76,436
420 90,079
843 90,37
79 67,862
283 90,06
647 90,362
87 55,458
271 90,052
532 90,169
126 72,957
350 90,09
698
90,3
5057
#opt
0
3
2
5
2
3
1
6
5
0
0
10
9
0
46
CFT
UB
130
510
65
410
811
76
282
640
87
267
513
119
331
680
4921
136
T
19,384
78,634
0,096
0,562
17,559
0,495
1,762
22,805
0,7
5,323
37,559
0,188
0,957
90,817
23,76
LB
125
501
65
410
811
76
280
640
87
267
513
119
331
671
YKI
#opt
UB
0
130
1
523
2
65
5
410
2
811
3
76
1
282
6
640
5
87
0
270
0
530
10
119
9
331
2
678
46
4952
105
T
600,42
600,56
10,23
32,19
36,6
96,625
185,24
92,462
5,13
204,02
577,16
30,171
30,3
518,1
233,5
2-DBPP
TFASE1 = 45 sec, TES = 9, TCFT = 135, TYKI = 600
Classe
n
1
2
3
4
5
6
7
8
10
Istanze
40
60
80
100
80
100
40
60
80
100
60
80
100
40
60
80
100
40
100
40
60
80
100
40
60
80
100
60
80
100
1
4
1
1
1
1
2
4
3
4
2
3
1
2
1
6
5
2
2
2
4
8
5
1
3
2
5
5
7
8
96
LB*
12
72
24
31
3
3
14
51
53
81
4
9
3
24
15
141
132
2
6
20
63
175
136
11
49
41
135
49
88
124
LB
11
72
24
31
3
3
14
51
53
81
4
9
3
22
15
141
132
2
6
20
63
175
136
11
49
41
135
49
88
124
Fase 1
UB
T
12
12,672
76
16,498
25
20,359
32
30,039
4
36,031
4
36,008
16
17,629
55
26,414
56
34,54
85
36,054
6
36,039
12
36,05
4
36,051
24
13,648
16
22,551
147
32,502
138
36,094
4
36,01
8
36,173
22
13,336
67
18,54
183
27,348
141
35,054
12
12,508
52
17,216
43
29,748
140
35,339
54
36,053
95
36,019
132
36,014
1665
CFT
#opt
0
1
0
1
0
0
0
1
1
2
0
0
0
0
0
0
3
0
0
0
2
0
1
0
1
1
0
2
0
1
17
UB
12
75
25
31
4
4
16
54
55
83
6
12
4
24
16
147
134
4
8
22
65
183
140
12
51
42
140
52
95
131
1647
18
T
23,976
75,607
152,918
285,918
136
135,59
41,936
124,288
105,632
164,737
0,949
18,7
0,539
6,992
57,121
166,257
134,283
0,494
0,449
29,98
93,989
236,693
269,095
6,48
93,616
180,264
278,611
114,078
153,02
133,957
133,575
LB
12
74
24
27
3
3
15
53
54
82
4
11
4
24
16
142
131
4
8
22
64
170
127
12
49
39
126
49
87
122
YKI
#opt
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
UB
12
76
25
32
4
4
16
55
56
85
6
12
4
24
16
147
138
4
8
22
67
183
141
12
52
43
140
54
95
132
1665
0
T
3,104
307,4
602,8
600,6
600
600
607,3
315,25
407,4
457,95
5,7
613,8
1,9
5,1
29,6
312,95
600
0,2
2,2
612,1
600
601,25
600
16,8
600
600
600
484,4
600
528,525
479,63
2-DBPP
TFASE1 = 45 sec, TES = 9, TCFT = 135, TYKI = 600
Classe n
...
Istanze
...
8
10
40
60
80
100
60
80
100
...
LB*
...
1
3
2
5
5
7
8
96
11
49
41
135
49
88
124
LB
...
11
49
41
135
49
88
124
Fase 1
UB
T
...
...
12
52
43
140
54
95
132
1665
12,508
17,216
29,748
35,339
36,053
36,019
36,014
CFT
#opt
UB
...
0
1
1
0
2
0
1
17
...
12
51
42
140
52
95
131
1647
18
T
...
6,48
93,616
180,26
278,61
114,08
153,02
133,96
133,58
LB
...
12
49
39
126
49
87
122
YKI
#opt
UB
...
...
0
0
0
0
0
0
0
0
T
...
12 16,8
52
600
43
600
140
600
54 484,4
95
600
132 528,53
1665 479,63
0
CONCLUSIONI
Nei due problemi presi in esame, cioè il 2-DVPP e
il 2-DBPP, l’algoritmo CFT offre in quasi tutte le
istanze risultati migliori dell’algoritmo YKI.
L’algoritmo YKI fornisce un lower bound
sensibilmente più alto, quindi migliore, in quasi
tutte le istanze considerate.