Parte V:
Disuguaglianze valide e
rappresentazione minimale di un
poliedro
Involucro convesso
- Consideriamo il seguente problema di programmazione lineare intera max{cTx: x∈X}
dove X = {x∈Z+n: Ax < b}.
- L'involucro convesso di X
conv (X) = {x: A'x < b', x > 0}
è un poliedro.
- Pertanto è sempre possibile riformulare un problema intero come problema di programmazione lineare.
- Purtroppo, per la maggior parte dei problemi non è possibile trovare una descrizione completa di conv(X).
- Pertanto l'obiettivo è determinare una buona approssimazione di conv(X) per una data istanze del problema intero.
Disuguaglianze valide
Definizione: Una disequazione aTx < α è valida per il poliedro P = {x∈ℜn : Ax < b} se e solo se P ⊆ {x∈ℜn : aTx < α}, ovvero se e solo se la disequazione è soddisfatta da tutte le soluzioni ammissibili del sistema Ax < b (diremo che aTx < α è implicata dal sistema Ax < b).
Consideriamo il seguente problema di programmazione lineare intera max 3x1 + 2x2
4x1 + 2x2 < 15 (1) x1 + 2x2 < 8 (2) x1 + x2 < 5 (3) x1, x2 > 0, intere
4x1 + 2x2 = 15
x1 + 2x2 = 8
x + x = 5
Disuguaglianze valide
Dalla combinazione conica dei vincoli (1) e (2) si ottiene la disequazione
5x
1+ 4x
2< 23
Poiché ogni punto del poliedro soddisfa questa disuguaglianza, possiamo dire che essa è valida per il poliedro in esame.
Tuttavia questa disuguaglianza non è utile per il nostro obiettivo di
approssimare
la descrizione dell'involucro convesso. Infatti, essa nonpermette di ridurre in maniera significativa la regione ammissibile associata al rilassamento lineare del problema.
Disuguaglianze valide
Moltiplicando per 1/2 il vincolo (1) otteniamo la disuguaglianza 2x
1+ x
2< 7.5
Poiché x
1e x
2sono vincolate ad assumere valori interi, anche la quantità 2x
1+ x
2dovrà essere intera e quindi la disuguaglianza può essere riscritta nella forma
2x
1+ x
2< 7
Questa disuguaglianza è valida ed è certamente migliore della
precedente!
Disuguaglianze valide
La rappresentazione Ax < b di un poliedro P non è
univocamente determinata. Infatti, è sempre possibile
aggiungere alla rappresentazione nuove disuguaglianze
valide per P, ottenute come combinazione conica delle
disequazioni del sistema Ax < b, senza modificare la
regione ammissibile.
Dimensione di un poliedro
Definizione: La dimensione di un poliedro P, dim(P), è data dal massimo numero di vettori affinemente indipendenti appartenenti a P meno uno.
Se dim(P) = n allora diremo che P ha dimensione piena.
Ricordiamo che:
Un insieme di punti x1, . . . , xk è affinemente indipendente se l'unica soluzione del sistema
Σ
λixi = 0Σ
λi = 0 è λi = 0 per ogni i = 1, ..., k.i = 1 k
i = 1 k
Dimensione di un poliedro
Consideriamo il seguente poliedro x1 < 2
x1 + x2 < 4 x1 + 2x2 < 10 x1 + 2x2 < 6
x1 + x2 > 2 x1, x2 > 0
x1 + x2 = 2
x1 + x2 = 4
x1 +2 x2 = 6 x1 +2 x2 = 10 x1 = 2
P
P ha dimensione piena. Infatti i vettori (2,0), (1,1) e (2,2) sono tre vettori affinemente indipendenti in P. Pertanto dim(P) = 2.
Dimensione di un poliedro
Consideriamo il seguente poliedro x1 < 2
x1 + x2 < 4 x1 + 2x2 < 10 x1 + 2x2 < 6
x1 + x2 > 2 x1, x2 > 0
x1 + x2 = 2
x1 + x2 < 4
x1 +2 x2 = 6 x1 +2 x2 = 10 x1 = 2
P
La disuguaglianza x1 < 2 induce la seguente faccia di P:
F1 = {(2,2); (2,0)}
Dimensione di un poliedro
Consideriamo il seguente poliedro x1 < 2
x1 + x2 < 4 x1 + 2x2 < 10 x1 + 2x2 < 6
x1 + x2 > 2 x1, x2 > 0
x1 + x2 = 2
x1 + x2 < 4
x1 +2 x2 = 6 x1 +2 x2 = 10 x1 = 2
P
La disuguaglianza x1 + 2x2 < 6 induce la seguente faccia di P:
F2 = {(2,2); (0,3)}
Dimensione di un poliedro
Consideriamo il seguente poliedro x1 < 2
x1 + x2 < 4 x1 + 2x2 < 10 x1 + 2x2 < 6
x1 + x2 > 2 x1, x2 > 0
x1 + x2 = 2
x1 + x2 < 4
x1 +2 x2 = 6 x1 +2 x2 = 10 x1 = 2
P
La disuguaglianza x1 + x2 > 2 induce la seguente faccia di P:
F3 = {(2,0); (0,1)}
Dimensione di un poliedro
Consideriamo il seguente poliedro x1 < 2
x1 + x2 < 4 x1 + 2x2 < 10 x1 + 2x2 < 6
x1 + x2 > 2 x1, x2 > 0
x1 + x2 = 2
x1 + x2 < 4
x1 +2 x2 = 6 x1 +2 x2 = 10 x1 = 2
P
La disuguaglianza x1 > 0 induce la seguente faccia di P:
F4 = {(0,2); (0,3)}
Facce di un poliedro
Analizziamo le facce che abbiamo individuato:
• F
1= {(2,2); (2,0)} ⇒ dim(F
1) = 1 = dim (P) – 1
• F
2= {(2,2); (0,3)} ⇒ dim(F
2) = 1 = dim (P) – 1
• F
3= {(2,0); (0,1)} ⇒ dim(F
3) = 1 = dim (P) – 1
• F
4= {(0,2); (0,3)} ⇒ dim(F
4) = 1 = dim (P) – 1
Pertanto, F
1, F
2, F
3ed F
4sono facce massimali di P.
Rappresentazione minimale
Definizione: Se P ⊆ ℜ
nè tale che dim(P) = n, una rappresentazione Ax < b è minimale se e solo se ogni disequazione del sistema definisce una faccia massimale di P.
Poiché i vincoli
x
1< 2 x
1+ 2x
2< 6
x
1+ x
2> 2 x
1> 0
inducono facce massimali essi faranno parte della
rappresentazione minimale.
Rappresentazione minimale
Osserviamo invece che
– Il vincolo x
1+x
2<4 può essere ottenuto dalla combinazione conica dei vincoli x
1<2 e x
1+2x
2<3 e, pertanto, esso è ridondante.
– Il vincolo x
2>0 può essere ottenuto dalla combinazione
conica dei vincoli x
1<2 e x
1+x
2>2 e, pertanto, esso è
ridondante.
Rappresentazione minimale
Pertanto la rappresentazione minimale del poliedro è la seguente:
x
1< 2 x
1+ 2x
2< 6
x
1+ x
2> 2
x
1> 0
Parte VI:
Metodo dei piani di taglio
Piani di taglio
Consideriamo il seguente problema di programmazione lineare intera P : min{c
Tx: x ∈ X}
dove X = {x ∈ Z
+n: Ax < b}.
Il rilassamento lineare di P è dato da
P
RL: min{c
Tx: x ∈ X
RL} dove X
RL= {x > 0: Ax < b}.
Sia x*
RLla soluzione ottima di P
RL.
– Se x*RL è intera allora concide con la soluzione ottima x* di P.
– Se x*RL non è intera proviamo a migliorare la formulazione di PRL aggiungendo degli opportuni vincoli.
Piani di taglio
Definizione: Un piano di taglio è una disuguaglianza valida αTx < β tale che αTx*RL > β, ossia è una disuguaglianza valida per P ma violata dalla soluzione di PRL.
x1 x2
x*LP
piano di taglio
piano di taglio
Metodo dei piani di taglio
Una volta individuato un piano di taglio per la soluzione ottima x*RL di PRL, possiamo aggiungere tale disuguaglianza alla formulazione originaria (“migliorando” la rappresentazione poliedrale del problema) e iterare la procedura in modo da avvicinarci alla soluzione ottima intera.
Finché non ottieni l'ottimo x*
1. Calcola la soluzione ottima x*
RL.
2. Se x*
RLè intera STOP(x*
RL= x*), altrimenti vai al passo 3.
3. Genera un piano di taglio α
Tx < β.
4. Aggiungi il piano di taglio alla formulazione corrente e
torna al passo 2.
Disuguaglianze di Chvatal
PUNTO CHIAVE DEL METODO: E' necessario generare dei piani di taglio efficaci ossia vicini a conv(X).
DISUGUAGLIANZE DI CHVATAL: Consideriamo la regione ammissibile iniziale
X = {x ∈ Z
+n: Ax < b}
di P, con A∈Z+m ×n e b∈Zm.Teorema: Dato un vettore u∈ℜm, ui >0 per i = 1, ...,m, ogni disuguaglianza αTx < β con
αj =
Σ
uiaij
β =
∑
uibi
è una disuguaglianza valida per P.
i=1
i=1 m
m
Disuguaglianze di Chvatal
ESEMPIO: Formuliamo il problema di massimo matching su un grafo completo di cardinaliltà 3.
1
2 3
max y
12+y
13+ y
23y
ij∈ {0,1} ∀ (i, j) ∈ E y
12+y
13< 1
y
12+y
23< 1 y
13+y
23< 1
La soluzione ottima del problema intero ha valore 1 e corrisponde a scegliere soltanto uno degli archi del grafo.
La soluzione ottima del rilassamento lineare ha invece valore 3/2 e corrisponde a scegliere y12 = y13 = y23 = 1/2.
Disuguaglianze di Chvatal
Consideriamo il vettore u = [1/2, 1/2, 1/2]T.
Calcoliamo i coefficienti della disuguaglianza di Chvatal:
α1 =
Σ
uiai1 = (1/2+1/2) = 1
α2 =
Σ
uiai2 = (1/2+1/2) = 1 β
= Σ
uibi = (1/2+1/2+1/2) = 1
α3 =
Σ
uiai3 = (1/2+1/2) = 1
La disuguaglianza di Chvatal risultante è y12 + y13 + y23 < 1.
Aggiungedo questa disuguaglianza al problema e risolvendo il rilassamento lineare si ottiene la soluzione ottima intera.
Disuguaglianze di Chvatal
Osservazione: Le disuguaglianze valide di Chvatal non sono necessariamente dei piani di taglio.
Non abbiamo nessuna informazione su come determinare una disuguaglianza valida che sia anche un piano di taglio.
TAGLI DI GOMORY (1970)
Piani di taglio di Gomory
Consideriamo un problema di programmazione lineare intera in forma standard ed il suo rilassamento lineare
P : min cTx PRL : min cTx
Ax = b Ax = b
x∈Z+n x > 0
Sia x*RL = [(x*RL)B, (x*RL)N]T una soluzione ottima di PRL. Pertanto (x*RL)B= A–1Bb e (x*RL)N=0
Riscrivendo i vincoli di PRL in funzione delle componenti in base e di quelle fuori base si ottiene
xB+ A–1BANxN = A–1Bb
A' b'
Piani di taglio di Gomory
Se x*RL ha tutte le componenti intere allora coincide con la soluzione ottima x* di P. Altrimenti dovrà esistere almeno una componente (x*RL)h con valore frazionario.
Supponiamo che l'i-esimo vincolo nel sistema xB+ A'xN = b'
sia quello corrispondente alla componente xh, ossia xh+
Σ
aij'xj = bi'= (x*RL)hOsservazione: La precedente espressione è ottenuta come combinazione conica dei vincoli del problema e, pertanto, è un vincolo valido per P.
j ∈N
Piani di taglio di Gomory
Se consideriamo la parte intera inferiore dei coefficienti delle variabili fuori base, otteniamo la seguente disuguaglianza valida
xh+
Σ
aij'xj
< xh+Σ
aij'xj = bi'= (x*RL)h.Poiché ogni soluzione ottima x* è a componenti intere, possiamo ulteriormente rafforzare la precedente disuguaglianza e ottenere
xh+
Σ
aij'xj
<
bi'.
Per verificare che, effettivamente, quello ottenuto è un piano di taglio sostituiamo i valori di x*RL nella disuguaglianza trovata. Poiché (x*RL)N=0, otteniamo
(x*RL)h <
bi' =
(x*RL)h
che è chiaramente violata e quindi è un piano di taglio.
j ∈N j ∈N
j ∈N
Piani di taglio di Gomory
Pertanto, il metodo introdotto da Gomory permette di determinare dei piani di taglio per qualsiasi problema di programmazione lineare intera a partire dalla soluzione ottima del rilassamento lineare.
ESEMPIO: Consideriamo il seguente problema P
La soluzione ottima del rilassamento lineare è x*RL = [62/21, 68/21, 0, 0]T ed è associata alla matrice A–1BAN =
max x
1+x
2x
i> 0, intera
– 3x
1+ 12 x
2+ x
3= 30 6x
1– 3 x
2+ x
4= 8
1/21 4/21 2/21 1/21
Piani di taglio di Gomory
Riscrivendo i vincoli per le due componenti frazionarie della soluzione otteniamo
x
1+ 1/21 x
3+ 4/21x
4= 62/21 x
2+ 2/21 x
3+ 1/21x
4= 68/21
Pertanto, applicando il troncamento sui coefficienti delle variabili fuori base e sul termine noto in entrambi i vincoli otteniamo i piani di taglio di Gomory
