Soluzione

laboratorio 3
Prof. E. Amaldi
Ottimizzazione
Assegnamento generalizzato: generazione di piani di taglio e branch-and-cut
Riprendiamo il problema di assegnamento generalizzato considerato a esercitazione nell’esercizio 4.4:
X
max
pij xij
i∈I,j∈J
s.t.
X
xij ≤ 1
i∈I
wij xij ≤ bj
j∈J
j∈J
X
i∈I
xij ∈ {0, 1}
i ∈ I, j ∈ J.
Consideriamo la specifica istanza dove

110 16 25 78

 65 69 54 28

 19 93 45 45


 89 31 72 83

 62 17 77 18

P =
 37 115 87 59

 89 102 98 74


 78 96 87 55

 74 27 99 91

88











W =









95
97
1
59


71 

9 


20 

39 


97 

61 


77 

5 

99 99 51
21 66 59


54 53 44 26 60 

3 91 43 42 5 


72 30 56 72 9 

44 1 71 13 27 


20 99 87 52 85 

72 96 97 73 49 


75 82 83 44 59 

68 8 87 74 4 

69 83 98 88 45
Documento preparato da S. Coniglio, L. Taccari, V. Danese
1
laboratorio 3
Ottimizzazione

91
Prof. E. Amaldi



 87 



109
b=




 88 
