Nozioni di geometria

Parte V:

Rafforzamento di formulazioni e

algoritmo dei piani di taglio

Nozioni di geometria

Definizione: Un vettore y∈ℜⁿ

è

dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

x

, con λ

> 0, per ogni i = 1,…,k.

k i = 1

Definizione: Un vettore y∈ℜⁿ

è

dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

x

, con Σ ^λ

= 1.

k

i = 1 k

i = 1

Definizione: Un vettore y∈ℜⁿ

è

dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

x

, con Σ ^λ

^{= 1 e λ}

> 0, per ogni i = 1,…,k.

k

i = 1 k

i = 1

Nozioni di geometria

Definizione: Dato un insieme S ⊆ ℜⁿ

, l’involucro convesso di S, conv(S), è l’insieme di tutti i vettori ottenibili come combinazione convessa di sottoinsiemi finiti di vettori di S.

Definizione: Dato un insieme convesso S, un vettore y∈S si dice estremo

se e solo se esso non è ottenibile come combinazione convessa di altri vettori in S.

Definizione: Un poliedro P = {x∈ℜⁿ

: Ax < b} è un insieme convesso

con un numero finito di punti estremi detti vertici di P.

Nozioni di geometria

Definizione: Una disequazione a^Tx < α è valida per il poliedro P = {x∈ℜⁿ : Ax < b} se e solo se P ⊆ {x∈ℜⁿ : a^Tx < α}, ovvero se e solo se la disequazione è soddisfatta da tutte le soluzioni ammissibili del sistema Ax < b (a^Tx < α è implicata dal sistema Ax < b).

Definizione: Una disequazione valida a^Tx < α definisce una faccia F = P ∩ {x∈ℜⁿ : a^Tx = α}. L’insieme {x∈ℜⁿ : a^Tx = α} è detto iperpiano di supporto di F.

Ogni faccia di un poliedro è essa stessa un poliedro.

Definizione: La dimensione di un poliedro P, dim(P), è data dal massimo numero di vettori affinemente indipendenti appartenenti a P meno uno.

Data una faccia F di P, risulta sempre dim(F) < dim (P).

Se dim(F) = dim(P), F è detta faccia impropria di P.

Se dim(F) = dim(P) – 1, F è detta faccia massimale di P.

Se dim(F) = 0, F coincide con un vertice di P.

Nozioni di geometria

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.

Definizione: Una rappresentazione Ax < b è minimale se, rimuovendo una qualsiasi disequazione dal sistema si ottiene un nuovo sistema A’x < b’ tale che P ⊂ {x∈ℜⁿ: A’x < b’}.

Definizione: Se P ⊆ ℜⁿ è tale che dim(P) = n, una rappresentazione Ax < b è minimale se e solo se ogni disequazione del sistema definisce una faccia massimale di P.

Formulazioni di problemi di PL 0-1

Ricordiamo che, date due diverse formulazioni lineari P

e P

di un problema di programmazione lineare 0-1 della forma (1), diremo che P

è migliore di P

se e solo se P

⊂ P

.

La formulazione ottima di un problema di programmazione lineare 0-1 della forma

è costituita dal poliedro contenuto in tutti i poliedri contenenti S, ovvero dall’involucro convesso conv(S). Indichiamo con P

la formulazione ottima.

max c

x

x∈S (S ⊆ {0,1}

)

Formulazioni di problemi di PL 0-1

Ricordiamo ancora che, dato un problema di programmazione lineare 0-1

max c

x (1)

x∈S (S ⊆ {0,1}

)

un poliedro P = {x∈ℜ

: Ax < b} è una formulazione lineare del problema se e solo se S = P ∩ {0,1}

.

Teorema: Un problema di programmazione lineare 0-1 della forma

(1) ammette sempre una formulazione lineare conv(S) con la

proprietà che x∈S se e solo se x è un vertice di conv(S).

Formulazioni di problemi di PL 0-1

