Slides Problemi di Selezione Sottoinsiemi

Modelli
Branch and Bound
Problemi di selezione di sottoinsiemi
Laura Galli
Dipartimento di Informatica
Largo B. Pontecorvo 3, 56127 Pisa
[email protected]
http://www.di.unipi.it/~galli
1 Dicembre 2014
Ricerca Operativa 2
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
A.A. 2014/15
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
1 / 19
Modelli
Branch and Bound
Problemi di selezione di sottoinsiemi
Insieme I = {1, . . . , m}.
Famiglia S1 , . . . , Sn di sottoinsiemi di I , ognuno ha costo (valore) cj .
Problema di copertura: determinare una sottofamiglia F di costo minimo tale
che ogni elemento di I appartenga ad almeno un sottoinsieme di F.
Problema di partizione: determinare una sottofamiglia F di costo minimo tale
che ogni elemento di I appartenga esattamente ad un sottoinsieme di F.
Problema di riempimento: determinare una sottofamiglia F di valore massimo
tale che ogni elemento di I appartenga ad al pi`
u un sottoinsieme di F.
I = {1, 2, 3, 4, 5, 6},
S1 = {1, 3}, S2 = {2, 4}, S3 = {2, 5, 6}, S4 = {5, 6}, S5 = {3, 4}.
copertura: F = {S1 , S2 , S3 } partizione: F = {S1 , S2 , S4 }
riempimento: F = {S3 , S5 }
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
2 / 19
Modelli
Branch and Bound
Modelli
(
1
Definiamo la matrice: aij =
0
se i ∈ Sj ,
altrimenti.
Ad ogni sottofamiglia F associamo una variabile x, dove xj =
(
1
0
se Sj ∈ F,
altrimenti.
Copertura
Partizione
Riempimento

n
P


cj xj
min



j=1
n
P
aij xj ≥ 1 ∀ i


 j=1


xj ∈ {0, 1} ∀ j

n
P


cj xj
min



j=1
n
P
aij xj = 1 ∀ i


 j=1


xj ∈ {0, 1} ∀ j

n
P


cj xj
max



j=1
n
P
aij xj ≤ 1 ∀ i


 j=1


xj ∈ {0, 1} ∀ j
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
3 / 19
Modelli
Branch and Bound
Riduzione di un problema di copertura
Si possono eliminare variabili e vincoli applicando le seguenti regole:
1. Se cj ≤ 0 allora pongo xj = 1 ed elimino tutti i vincoli in cui compare xj
(perch´e esiste una sol. ottima con xj = 1).
(
1 se j = p,
2. Se esiste un vincolo r tale che arj =
allora pongo xp = 1 ed
0 altrimenti,
elimino tutti i vincoli in cui compare xp (perch´e ogni sol. ammissibile ha
xp = 1).
3. Se esistono 2 vincoli r , s tali che arj ≤ asj per ogni j, allora elimino il vincolo
s (perch´e il vincolo r implica il vincolo s).
4. Se esiste un sottoinsieme Sp e una famiglia F tali che
P
aip ≤
aij
per ogni i ∈ I
j∈F
P
cj
cp ≥
j∈F
allora pongo xp = 0 (perch´e gli elementi di Sp sono coperti anche dalla
famiglia F ed il costo di Sp non `e inferiore a quello di F ).
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
4 / 19
Modelli
Branch and Bound
Riduzione di un problema di copertura: esempio
Consideriamo il problema di copertura:
cj
i\
A=
j
1
2
3
4
5
6
7
8
9
10
1
1
0
1
0
1
1
1
1
0
6
2
1
0
1
0
0
1
0
0
1
4
3
0
1
1
0
0
0
0
0
0
2
4
0
0
0
0
1
0
1
0
0
8
5
0
1
0
1
0
0
0
0
1
5
6
1
0
0
0
0
1
1
1
0
3
7
1
0
0
0
1
1
0
1
1
7
8
0
1
1
0
0
1
0
1
0
Dalla 4◦ riga si ottiene x5 = 1 e si eliminano le righe 2, 4 e 9.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
5 / 19
Modelli
Branch and Bound
Riduzione di un problema di copertura: esempio (segue)
Il problema ridotto diventa:
cj
j
i\
1
3
A=
5
6
7
8
10
1
1
1
1
1
1
1
6
2
1
1
0
1
0
0
4
3
0
1
0
0
0
0
2
4
0
0
1
0
1
0
5
6
1
0
0
1
1
1
3
7
1
0
1
1
0
1
7
8
0
1
0
1
0
1
Poich´e a1j ≤ a6j per ogni j, si pu`
o eliminare la riga 6.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
6 / 19
Modelli
Branch and Bound
Riduzione di un problema di copertura: esempio (segue)
10
1
1
1
1
1
1
cj
i\
A=
j
1
3
5
7
8
6
2
1
1
0
0
0
4
3
0
1
0
0
0
2
4
0
0
1
1
0
5
6
1
0
0
1
1
3
7
1
0
1
0
1
7
8
0
1
0
0
1
La 1◦ colonna `e dominata dalle colonne 3, 4 e 7, quindi si pone x1 = 0.
cj
i\
A=
L. Galli
j
1
3
5
7
8
6
2
1
1
0
0
0
Corso di Ricerca Operativa 2
4
3
0
1
0
0
0
-
2
4
0
0
1
1
0
5
6
1
0
0
1
1
3
7
1
0
1
0
1
7
8
0
1
0
0
1
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
7 / 19
Modelli
Branch and Bound
Metodo Branch and Bound per problemi di copertura
D’ora in poi consideriamo un problema di copertura:

n
P


cj xj
min



j=1
n
P
aij xj ≥ 1 ∀ i


 j=1


xj ∈ {0, 1} ∀ j
Per applicare il metodo Branch and Bound `e necessario:
• calcolare le vI (Pi )
• calcolare una vS (P)
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
8 / 19
Modelli
Branch and Bound
Rilassamenti
vI (P): possiamo usare il rilassamento continuo o il rilassamento lagrangiano.
Il rilassamento lagrangiano `e facile da risolvere:
!

n
m
n
P
P

P


aij xj =
λi 1 −
cj xj +
min



j=1
i =1
j=1
m
m
n
P
P
P

λi
x
+
λ
a
c
−

j
i
ij
j


i =1
i =1
j=1


xj ∈ {0, 1} ∀ j
(RLλ )
La soluzione ottima `e

m
1 se c − P λ a ≤ 0,
i ij
j
x¯j =
i =1

0 altrimenti.
Teorema
Il valore ottimo del duale lagrangiano `e uguale al valore ottimo del rilassamento
continuo del problema di copertura.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
9 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di Chv´
atal
vS (P): un algoritmo greedy.
Algoritmo di Chv´
atal
1. I = {1, . . . , m}, J = {1, . . . , n}, x := 0.
2. Per ogni j ∈ J calcola i costi unitari di copertura
cj
uj = P
aij
i ∈I
3. Trova un indice k ∈ J tale che uk = min uj
j∈J
Poni xk := 1, da J elimina k, da I elimina {i : aik = 1}
4. Se I = ∅ allora STOP (x `e una copertura)
5. Se J = ∅ allora STOP (non esistono coperture)
altrimenti torna al passo 2.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
10 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di Chv´
atal
Esempio
I = {1, . . . , 9}, J = {1, . . . , 8}.
cj
i\
j
Costi unitari:
L. Galli
uj
j
A
1
2
3
4
5
6
7
8
9
1
10
6
2
6
5
10
1
1
0
1
0
1
1
1
1
0
6
2
1
0
1
1
0
1
0
0
1
3
4
2
1
Corso di Ricerca Operativa 2
4
3
0
1
1
0
0
0
0
0
0
5
8
3
-
2
4
0
0
0
0
1
0
1
0
0
8
5
0
1
0
1
0
0
0
0
1
6
5
4
7
3
5
5
6
1
0
0
0
0
1
1
1
0
8
7
4
3
7
1
0
0
0
1
1
0
1
1
7
8
0
1
1
0
0
1
0
1
0
u7 = min uj → x7 = 1
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
11 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di Chv´
atal
Esempio (segue)
Elimino la colonna 7 e le righe 1,5,6,8,9:
10
1
0
1
0
1
cj
j
i\
2
3
4
7
Costi unitari:
j
uj
1
5
2
3
3
2
4
2
6
2
0
1
1
0
4
3
1
1
0
0
5
4
6
5
2
4
0
0
0
1
8
5
1
0
1
0
5
6
0
0
0
1
7
8
1
1
0
0
8
u = min uj → x3 = 1.
7/2 3
In seguito si trova x4 = 1 e x2 = 1.
L’algoritmo di Chv´atal trova la copertura (0, 1, 1, 1, 0, 0, 1, 0) di costo 15.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
12 / 19
Modelli
Branch and Bound
Metodi euristici: arrotondamento
Un altro metodo euristico `e risolvere il rilassamento continuo e arrotondare per eccesso
(cio`e ad 1) le componenti frazionarie.
Esempio
A
cj
10
6
4
2
8
5
3
7
j
i\
1
2
3
4
5
6
7
8
9
1
1
0
1
0
1
1
1
1
0
2
1
0
1
1
0
1
0
0
1
3
0
1
1
0
0
0
0
0
0
4
0
0
0
0
1
0
1
0
0
5
0
1
0
1
0
0
0
0
1
6
1
0
0
0
0
1
1
1
0
7
1
0
0
0
1
1
0
1
1
8
0
1
1
0
0
1
0
1
0
L’ottimo del rilassamento continuo (trovato con AMPL) `e
1 1 1 1 1 1 1
0, , , , , , , , 0 ,
2 2 2 2 2 2 2
quindi (0, 1, 1, 1, 1, 1, 1, 0) `e una copertura di costo 28.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
13 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di aggiustamento dei moltiplicatori
Metodo euristico lagrangiano: ad ogni iterazione risolviamo il RLλ e cambiamo i
valori di λ fino a trovare una soluzione ammissibile.
Fissiamo λ. Il rilassamento lagrangiano `e

n
m
m
P
P
 min P
λi
λi aij xj +
cj −
j=1
i =1
i =1

xj ∈ {0, 1}
Chiamiamo costo ridotto c¯j (λ) = cj −
m
P
(RLλ )
λi aij . Quindi l’ottimo di RLλ `e
i =1
L. Galli
x¯j (λ) =
(
Corso di Ricerca Operativa 2
-
1
0
se c¯j (λ) ≤ 0,
altrimenti.
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
14 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di aggiustamento dei moltiplicatori
Se x¯ non `e una copertura, allora esiste un elemento k che non `e coperto da x¯.
Chiamiamo K = {j : k ∈ Sj } la famiglia dei sottoinsiemi che contengono k.
Allora x¯j = 0 per ogni j ∈ K e quindi c¯j (λ) > 0 per ogni j ∈ K .
Per coprire anche l’elemento k, almeno una delle variabili x¯j con j ∈ K deve
assumere valore 1. Per far questo modifichiamo λ in modo che una di queste
variabili abbia costo ridotto nullo.
Modifichiamo solo la k-esima componente di λ:
(
λi
se i 6= k,
′
λi =
λk + δ se i = k.
I nuovi costi ridotti sono:
′
c¯j (λ ) =
(
c¯j (λ)
c¯j (λ) − δ
se j ∈
/ K,
se j ∈ K .
Se scegliamo δ = min c¯j (λ), nel nuovo rilassamento lagrangiano avremo un costo
j∈K
ridotto nullo per un indice j ∈ K e quindi potremo coprire k.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
15 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di aggiustamento dei moltiplicatori
Algoritmo di aggiustamento dei moltiplicatori
1. Poni λ = 0 e c¯j = cj per ogni j.
2. Calcola l’ottimo del rilassamento lagrangiano:
(
1 se c¯j ≤ 0,
x¯j =
0 altrimenti.
3. Se x¯ `e una copertura allora STOP
Pn
4. Scegli il primo indice k tale che j=1 akj x¯j = 0.
Calcola K = {j : akj = 1} e δ = min c¯j .
j∈K
5. Aggiorna i moltiplicatori e i costi ridotti:
(
(
λi
se i 6= k,
c¯j
λi :=
c¯j :=
λk + δ se i = k.
c¯j − δ
se j ∈
/ K,
se j ∈ K .
e torna al passo 2.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
16 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di aggiustamento dei moltiplicatori
Esempio
Applichiamo l’algoritmo di aggiustamento dei moltiplicatori al problema precedente:
λ
c¯
x¯
k
K
δ
λ
c¯
x¯
k
K
δ
1◦ iterazione
(0, 0, 0, 0, 0, 0, 0, 0, 0)
(10, 6, 4, 2, 8, 5, 3, 7)
(0, 0, 0, 0, 0, 0, 0, 0)
1
{1, 2, 6, 7}
min{10, 6, 5, 3} = 3
3◦ iterazione
(3, 4, 0, 0, 0, 0, 0, 0, 0)
(7, 3, 0, 2, 4, 2, 0, 3)
(0, 0, 1, 0, 0, 0, 1, 0)
4
{2, 5}
min{3, 4} = 3
2◦ iterazione
(3, 0, 0, 0, 0, 0, 0, 0, 0)
(7, 3, 4, 2, 8, 2, 0, 7)
(0, 0, 0, 0, 0, 0, 1, 0)
2
{3, 5, 8}
min{4, 8, 7} = 4
4◦ iterazione
(3, 4, 0, 3, 0, 0, 0, 0, 0)
(7, 0, 0, 2, 1, 2, 0, 3)
(0, 1, 1, 0, 0, 0, 1, 0)
7
{1, 4, 6}
min{7, 2, 2} = 2
5◦ iterazione
(3, 4, 0, 3, 0, 0, 2, 0, 0)
(5, 0, 0, 0, 1, 0, 0, 3)
(0, 1, 1, 1, 0, 1, 1, 0)
L’algoritmo trova la copertura (0, 1, 1, 1, 0, 1, 1, 0) di costo 20.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
17 / 19
Modelli
Branch and Bound
Metodi euristici: algoritmo di aggiustamento dei moltiplicatori
Osservazione
L’algoritmo di aggiustamento dei moltiplicatori, essendo basto sulla risoluzione di
rilassamenti lagrangiani, fornisce sia una vS (P) (costo della copertura trovata), sia
una vI (P). Infatti se l’algoritmo termina con la copertura x¯ e i moltiplicatori λ
allora
n
m
X
X
vI (P) =
c¯j x¯j +
λi .
j=1
i =1
Nell’esempio precedente si ha vI (P) = 0 + 12 = 12.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
18 / 19
Modelli
Branch and Bound
Esempio di applicazione del metodo Branch and Bound
Risolviamo il problema precedente con il metodo Branch and Bound.
Conosciamo la copertura
costo 15 = vS (P) e l’ottimo del
(0, 1, 1, 1, 0, 0, 1, 0) di 1 1 1 1 1 1 1
rilassamento continuo 0, , , , , , , , 0 di costo 14 = vI (P).
2 2 2 2 2 2 2
Istanziamo la prima variabile frazionaria, cio`e x2 :
14,15
P
x2 = 1
x2 = 0
17,15
15,15
P1
P2
L’ottimo del rilassamento continuo di P1 `e (0, 0, 1, 1, 1, 0, 1, 0) di costo
17 = vI (P1 ) > vS (P) = 15, pertanto chiudiamo il nodo P1 .
L’ottimo del rilassamento continuo di P2 `e (0, 1, 1, 12 , 0, 12 , 21 , 0) di costo
15 = vI (P2 ) = vS (P), quindi chiudiamo anche il nodo P2 .
La copertura ottima `e (0, 1, 1, 1, 0, 0, 1, 0) di costo 15.
L. Galli
Corso di Ricerca Operativa 2
-
Laurea Magistrale in Ingegneria Gestionale
Universit`
a di Pisa
19 / 19

Download Report