Disequazioni cover e lifting
Rafforzamento di formulazioni
Il problema di knapsack max 5x
1+ 2x
23x
1+ 4x
2< 6
x ∈ {0,1}
2ha come rilassamento lineare max 5x
1+ 2x
23x
1+ 4x
2< 6 x
1> 0
x
2> 0 x
1< 1 x
2< 1
Indichiamo con x*LP la soluzione ottima del rilassamento.
Separazione
Domanda
Possiamo individuare una disequazione valida per conv ( F ) che “separa” x
*LPda conv ( F ) ?
x2
x*LP
x1
Minimal cover
Consideriamo l’insieme
X = { Σ
j=1, …, na
jx
j< b, x ∈ {0,1}
n} Definizione
Un insieme C ⊆ N è un cover se e solo se
Σ
j ∈Ca
j> b.
Un cover è minimale se, comunque preso j ∈ C, l’insieme C \ { j } NON è un cover
Osservazione
Un cover ha associato un vettore caratteristico non
ammissibile per X
Disequazioni cover
Teorema
Se C ⊆ N è un cover, la disequazione
Σ
j ∈C xj < |C| - 1 (*) è valida per conv (X ).Dimostrazione
Dimostriamo che se xR ∈ {0,1}n non soddisfa il vincolo (*) allora xR
∉ X.
Se xR è tale che
Σ
j ∈c xj > |C| - 1, allora |R ∩ C|= |C|, quindi C ⊆ R.Pertanto:
Σ
j ∈Na
jx
jR= Σ
j ∈Ra
j> Σ
j ∈Ca
j> b
ovvero xR ∉ X. ■
Esempio
Consideriamo il problema di knapsack
max 15 x
1+ 9 x
2+ 8 x
3+ 6 x
4+ 5 x
5+ 4 x
6+ x
711 x
1+ 6 x
2+ 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6+ x
7< 19 x ∈ [0,1]
7x
*LP= (1, 1, 1/3, 0, 0, 0, 0)
Una disequazione cover violata da x
*LPè la disequazione x
1+ x
2+ x
3< 2
Come si individua una disequazione di tipo cover violata
da x
*LP?
Problema di separazione
Domanda
Dato un poliedro P, formulazione di un problema di PL-{0,1}, esiste una disequazione di tipo cover che separa x
*LPda conv ( X )?
Risposta
a) SI la disequazione esiste e fornisce anche il cover associato C
b) NO non esiste
Un algoritmo A che risponde (correttamente) alla
domanda con una delle due risposte possibili a) o b), si
chiama ORACOLO DI SEPARAZIONE
Oracolo di separazione
Riscriviamo la disequazione come
La disequazione è violata da x*
LPse e solo se:
Quindi, posso massimizzare la violazione definendo
Un algoritmo per SEP è un oracolo di separazione
⎭⎬
⎫
⎩⎨
⎧ −
=
∑
∈
knapsack di
vincolo del
cover un
è ,
) 1 (
max xLP* C
SEP
C j
j
∑
∈>
− +
C j
x
j1 ) 0 (
1
LP*∑
∈−
≤
C j
j
C
x 1 ∑
∈
≤
− +
C j
j
C
x | | 0
1
Difatti…
Sia z
*SEPil valore della soluzione ottima y
*SEPdi
Se 1 + z
*SEP> 0 allora esiste una disequazione cover violata associata a y
*SEPSe 1 + z
*SEP< 0 allora NON esiste una disequazione cover violata
⎭⎬
⎫
⎩⎨
⎧ −
=
∑
∈
knapsack di
vincolo del
cover un
è ),
1 (
max xLP* C
SEP
C j
j
Formulazione del problema di separazione
Variabili decisionali
y
j= 1 se l’indice j è nel cover y
j= 0 altrimenti
Funzione obiettivo
Vincoli
j n
j
j
y
x 1 ) (
max
1
*
LP
−
∑
=n j n
j
j
y
b y
a
} 1 , 0 {
1
1
∈
+
∑ ≥
=
Osservazione
I coefficienti in funzione obiettivo sono < 0, quindi il problema non ammette una soluzione banale
Proprietà del cover
Trasformazione …
Ponendo w
j= 1 – y
jil problema di separazione diventa
ovvero …
n
n j
j j
n j
j
j n
j
j n
j
j
w
b a
w a
w x
x
} 1 , 0 {
1 st
) 1 (
) 1 (
max
1 1
1
* LP 1
* LP
∈
+ +
−
≥
−
−
−
−
∑
∑
∑
∑
=
=
=
=
…un problema di knapsack
n n j
j j
n j
j
j n
j
j
w
b a
w a
w x
} 1 , 0 {
1 st
) 1
( max
1 1
1
* LP
∈
−
−
≤
−
∑
∑
∑
=
=
=
Esempio
max 15 x
1+ 9 x
2+ 8 x
3+ 6 x
4+ 5 x
5+ 4 x
6+ x
711 x
1+ 6 x
2+ 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6+ x
7< 19 x ∈ {0,1}
7x
*LP= (1, 1, 1/3, 0, 0, 0, 0) Problema di separazione
max (1 – 1) w
1+ (1 – 1) w
2+ (1 - 1/3) w
3+ w
4+ w
5+ w
6+ w
711 w
1+ 6 w
2+ 6 w
3+ 5 w
4+ 5 w
5+ 4 w
6+ w
7<
38 – 19 – 1 = 18
w ∈ {0,1}
7Separazione
Problema di separazione
max 2/3 w
3+ w
4+ w
5+ w
6+ w
711 w
1+ 6 w
2+ 6 w
3+ 5 w
4+ 5 w
5+ 4 w
6+ w
7<
18
w ∈ {0,1}
7Soluzione ottima
w* = (0, 0, 0, 1, 1, 1, 1) di valore 4 Riportiamola nello spazio delle y:
y* = (1, 1, 1, 0, 0, 0, 0) di valore -2/3, ovvero < 1
Pertanto…
1. Il valore di 1 + z
*SEPè > 0, ovvero esiste una disequazione cover violata
2. La disequazione è scritta in corrispondenza agli indici che hanno valore 1 in y
*, ovvero
y* = (1, 1, 1, 0, 0, 0, 0) corrisponde a x
1+ x
2+ x
3< 2
Ricapitolando
Algoritmo del piano di taglio (CUT)
Dato il rilassamento lineare di un problema di knapsack 1. Calcola la soluzione ottima x
*LP2. Se x
*LP∈{0, 1}
nSTOP altrimenti vai a 3.
3. Definisce il problema di separazione 4. Risolve il problema di separazione
5. Se esiste una disequazione cover violata si aggiunge alla formulazione corrente e torna al punto 1,
altrimenti STOP
Rafforzamento di disequazioni cover
Teorema
Se C ⊆ N è un cover, la disequazione
Σ
j ∈E(C) xj < |C| - 1 (*)è valida per conv (X ) con E(C)=C ∪ {j:aj ≥ ai per ogni i ∈C}
Esempio
11 x
1+ 6 x
2+ 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6+ x
7< 19
La disequazione cover
x
3+ x
4+ x
5+ x
6< 3
diventa
x
1+ x
2+ x
3+ x
4+ x
5+ x
6< 3
Rafforzamento di disequazioni cover Esempio
11 x
1+ 6 x
2+ 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6+ x
7< 19 La disequazione cover
x
3+ x
4+ x
5+ x
6< 3
è valida.
La disequazione
α
1x
1+ x
3+ x
4+ x
5+ x
6< 3
ammette dei valori di α
1diversi da 0 per cui continua a
rimanere valida?
Rafforzamento di disequazioni cover
Se x
1=x
2=x
7=0 è valida per ogni valore di α
1Invece, se x
1=1 e x
2=x
7=0 α
1+ x
3+ x
4+ x
5+ x
6< 3
è valida se e solo se soddisfa tutti i punti x ∈B
4tali che 11·1+ 6 · 0 + 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6+ 1·0 < 19
Ovvero se α
1< 3 –
max {x
3+ x
4+ x
5+ x
6:6 x
3+ 5 x
4+ 5 x
5+ 4 x
6< 8, x
2=x
7=0, x ∈ {0,1}
7} = 3 - 1 = 2
Quindi la risultante disequazione è
2x
1+ x
3+ x
4+ x
5+ x
6< 3
Rafforzamento di disequazioni cover
Ripetendo il calcolo per x
2si ha:
α
2 <3 – max { 2x
1+x
3+ x
4+ x
5+ x
6:
11 x
1+ 6 x
3+ 5 x
4+ 5 x
5+ 4 x
6< 13, x
7=0, x ∈ {0,1}
7} = 1
ottenendo
2x
1+ x
2+ x
3+ x
4+ x
5+ x
6< 3
Questa procedura si chiama lifting sequenziale
Esempio
max 18 x
1+ 10 x
2+ 8 x
3+ 5 x
4+ 2 x
5+ 2 x
6+ 3 x
712 x
1+ 8 x
2+ 7 x
3+ 5 x
4+ 3 x
5+ 9 x
6+ 11 x
7< 18 x ∈ {0,1}
7x*
LP= (1, 0.75, 0, 0, 0, 0, 0)
min 0y
1+ 0.25 y
2+ y
3+ y
4+ y
5+ y
6+ y
712 y
1+ 8 y
2+ 7 y
3+ 5 y
4+ 3 y
5+ 9 y
6+ 11 y
7> 19 y ∈ {0,1}
7x
1+ x
2< 1
Esempio
Lifting sequenziale
Sequenza di lifting: x
3→ x
4→ x
5→ x
6→ x
7α
3< 1-max{x
1+ x
2| knapsack e x
3= 1, x
4,x
5, x
6, x
7= 0 }
quindi
α
3= 1−1=0
α
4< 1-max{x
1+ x
2| knapsack e x
4= 1, x
5, x
6, x
7= 0 }= 1 -1 = 0
α
5< 1-max{x
1+ x
2| knapsack e x
5= 1, x
6, x
7= 0 } = 0 α
6< 1-max{x
1+ x
2| knapsack e x
6= 1, x
7= 0 } = 0
α
7< 1-max{x
1+ x
2| knapsack e x
7= 1} = 1 – 0 = 1
In definitiva: x
1+ x
2+ x
7< 1
Esempio
Come cambia il lifting se la variabile interessata è a 1 e deve essere liftata a 0 ? (x
1= 1 → x
1= 0)
Consideriamo la disequazione cover
x
4+ x
5< 1 valida se x
1= 1, x
2= 0, x
3= 0 , x
6= 0 , x
7= 0 Essa rimane valida se il coefficiente di lifting α
1soddisfa:
α
1(1- x
1)+ x
4+ x
5< 1 ovvero se
α
1< 1 – max {x
4+ x
5|knapsack e x
1,x
2, x
3, x
6, x
7= 0}
ovvero
α
1< 1 – 2 = -1 Quindi
-1 (1 - x
1) + x
4+ x
5< 1 che corrisponde a x
1+ x
4+ x
5< 2
…
Ricapitolando
Algoritmo del piano di taglio (CUT)
Dato il rilassamento lineare di un problema di knapsack 1. Calcola la soluzione ottima x
*LP2. Se x
*LP∈{0, 1}
nSTOP altrimenti vai a 3.
3. Definisce il problema di separazione 4. Risolve il problema di separazione
5. Se esiste una disequazione cover violata
Si rafforza tramite la procedura di lifting quindi
si aggiunge alla formulazione corrente e si torna al punto 1, altrimenti STOP
Osservazioni
L’algoritmo del piano di taglio può arrestarsi senza aver trovato la soluzione ottima intera. Che cosa si fa in questo caso?
Algoritmo di Cut-and-branch Osservazioni
Il problema di separazione e i problemi di lifting sono problemi di knapsack come il problema originario.
Perché non risolvere all’ottimo direttamente il problema originario?
Cosa succede se si risolve euristicamente il problema di
separazione o il problema di lifting?
Cut-and-branch
Caso 3: Ottimalità
Se Pi ≠ ∅ e la soluzione ottima xiUB del RL è intera, allora elimina Si.
Se ziUB> zLB allora zLB =ziUB, vai a Test Individua una componente frazionaria k di xiUBe ramifica Si aggiungendo ad L Scount+1 = Si ∩ {xk= 0}
Scount+2 = Si ∩ {xk= 1}
count = count + 2 Caso 2: Bound
Se Pi ≠ ∅, sia ziUB il valore della soluzione ottima xiUBdel RL.
Se ziUB< zLB elimina Si per bound, vai a Test
Inizializzazione
zLB= - ∞; count = 0;
Calcola P, formulazione di S, applicando CUT
L=P
Test: L = ∅?
Scegli un problema Si dalla lista
Risolvi il Rilassamento Lineare su Pi
Caso 1: Inammissibilità Se Pi = ∅ elimina Si per inammissibilità, vai a Test
Dal cut-and-branch al branch-and-cut
Consideriamo il seguente esempio:
max 39 x
1+ 28 x
2+ 46 x
3+ 7 x
4+ 9 x
5+ 6 x
6+ 4 x
726 x
1+ 14 x
2+ 30 x
3+ 8 x
4+ 8 x
5+ 12 x
6+ 11 x
7< 50 x ∈ {0,1}
7x*
LP= (0.23, 1, 1, 0, 0, 0, 0)
Una soluzione ammissibile è z*
LB= (1, 1, 0, 0, 1) di valore
76
Esempio
0
1 2
z*
LP=83
z*
1LP=80.75 z*
2LP=82.33 x
1=0 x
1=1
39 + max 28 x
2+ 46 x
3+ 7 x
4+ 9 x
5+ 6 x
6+ 4 x
714 x
2+ 30 x
3+ 8 x
4+ 8 x
5+ 12 x
6+ 11 x
7< 24
x ∈ [0,1]
7x*
2LP= (1, 1, 0.33, 0, 0, 0, 0)
Disequazione cover violata
x
3< 0
Liftiamola nella sequenza
x
1→ x
2→ x
4→ x
5→ x
6→ x
7Esempio
Lifting
x3 < 0 (x1 = 1 → x1 = 0) α1 (1- x1)+ x3 < 0
α1 < 0 – max {x3 |knapsack e x1,x2, x4,x5 ,x6 ,x7 = 0}
α1 =-1 → x1+ x3 < 1
α2 < 1- max {x1 + x3 |knapsack e x2=1, x4,x5 ,x6 ,x7 = 0}=0 α4 < 1- max {x1 + x3 |knapsack e x4=1, x5 ,x6 ,x7 = 0}=0 α5 < 1- max {x1 + x3 |knapsack e x5=1, x6 ,x7 = 0}=0 α6 < 1- max {x1 + x3 |knapsack e x6=1, x7 = 0}=0 α7 < 1- max {x1 + x3 |knapsack e x7=1}=0
Quindi si ottiene x1+ x3 < 0. Questa disequazione è globalmente valida (grazie alla procedura di lifting) e può essere aggiunta direttamente alla formulazione iniziale.
Esempio
0
1 2
z*
LP=83
z*
LP=80.75 z*
LP=77.75
x
1=0 x
1=1
39 + max 28 x
2+ 46 x
3+ 7 x
4+ 9 x
5+ 6 x
6+ 4 x
714 x
2+ 30 x
3+ 8 x
4+ 8 x
5+ 12 x
6+ 11 x
7< 24
x
1+ x
3< 0 x ∈ [0,1]
7Al nodo 2 si ottiene: x*
2LP= (1, 1, 0, 0.25, 1, 0, 0)
Esempio
0
1 2
z*
LP=83
z*
LP=80.75 z*
LP=77.75
x
1=0 x
1=1
3 4
x
4=1 x
4=0
z*
LP=77.75 →76.27 z*
LP=76.25
x*
3LP= (1, 1, 0, 0, 1, 0.167, 0)
Cover violata: x
2+ x
5+ x
6< 2 Sequenza di lifting:
x
1→ x
3→ x
4→ x
7α
1=-1, α
3=1, α
4=1, α
7=1 → x
1+ x
2+ x
3+ x
5+ x
6< 3
Il nodo 3 e il nodo 4 si eliminano per bound …. continua…
Rilassamento Lagrangiano
Rilassamento Lagrangiano
Consideriamo il problema di PLI
e introduciamo un vettore λ = (λ1, …, λm) tale che λ ≥ 0.
Il problema P(λ) (rilassamento lagrangiano di P )
è un rilassamento per P
Difatti: 1. la regione ammissibile di P ⊆ P(λ)
2. ogni soluzione ammissibile di P è ammissibile per P(λ) e il suo valore in P(λ) è maggiore o uguale del valore in P per costruzione (λ ≥ 0)
X x
P b
Ax
cx z
∈
≤
=
) ( max
punti) di
finito (insieme
) (
max )
(
X x
Ax b
cx z
∈
− +
= λ
λ
Duale lagrangiano
Trovare il miglior rilassamento possibile (rispetto λ) significa risolvere il problema
Teorema. Sia λ ≥ 0 e sia x(λ) una soluzione ottima per P(λ). Se Ax(λ) ≤ b e λ (b – Ax(λ)) = 0, allora x(λ) è ottima per P
Dimostrazione
w ≤ z(λ) = cx(λ) + λ (b - A x(λ)). Essendo λ (b – Ax(λ)) = 0 si ha che cx(λ) + λ (b - A x(λ)) = cx(λ).
Poiché Ax(λ) ≤ b, x(λ) è ammissibile per P, si ha cx(λ) ≤ z.
In definitiva: w ≤ z(λ) = cx(λ) + λ(b - A x(λ)) = cx(λ) ≤ z.
Essendo w ≥ z, si ha w=z.
{ ( ) : 0 }
min ≥
= z λ λ
w
Qualità del rilassamento
Riscriviamo w come
ovvero
{ }
{ } { }
⎪⎭
⎪ ⎬
⎫
⎪⎩
⎪ ⎨
⎧ + −
=
− +
=
=
=
≥
∈
≥
≥
) (
max min
) (
max min
) ( min
,.., 0 1
0 0
t t
T t
X
x
cx b Ax cx b Ax
z w
λ λ
λ
λ λ
λ
0
1
) (
min
≥
=
∀
− +
≥ λ
λ γ
γ
,..,T t
Ax b
cx
t tQualità del rilassamento
Facciamo il duale:
Osservando che 0
1
0 )
(
) (
max
1 1
1
≥
=
≤
−
−
=
∑
∑
∑
=
=
=
µ µ µ
µ
T t
t T
t
t t
T t
t t
b Ax
b Ax
w
0
1
1 1
≥
=
= ∑ ∑
=
=
µ µ
µ
Tt
t T
t
t t