Dal teorema precedente, possiamo riscrivere il problema (1) nella forma

max c

x (2)

x∈P

Infatti, poiché i vertici di P

coincidono con i vettori in S, risolvere il problema (1) è equivalente ad individuare un vertice di P

che minimizzi c

x, ovvero ad individuare un vertice ottimo per il problema (2).

Pertanto, ogni problema di programmazione lineare 0-1 può essere

espresso come problema di programmazione lineare.

Il fatto che si possa passare da un problema di programmazione lineare 0-1 a un problema di programmazione lineare suggerisce importanti conseguenze riguardanti la complessità computazionale:

infatti, è noto che un problema di programmazione lineare può essere risolto in tempo e spazio polinomiali ricorrendo a opportuni algoritmi.

Tuttavia…è errato pensare che algoritmi polinomiali per problemi di programmazione lineare possano essere utilizzati per risolvere qualsiasi problema di programmazione lineare 0-1.

Formulazioni di problemi di PL 0-1

Alcuni metodi per la programmazione lineare richiedono una rappresentazione esplicita della formulazione P_S. Tale rappresentazione è teoricamente ottenibile per qualsiasi problema di programmazione lineare 0-1 ma è spesso algoritmicamente impraticabile.

Invece altri metodi,come il Metodo dell’Ellissoide, si accontentano di una rappresentazione implicita della formulazione P_S fornita dal cosiddetto Oracolo di Separazione.

Tale oracolo è realizzato da un algoritmo che, dato un vettore x^’∈ℜⁿ, o genera un iperpiano che separa x^’ da P_S oppure conclude che x^’∈P_S.

L’oracolo di separazione descrive P_S in modo algoritmico e rende i metodi che lo utilizzano indipendenti dal numero di disequazioni della rappresentazione esplicita.

Formulazioni di problemi di PL 0-1

Rafforzamento di formulazioni

Il problema di knapsack max 5x

+ 2x

3x

+ 4x

< 6

x ∈ {0,1}

ha come rilassamento lineare max 5x

+ 2x

3x

+ 4x

< 6 x

> 0

x

> 0 x

< 1 x

< 1

Sia x

la soluzione ottima del rilassamento.

Oracolo di Separazione

Dato il vettore x

, l’oracolo di separazione consente

– di individuare una disequazione soddisfatta da tutti i vettori in

(valida per P

), e non soddisfatta dal vettore x

OPPURE – di concludere che x

∈

.

Dal punto di vista geometrico, l’oracolo costruisce, se esiste, un iperpiano che separa x

da P

. Se tale iperpiano non esiste allora il punto x

appartiene a P

.

L’iperpiano individuato è detto iperpiano di separazione o

piano di taglio.

Oracolo di Separazione

x1

x2

x^*

LP

L’oracolo viene generalmente realizzato tramite un algoritmo

detto Algoritmo di Separazione.

Disuguaglianze valide per il Knapsack 0-1

Consideriamo l’insieme

X = {x ∈ {0,1}ⁿ

: Σ

< b}.

Definizione: Un insieme C ⊆ N è un cover

se e solo se Σ

Un cover è

se, comunque preso j ∈C, l’insieme C \ { j } NON è un cover.

Osservazione: Un insieme C è un cover se e solo se il suo vettore

caratteristico x

non è ammissibile per X.

n

j = 1

j ∈ C

Teorema: Se C ⊆ N è un cover per X, la disequazione

Σ

< |C| – 1 (*) è valida per X.

Dimostrazione: Dimostriamo che se un generico vettore x^R

non soddisfa il vincolo (*) allora x

∉

Se x

è tale che Σ

> |C| – 1, allora |R ∩ C|= |C| e quindi C ⊆

Pertanto:

Σ

Σ

Σ

ovvero x

∉

Disuguaglianze valide per il Knapsack 0-1

j ∈C

j ∈C

j =1 n

j ∈R j ∈C