64
(a) Si formuli il problema in termini di Programmazione Lineare Intera e lo si risolva mediante
AMPL e CPLEX.
(b) Si proponga un insieme di disuguaglianze valide per il problema.
(c) Si formuli il problema di separazione per suddette disuguaglianze.
(d) Si implementi un algoritmo di generazione di piani di taglio per l’insieme di disuguaglianze
proposte.
(e) Si risolva il problema mediante l’algoritmo di branch-and-cut implementato in CPLEX,
valutando la differenza in numero di nodi dell’albero di branch-and-bound generati nei
casi in cui l’introduzione di piano di taglio sia attiva (come da default di CPLEX) o
completamente disabilitata. Si utilizzino i parametri di CPLEX indicati nel file ga.run.
Suggerimento: si osservino le disuguaglianze singolarmente. A quale problema studiato sono
riconducibili? Dato un problema (A) e un suo rilassamento (B), le disuguaglianze valide per (B)
sono valide anche per (A)?
Documento preparato da S. Coniglio, L. Taccari, V. Danese
2
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
Traccia di soluzione
File dati ga.dat:
#ga.dat
param m := 10;
param n := 5;
param p: 1
2
1 110 16
2 65 69
3 19 93
4 89 31
5 62 17
6 37 115
7 89 102
8 78 96
9 74 27
10 88 97
;
3
25
54
45
72
77
87
98
87
99
99
4
78
28
45
83
18
59
74
55
91
99
5 :=
59
71
9
20
39
97
61
77
5
51
param w:
1
2
3
4
5
6
7
8
9
10
;
3
21
44
43
56
71
87
97
83
87
98
4
66
26
42
72
13
52
73
44
74
88
5 :=
59
60
5
9
27
85
49
59
4
45
1
95
54
3
72
44
20
72
75
68
69
2
1
53
91
30
1
99
96
82
8
83
param b :=
1 91
2 87
3 109
4 88
5 64
;
Documento preparato da S. Coniglio, L. Taccari, V. Danese
3
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
Segue il file ga-i.mod contenente il modello parziale della formulazione (DFJ), da completare:
#ga.mod
param
param
set I
set J
m;
n;
:= 1..m;
:= 1..n;
param p{I,J};
param w{I,J};
param b{J};
#Variables
#Objective function
#Constraints
Documento preparato da S. Coniglio, L. Taccari, V. Danese
4
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
Implementazione parziale dell’algoritmo di piani di taglio, file cuttingplanes-i.run:
#cuttingplanes-i.run
#load .mod and .dat files
option solver cplex;
problem primal:
#list vars, objective function, constraints names
problem separation:
#list vars, objective function, constraints names
let nc := 0;
param violation, default 1e300;
param found, binary, default 0;
repeat {
solve primal;
for {jj in J} {
let j_bar := jj;
let {i in I} x_star[i] := x[i,j_bar];
let found := 0;
solve separation;
let violation := violationObj;
if (violation <= 0.1) then {
continue;
}
else {
#add the cut to the constraints of the primal problem
let found := 1;
break;
}
}
} while (found == 1);
File con parametrizzazione CPLEX per l’esecuzione dell’algoritmo di branch-and-cut, file
Documento preparato da S. Coniglio, L. Taccari, V. Danese
5
laboratorio 3
Prof. E. Amaldi
Ottimizzazione
ga.run:
#ga.run
model ga.mod
data ga.dat
option solver cplex;
option cplex_options "presolve 0
\
zerohalfcuts=-1
mipcuts=-1
covercuts=-1
mipdisplay=5";
\
\
\
solve;
display x;
Per abilitare la generazione della famiglia di disuguaglianze proposta si cambi la riga covercuts=-1
in covercuts=0.
Documento preparato da S. Coniglio, L. Taccari, V. Danese
6
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
Soluzione
(a) File di modello ga.mod:
#ga.mod
param
param
set I
set J
m;
n;
:= 1..m;
:= 1..n;
param p{I,J};
param w{I,J};
param b{J};
var x{I,J}, binary;
maximize obj:
sum{i in I, j in J} x[i,j] * p[i,j];
s.t. assignment{i in I}:
sum{j in J} x[i,j] <= 1;
s.t. knapsack{j in J}:
sum{i in I} w[i,j]*x[i,j] <= b[j];
File .run:
model Lab3_07052013_AMPL/ga.mod;
data Lab3_07052013_AMPL/ga.dat;
option solver cplex;
solve;
display x;
option relax_integrality 1;
solve;
display x;
Documento preparato da S. Coniglio, L. Taccari, V. Danese
7
laboratorio 3
Prof. E. Amaldi
Ottimizzazione
Soluzione della formulazione di PLI e del suo rilassamento continuo:
CPLEX 11.2.0: optimal integer solution; objective 545
50 MIP simplex iterations
0 branch-and-bound nodes
9 cover cuts
2 clique cuts
1 Gomory cut
3 zero-half cuts
x [*,*]
:
1
2
3
4
5
:=
1
0
1
0
0
0
2
0
0
1
0
0
3
1
0
0
0
0
4
0
0
1
0
0
5
0
1
0
0
0
6
1
0
0
0
0
7
0
0
0
0
1
8
0
1
0
0
0
9
1
0
0
0
0
10
0
0
0
1
0
;
CPLEX 11.2.0: optimal solution; objective 595.724698
32 dual simplex iterations (9 in phase I)
x [*,*]
:
1
2
3
4
5
1
0
1
0
0
0
2
0
1
0
0
0
3
1
0
0
0
0
4
0
0
1
0
0
5
0
1
0
0
0
6
0.883248
0.116752
0
0
0
7
0.897959
0
0
0
0.102041
8
0
0
0
0
1
9
0
0
0.609195
0.390805
0
10
0.0823476
0.246284
0
0.671369
0
;
:=
(b) Il problema pu`o essere visto come una generalizzazione del problema dello zaino binario,
in cui si hanno |J| zaini con capacita bj . Considerando singolarmente le disuguaglianze del
problema, possiamo quindi utilizzare delle diseguaglianze valide per il problema di zaino,
ovvero le diseguaglianze di copertura (cover inequalities). Data la diseguaglianza relativa
aj∈J
X
wij xij ≤ bj ,
i∈I
definiamo un insieme di copertura C, o cover, come un sottoinsieme C ⊆ I tale che:
X
wij > bj .
i∈C
Intuitivamente, un insieme di copertura C contiene gli indici di item i che, se assegnati
contemporaneamente a j, eccedono la capacit`a bj . E’ evidente quindi che, in una soluzione
ammissibile, le variabili binarie associate agli indici in un insieme di copertura C non
possono assumere tutte valore 1. In altre parole, data una cover C, risulta valida la
Documento preparato da S. Coniglio, L. Taccari, V. Danese
8
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
corrispondente diseguaglianza di copertura
X
xij ≤ |C| − 1,
i∈C
che pu`o anche essere equivalentemente espressa come
X
(1 − xij ) ≥ 1,
i∈C
indicando che almeno una delle variabili deve essere posta a 0.
Le diseguaglianze di copertura sono valide per il problema di assegnamento, ma non per il
suo rilassamento continuo. Attraverso la generazione di diseguaglianze di copertura possiamo quindi migliorare la formulazione del rilassamento continuo del problema, rendendola
pi`
u stringente.
(c) Per la generazione di diseguaglianze di copertura, si consideri una soluzione ottima x∗
del rilassamento continuo. Si risolve quindi il problema di separazione che permette di
trovare un insieme C ⊆ I per cui la diseguaglianza di copertura non `e soddisfatta da x∗
e si aggiunge tale diseguaglianza al modello. Tale problema comporta la massimizzazione
della violazione di una diseguaglianza di copertura
X
(1 − xij ) ≥ 1,
i∈C
utilizzando delle variabili binarie αij che indicano quali indici i appartengano alla cover C
per una diseguaglianza j. In particolare, la diseguaglianza `e violata se
X
1−
x∗ij αij > 0.
i∈I
Affinch´e l’insieme definito dagli α sia effettivamente un insieme di copertura relativo alla
j-esima diseguaglianza, occorre che
X
wij αij > bj .
i∈I
Poich`e in AMPL i vincoli vengono formulati
P con dei vincoli di tipo ≥ (e non >), scegliamo
di esprimere la condizione con il vincolo i∈I wij αij ≥ bj + ǫ, dove ǫ > 0. Possiamo fissare
ǫ = 1 per
ogni j ∈ J perch`e dal file ga.dat osserviamo che il minimo comune multiplo dei
numeri {wij}i∈I , bj `e maggiore o uguale ad 1 per ogni j ∈ J (in altre parole i numeri
J): ci`
o, insieme al fatto che le variabili αij sono
{wij }i∈I , bj sono interi per ogni j ∈P
intere, assicura che anche la differenza i∈I wij αij − bj `e un multiplo intero di 1.
Il procedimento `e iterato finch´e non esistono pi`
u diseguaglianze di copertura violate.
Documento preparato da S. Coniglio, L. Taccari, V. Danese
9
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
(d) File di modello del rilassamento continuo predisposto per l’inserimento di nuove disuguaglianze:
#primal.mod
param
param
set I
set J
m;
n;
:= 1..m;
:= 1..n;
param p{I,J};
param w{I,J};
param b{J};
param nc >= 0;
set CUTS := 1..nc;
set C{CUTS} within I;
param J_bar{CUTS} symbolic within J;
var x{I,J}, >= 0, <=1;
maximize obj:
sum{i in I, j in J} x[i,j] * p[i,j];
s.t. assignment{i in I}:
sum{j in J} x[i,j] <= 1;
s.t. knapsack{j in J}:
sum{i in I} w[i,j]*x[i,j] <= b[j];
s.t. cover_cuts{k in CUTS}:
sum{i in C[k]} x[i,J_bar[k]] <= card(C[k]) - 1;
File di modello del problema di separazione, separation.mod:
#separation.mod
param j_bar symbolic within J;
param x_star{I}, >=0, <= 1;
var alpha{I}, binary;
maximize violationObj:
1 - sum{i in I} ( 1 - x_star[i] ) * alpha[i];
s.t. cover:
sum{i in I} w[i,j_bar]*alpha[i] >= b[j_bar] + 1;
Documento preparato da S. Coniglio, L. Taccari, V. Danese
10
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
Implementazione completa dell’algoritmo di piani di taglio, file cuttingplanes.run:
#cuttingplanes.run
model primal.mod;
model separation.mod;
data ga.dat;
option solver cplex;
problem primal:
x, obj, assignment, knapsack, cover_cuts;
problem separation:
alpha, violationObj, cover;
let nc := 0;
param violation, default 1e300;
param found, binary, default 0;
repeat {
solve primal;
display x;
for {jj in J} {
let j_bar := jj;
display nc, j_bar;
let {i in I} x_star[i] := x[i,j_bar];
let found := 0;
solve separation;
expand;
display x_star, alpha;
let violation := violationObj;
if (violation <= 0.1) then {
continue;
}
else {
let nc := nc + 1;
let C[nc] := setof{i in I: alpha[i] = 1} i;
let J_bar[nc] := j_bar;
let found := 1;
display C[nc], j_bar;
break;
}
}
} while (found == 1);
solve primal;
display x;
display C, J_bar;
Documento preparato da S. Coniglio, L. Taccari, V. Danese
11
laboratorio 3
Prof. E. Amaldi
Ottimizzazione
Soluzione ottenuta con l’algoritmo dei piani di taglio:
CPLEX 11.2.0: optimal solution; objective 587.5580157
0 simplex iterations (0 in phase I)
x [*,*]
:
1
2
3
4
5
1
0
1
0
0
0
2
0
0.72687
0.141733
0
0.131397
3
1
0
0
0
0
4
0.104167
0
0.788382
0.107451
0
5
0
1
0
0
0
6
0.5
0
0.211618
0.288382
0
7
0.5
0
0.211618
0
0.288382
8
0
0.27313
0.0152521
0
0.711618
9
0
0.176178
0.211618
0.612204
0
10
0.5
0.27313
0
0.22687
0
;
:=
nc = 15
set
set
set
set
set
set
set
set
set
set
set
set
set
set
set
C[1] := 3 6 7;
C[2] := 3 6 10;
C[3] := 3 7 10;
C[4] := 1 6;
C[5] := 6;
C[6] := 1 2 10;
C[7] := 3 5 7;
C[8] := 1 2 8;
C[9] := 2 8;
C[10] := 2 10;
C[11] := 4 7;
C[12] := 4 9;
C[13] := 4 6;
C[14] := 7 8;
C[15] := 6;
J_bar [*] :=
1 1
2 1
3 1
4 2
5 2
6 2
7 1
8 2
9 2
10 2
11 3
12 3
13 3
14 5
15 5
;
Dalla soluzione riportata nel punto a) possiamo osservare che il rilassamento continuo
forniva un limite superiore sul valore ottimo pari a 595.7, mentre la formulazione con l’aggiunta di disuguaglianze di copertura ne fornisce uno di 587.6, avvicinandosi al valore del
problema di PLI originale: ci`
o conferma che questi tagli restringono la regione ammissibile
individuata dal rilassamento continuo.
Documento preparato da S. Coniglio, L. Taccari, V. Danese
12
laboratorio 3
Ottimizzazione
Prof. E. Amaldi
(e) La generazione di piani di taglio pu`o essere tipicamente usata all’interno di un branch-andbound, ottenendo un metodo cosiddetto di branch-and-cut. Attivando l’opzione di CPLEX
che permette la generazione di diseguaglianze di copertura (cover cuts) `e possibile notare
la differenza di comportamento.
Soluzione ottenuta disabilitando le disuguaglianze di copertura:
CPLEX 11.2.0: optimal integer solution; objective 545
668 MIP simplex iterations
329 branch-and-bound nodes
x [*,*]
:
1
2
3
4
5
:=
1
0
1
0
0
0
2
0
0
1
0
0
3
1
0
0
0
0
4
0
0
1
0
0
5
0
1
0
0
0
6
1
0
0
0
0
7
0
0
0
0
1
8
0
1
0
0
0
9
1
0
0
0
0
10
0
0
0
1
0
;
Soluzione ottenuta abilitando la separazione di disuguaglianze di copertura:
CPLEX 11.2.0: optimal integer solution; objective 545
90 MIP simplex iterations
0 branch-and-bound nodes
14 cover cuts
x [*,*]
:
1
2
3
4
5
:=
1
0
1
0
0
0
2
0
0
1
0
0
3
1
0
0
0
0
4
0
0
1
0
0
5
0
1
0
0
0
6
1
0
0
0
0
7
0
0
0
0
1
8
0
1
0
0
0
9
1
0
0
0
0
10
0
0
0
1
0
;
Osserviamo che attivando la generazione di disuguaglianze di copertura il numero di nodi
dell’albero di enumerazione si riduce grandemente. Ci`
o conferma che l’aggiunta di tali
disuguaglianze contribuisce a rendere pi`
u stringenti le formulazioni dei vari sottoproblemi,
migliorandone i rispettivi bound e rendendo il processo di branch-and-bound pi`
u efficiente.
Documento preparato da S. Coniglio, L. Taccari, V. Danese
13

Download Report