Consideriamo il problema di knapsack

max 15 x

+ 9 x

+ 8 x

+ 6 x

+ 5 x

+ 4 x

+ x

11 x

+ 6 x

+ 6 x

+ 5 x

+ 5 x

+ 4 x

+ x

< 19 x ∈ {0,1}

La soluzione associata al suo rilassamento lineare è (x

)

= (1, 1, 1/3, 0, 0, 0, 0).

Una disequazione cover violata da (x

)

è la disequazione x

+ x

+ x

< 2.

Qual è il problema di separazione che consente di individuare una disequazione di tipo cover violata da (x

)

?

Esempio

Oracolo di separazione

Riscriviamo la disequazione Σ

< |C| – 1 nella forma 1 + Σ

- |C| < 0 ⇔ 1 + Σ ^(x

– 1) < 0

La disequazione è violata da (x

)

se e solo se:

1 + Σ ((x

)

– 1) > 0

Quindi, possiamo massimizzare la violazione definendo SEP = max { Σ ((x

)

– 1) : Σ

> b}

Un algoritmo per SEP è un oracolo di separazione.

j ∈C

j ∈C j ∈C

j ∈C

j ∈C j ∈C

C ⊆ N

Siano

– y

la soluzione ottima del problema SEP, e

– z

il corrispondente valore della funzione obiettivo.

Se 1 + z

> 0, allora esiste una disuguaglianza cover violata da y

.

Se 1 + z

< 0, allora non esiste una disuguaglianza cover violata da y

.

A questo punto non resta che formulare come programmazione lineare 0-1 il problema di separazione.

Oracolo di separazione

Formulazione del problema di separazione

Il problema di separazione può essere formulato come un problema di programmazione lineare 0-1 in cui la variabile y

= 1 se j∈C e

= 0 altrimenti.

Funzione Obiettivo

max Σ ((x

)

– 1)y

Σ

> b + 1

y ∈ {0,1}ⁿ

Osservazione: I coefficienti in funzione obiettivo sono < 0 e quindi il

problema non ammette una soluzione banale.

j ∈N

j ∈N

Trasformazione

Ponendo w

= 1 – y

, il problema di separazione diventa

Poiché Σ ((x

)

– 1) è una costante nella nuova funzione obiettivo, si ottiene…

Funzione Obiettivo

max Σ ((x

)

– 1) – Σ ((x

)

– 1)w

– Σ

> – Σ

+ b + 1

w ∈ {0,1}ⁿ

j ∈N

j ∈N j ∈N

j ∈N

j ∈N

…un problema di knapsack

Funzione Obiettivo max Σ (1 – (x

)

)w

Vincoli Σ a

w

< Σ a

– b – 1 w ∈ {0,1}

j ∈N j ∈N

j ∈N

Esempio

max 15 x

+ 9 x

+ 8 x

+ 6 x

+ 5 x

+ 4 x

+ x

11 x

+ 6 x

+ 6 x

+ 5 x

+ 5 x

+ 4 x

+ x

< 19

x^*_LP

= (1, 1, 1/3, 0, 0, 0, 0)

Problema di separazione

max (1 – 1) w

+ (1 – 1) w

+ (1 - 1/3) w

+ w

+ w

+ w

+ w

11 w

+ 6 w

+ 6 w

+ 5 w

+ 5 w

+ 4 w

+ w

< 38 – 19 – 1 = 18

Separazione

Problema di separazione

max 2/3 w

+ w

+ w

+ w

+ w

11 w

+ 6 w

+ 6 w

+ 5 w

+ 5 w

+ 4 w

+ w

< 18 w ∈ {0,1}

Soluzione 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 z

= –2/3.

Pertanto, 1 + z

= 1/3 > 0

Pertanto…

1. Il valore di 1 + z

è > 0, ovvero esiste una disequazione cover violata.

2. La disequazione è scritta in corrispondenza degli indici che hanno valore 1 in y

, ovvero

y* = (1, 1, 1, 0, 0, 0, 0) corrisponde a x

+ x

+ x

< 2

Algoritmo dei piani di taglio

Dato il rilassamento lineare di un problema di knapsack 1. Calcola la soluzione ottima x

.

2. Se x

∈ {0, 1}

STOP, altrimenti vai al passo 3.

3. Definisci il problema di separazione.

4. Risolvi il problema di separazione.

5. Se esiste una disequazione cover violata aggiungila

alla formulazione corrente e torna al punto 1, altrimenti

STOP.

Pianificazione degli investimenti

Dati

– I = {1, 2, …, n} = insieme di investimenti attivabili su un orizzonte temporale T = {1, 2, …, t} di t periodi

– Ad ogni investimento i è associato un indice di redditività c_i

– Ogni investimento i genera un flusso di cassa a_i = (a_i1, a_i2, …, a_it) (>

0 introiti, < 0 esborsi) per ogni periodo j ∈T

– Per ogni periodo j∈T esiste un budget b_jche limita gli esborsi (flussi di cassa negativi).

Problema

Determinare l’insieme di investimenti

⊆

che massimizza la

redditività e che rispetta il vincolo per cui la somma dei flussi di

cassa degli investimenti attivati in ogni periodo

non superi il

budget b

.

Esempio

Investimento 1

Investimento 2

Investimento 3

Periodo 1 b₁ = –4

Periodo 2 b₂ = –5

Periodo 3 b₃ = –1 a₁₁=2

a₂₁=3

a₃₁=–6

a₁₂=–10

a₂₂=–3

a₃₂=2

a₁₃=–2

a₂₃=5

a₃₃=–3

Esempio

Formulazione

Variabili decisionali

x_i

= 1 se il progetto i è attivato

= 0 altrimenti

Nell’esempio precedente, se vengono attivati tutti e tre gli investimenti il vincolo di budget nel periodo 2 NON è rispettato.

max Σ

Σ

> b

x∈{0,1}

i∈I i∈I

max c

x∈{0,1}

Per migliorare la formulazione precedente, consideriamo un singolo vincolo di budget del sistema Ax > b e il problema di Knapsack continuo ad esso associato:

Rilassamento lineare

(KP

) max c

x

a

x > b

0 < x < 1

max c

x

– a

x < –b

0 < x < 1

cambiamo segno nel vincolo

Rafforzamento

L’insieme delle soluzioni del problema di pianificazione originario è costituito dall’intersezione degli insiemi delle soluzioni dei singoli problemi di knapsack (KP

).

Pertanto, è possibile rafforzare ciascun problema KP

, ad

esempio con disequazioni cover, per ottenere un

rafforzamento della formulazione di pianificazione.

Esempio

Consideriamo la seguente istanza di un problema di pianificazione:

– I = {1, 2, 3, 4, 5}

– T = {1, 2, 3}

– c = (3, 7, 3, 5, 7) = Redditività – b = (-2, 0, -5) = Budget

– a

= (-4, 1, -2) = Flusso di Cassa I

– a

= (2, -4, 1) = Flusso di Cassa I

– a

= (1, 3, -5) = Flusso di Cassa I

– a

= (1, -3, -2) = Flusso di Cassa I

– a

= (-3, 4, 1) = Flusso di Cassa I

Esempio

1 0

5 2

5 2

0 4

3 3

4

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

≤

≤

≤

− +

+

−

≤

− +

− +

−

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

x x

x x

x

x x

x x

x

La soluzione ottima di (PL) è:

x

= [0.67; 1; 0.74; 0.96; 1] di valore z = 23.09

(PL)

Il rilassamento lineare si scrive (considerando il

cambiamento di segno sul vincolo di budget)

Esempio

Consideriamo a questo punto il primo vincolo di budget e il problema di knapsack continuo ad esso associato:

1 0

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

≤

≤

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

(KP

)

Effettuiamo un cambio di variabili per ottenere tutti coefficienti positivi nel vincolo di knapsack:

J(–) = {2, 3, 4} ⇒ y

= 1 – x

per ogni i ∈ J(–).

Si ottiene:

6 3

2

4 x

+ y

+ y

+ y

+ x

≤

Esempio

Dobbiamo vedere se esiste una cover violata rispetto alla soluzione:

Risolvendo il problema di separazione si individua la cover violata

+ x

< 1, che si può aggiungere direttamente alla formulazione, essendo già nelle variabili x.

Osservazione: Se la cover contiene variabili y, bisogna effettuare il

cambio di variabile y

prima di aggiungere la disequazione alla formulazione

La nuova soluzione ottima del RL (peraltro intera) è

x

= [0.67; 1–1 = 0 ; 1–0.74 = 0.26; 1–0.96 = 0.04; 1]

x

= [0; 1; 1; 1; 1] di valore z = 22.

Parte VI:

Formulazioni con un numero di

vincoli non polinomiale

Metodo del Simplesso Dinamico Primale

Il metodo del simplesso può essere usato per risolvere un problema di ottimizzazione combinatoria qualora sia nota una rappresentazione del tipo Ax < b (rappresentazione esterna) dell’involucro convesso dei suoi insiemi ammissibili conv (S).

Domanda: Abbiamo realmente bisogno di una

rappresentazione esterna di conv (S)?

Problema del cammino minimo

Sia G = (V, E) un grafo non orientato.

Dati

s, t ∈ V

l

∈ R

∀ uv ∈ E = lunghezza dell’arco uv Problema

Determinare un (s, t)-cammino di lunghezza totale minima.

Variabili decisionali

x

= 1 se l’arco ij appartiene all’ (s, t)-cammino

x

= 0 altrimenti

(s, t)-tagli

Un (s, t)-taglio è una partizione (X, V\X) dei vertici di G tale che s∈X e t∈V\X.

L’insieme K di archi con un estremo in X e l’altro in V\X definisce gli archi del taglio. Si dice peso del taglio la somma dei pesi degli archi in K.

Esempio

s t

1 2 3

4

5

6

X = {s, 1, 4, 5}, V\X = {2, 3, 6, t}

K = {12, 34, 46, 56}

Formulazione

Ciascun vincolo esprime la condizione che almeno un arco di ogni (s, t)-taglio deve appartenere al cammino da s a t.

E K uv

uv E uv

uv uv

x

x x l

} 1 , 0 {

1 min

∈

∑ ≥

∑

∈

∈

∀ K corrispondente a un (s, t)-taglio

Osservazioni

Il numero dei vincoli è esponenziale rispetto alla cardinalità di E.

Sebbene la matrice dei coefficienti non sia totalmente unimodulare, il rilassamento lineare (PL) di (P) fornisce la soluzione ottima del problema intero.

Tuttavia, nella pratica il numero di vincoli rende impossibile

“scrivere” le matrici del metodo del simplesso.

Simplesso Dinamico Primale

Il simplesso dinamico primale acquisisce le informazioni sulla struttura del poliedro attraverso un oracolo di separazione.

Oracolo di separazione

Dato x

∈ R

, l’oracolo di separazione restituisce una disequazione a

x ≤ b

del sistema Ax ≤ b violata da x

oppure conclude che tutte le disequazioni del sistema Ax

≤ b sono soddisfatte da x

.

Algoritmo

Supponiamo di voler risolvere il problema (P)

1 0

max

≤

≤

≤ x

b Ax

x c

dove A è una matrice (m × n) e b∈ R

.

Sia D una sottomatrice di A con q << m righe e n colonne. Definiamo il sottoproblema iniziale:

( )

1 0

max

≤

≤

≤ x

d Dx

x

c

P ~

Algoritmo

(P) è

inammissibile Risolvere il problema ( )_P^~

È ammissibile? no

si

= soluzione ottima di ( )_P^~

x

Esiste un vincolo violato?

no soluzione ottima di (P)

x

Si aggiunge il vincolo violato a^tx ≤ b₀ a ( )^P~

si

Esempio

s t

2 3

1 4

3

2

1 1

1 1

1

1

Trovare l’(s, t)-cammino di lunghezza minima sul grafo in figura.

Partiamo dalla formulazione:

E uv

x x x

x x

x x

x x

x x

x x

uv t t

s s

t t

s s

∈

∀

≤

≤

≥ +

≥ +

+ +

+ +

+ +

+

1 0

1

1 2

3 min

4 3

2 1

3 4

34 14

23 12

2 1

( ) P ~

Esempio

La soluzione ottima è data da

0 1

3 34

14 23

12 1

4 2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x x

x x

Oracolo di separazione

Associamo il peso ad ogni arco uv∈E e cerchiamo l’

(s, t)-taglio di peso minimo K

.

Se il peso di K

è < 1 allora il relativo vincolo è violato da . Se il peso di K

è ≥ 1 allora non ci sono disequazioni violate.

x

x

Esempio

s t

2 3

1 4

0

1

0 0

0 0

1

0

X = {s, 2}

K

= {s1, 12, 23}

Aggiungiamo al problema ( ) il vincolo e risolviamo di nuovo.

23

1

12

1

+ x + x ≥

x

P ~

Esempio

La nuova soluzione ottima è data da

0 1

3 34

14 23

1

4 12

2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x

x x

x

s t

2 3

1 4

0

1

0 0

0 1

1

0

X = {s, 1, 2}

K

= {14, 23}

Esempio

Aggiungiamo il vincolo violato:

23

1

14

+ x ≥ x

La nuova soluzione ottima è:

0 1

3 34

14 12

1

4 23

2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x

x x

x

Esempio

s t

2 3

1 4

0

1

0 0

1 0

1

0

X = {s, 2, 3}

K

= {s1, 12, 34, 3t}

Aggiungiamo il vincolo violato:

3

1

34 12

1

+ + +

≥

s

x x x

x

Esempio

La nuova soluzione ottima è data da

0 1

4 34

14 12

1

3 23

2

=

=

=

=

=

=

=

=

t s

t s

x x

x x

x

x x

x

s t

2 3

1 4

0

1

0 0

1 0

0

1

Non esistono (s, t)-tagli di peso < 1 ⇒ STOP.

Il minimo albero ricoprente

Dati

G (V, E) grafo connesso, c

> 0 costo associato ad ogni arco e ∈ E.

Problema

Trovare un albero ricoprente di costo minimo.

Algoritmi combinatori noti: Prim e Kruskal

Formulazione

x

=

1 se l’arco ij appartiene all’albero ricoprente 0 altrimenti

min Σ c

x

Σ x

= n – 1 (1)

Σ x

< |S| – 1 ∀ S ⊆ V : 2 < |S| < n – 1 (2) x > 0

ij ∈ E

ij ∈ E

ij ∈ E(S)

RILASSAMENTO LINEARE

Osservazioni

1.I bound x < 1 sono implicati dai vincoli (2).

2.La matrice dei vincoli non è totalmente unimodulare.

Infatti, consideriamo un grafo con 5 nodi e i seguenti vincoli di tipo (2):

che ha determinante –2 e, quindi, non è totalmente unimodulare.

Nonostante la matrice dei coefficienti non sia totalmente unimodulare, il rilassamento lineare fornisce una soluzione intera. Tuttavia,il numero dei vincoli cresce esponenzialmente con il numero dei nodi del grafo.

3 3 2

34 45

23

15 45

12

23 12

≤ +

+

≤ +

+

≤ +

x x

x

x x

x

x x

1 1

0

1 0

1

0 1

1

x₄₅ x₂₃

x₁₂

matrice associata

Esempio

2

1

3

4

8 9

6

5 7

2 2

5 10

4 1

3 8 9

2 5

3

0 1

8 st

5 3

2 5

2 2

9 8

10 1

3 4

min

67 57

56 89

49 48

45 35

34 23

13 12

67 57

56 89

49 48

45 35

34 23

13 12

≥

≤

= +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

Consideriamo il sottoproblema

con la sola famiglia di vincoli

(1).

Soluzione del primo sottoproblema

Valore della soluzione: 22

Gli archi verdi di maggiore spessore corrispondono a variabili poste a 1.

2

1

3

4

8 9

6

5 7

2 2

5 10

4 1

3 8 9

2 5

3

Domanda: Esiste un vincolo della famiglia

violato dalla soluzione ottima corrente? SI

Ad esempio, x

+ x

+ x

< 2 che viene aggiunto alla formulazione corrente.

Separazione

1

|

| 2 che tale

, ogni per

1

|

)

|

(

≤ − ≤ ≤ −

∑

^x

^{S S S n}

0 1

2

8 st

5 3

2 5

2 2

9 8

10 1

3 4

min

89 49

48

67 57

56 89

49 48

45 35

34 23

13 12

67 57

56 89

49 48

45 35

34 23

13 12

≥

≤

≤ +

+

= +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+

x x

x x

x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

Soluzione del secondo sottoproblema

Valore della soluzione: 22

Gli archi verdi di maggiore spessore corrispondono a variabili poste a 1

2

1

3

4

8 9

6

5 7

2 2

5 10

4 1

3 8 9

2 5

3

Separazione

Domanda: Esiste un vincolo della famiglia

violato dalla soluzione ottima corrente? SI

Ad esempio, x

+ x

+ x

< 2 che viene aggiunto alla formulazione corrente

0 1

2 2

8 st

5 3

2 5

2 2

9 8

10 1

3 4

min

67 57

56

89 49

48

67 57

56 89

49 48

45 35

34 23

13 12

67 57

56 89

49 48

45 35

34 23

13 12

≥

≤

≤ +

+

≤ +

+

= +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+

x x

x x

x

x x

x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

1

|

| 2 che tale

, ogni per

1

|

)

|

(

≤ − ≤ ≤ −

∑

^x

^{S S S n}

Soluzione del terzo sottoproblema

Valore della soluzione: 25

Gli archi verdi di maggiore spessore corrispondono a variabili poste a 1.

2

1

3

4

8 9

6

5 7

2 5 10

4 1

3 8 9

2 5

3

Separazione

Domanda: Esiste un vincolo della famiglia

violato dalla soluzione ottima corrente? SI

Ad esempio, x

+ x

+ x

< 2 che viene aggiunto alla formulazione corrente.

0 1

2 2 2

8 st

5 3

2 5

2 2

9 8

10 1

3 4

min

23 13

12

67 57

56

89 49

48

67 57

56 89

49 48

45 35

34 23

13 12

67 57

56 89

49 48

45 35

34 23

13 12

≥

≤

≤ +

+

≤ +

+

≤ +

+

= +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+

x x

x x

x

x x

x

x x

x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

1

|

| 2 che tale

, ogni per

1

|

)

|

(

≤ − ≤ ≤ −

∑

^x

^{S S S n}

Valore della soluzione: 30

Gli archi verdi di maggiore spessore corrispondono a variabili poste a 1.

Soluzione del quarto sottoproblema

2

1

3

4

8 9

6

5 7

2 5 10

4 1

3 8 9

2 5

3

Separazione

Domanda: Esiste un vincolo della famiglia

violato dalla soluzione ottima corrente? NO

La soluzione trovata è ottima per il rilassamento ed è anche INTERA, ovvero ottima per PL-{0,1}.

1

|

| 2 che tale

, ogni per

1

|

)

|

(

≤ − ≤ ≤ −

∑

^x

^{S S S n}

Formulazione “cutset” per il minimo albero ricoprente

x

=

1 se l’arco ij appartiene all’albero ricoprente 0 altrimenti

min Σ c

x

Σ x

= n – 1 (1)

Σ x

> 1 ∀ S ⊆ V : 1 < |S| < n – 1 (2) x > 0

ij ∈ E

i∈S, j∈δ(S)

RILASSAMENTO LINEARE

La formulazione cutset non è intera.

Infatti, consideriamo il seguente sottoproblema ottenuto tramite la formulazione cutset:

0 1

1 1 1

8 st

5 3

2 5

2 2

9 8

10 1

3 4

min

45 35

45 34

35 34

67 57

56 89

49 48

45 35

34 23

13 12

67 57

56 89

49 48

45 35

34 23

13 12

≥

≤

≥ +

≥ +

≥ +

= +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+ +

+

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

x x

Formulazione “cutset” per il minimo albero ricoprente

S contiene i nodi {1,2, 3} e non contiene i nodi {4,5}.

S contiene i nodi {4,8,9} e non contiene i nodi {3,5}.

S contiene i nodi {5,6,7} e non contiene i nodi {3,4}.

Soluzione frazionaria

1 1

0.5 1

1

0.5 0.5

1

1

Il problema così formulato ammette la seguente soluzione ottima

di valore 28.5 e che NON ha tagli violati !!!!

0.5

Problema di separazione

I vincoli utilizzati nella precedente formulazione del problema del minimo albero ricoprente, ossia

sono denominati subtour elimination constraint.

Vogliamo formulare il problema di separazione per tali vincoli.

Consideriamo le seguenti variabili decisionali:

z

= 1 se j ∈ S z

= 0 altrimenti

1

|

| 2 che tale

, ogni per

1

|

)

|

(

≤ − ≤ ≤ −

∑

^x

^{S S S n}

Un vincolo subtour è violato dalla soluzione x*

se e solo se esiste un S tale che

ovvero se

1

|

)

|

(

*

− > −

∑

^x

^S

{ }

{ }

{ }

1 max

|

| max

* 1

, 0

) (

*

−

>

−

=

−

∑ ∑

∑

∈ ∈

∈

⊂ ∈

E

ij ij i j j V j

z

S E

ij ij

V S

z z

z x

S x

Problema di separazione

Osservazioni

1. Il problema

ha soluzione ottima di valore 0 con z = 0.

Per ovviare a ciò si deve fissare z

=1, per k = 1,…,|V|.

In questo modo si risponde alla domanda se esiste un vincolo di tipo subtour violato che contiene il vertice k.

2. Il problema non è un problema di PL-{0,1}. Si deve effettuare una linearizzazione.

{ }

{ }

1

max

1 , 0

−

>

∑

− ∑

∈ ij E ij i j j V j

z

x z z z

Linearizzazione

Introduciamo la variabile w

= z

z

. Il problema diventa

{ } { }

E ij

w z

z

z z

w

z w

z w

z w

x

E V

k

j i

ij

j ij

i ij

E

ij j V

j ij

ij

∈

∈

∈

=

−

≥

−

−

≤

−

≤

−

∑ − ∑

∈ ∈

ogni per

1 , 0 ,

1 , 0

1

1 0 0 st

max

|

|

|

|

*

Linearizzazione

I vincoli possono essere eliminati in quanto i coefficienti delle w

nella funzione obiettivo sono > 0 ovvero,

Questo implica che il vincolo è sempre soddisfatto in quanto

Eliminando questi vincoli osserviamo anche che la matrice dei coefficienti è totalmente unimodulare. Pertanto, può essere rimossa anche la stipula di interezza.

Possiamo pertanto concludere che il problema di separazione dei subtour elimination constraint è “facile”.

− 1

≥

−

−

ij

z z

w

{ , } min

ij

z z

w =

{ , } 1

min z

z

≥ z

+ z

-