Lower (upper) bound

Parte II:

Ottimalità, rilassamenti e bound

Sommario

• Definizioni di bound primali e duali.

• Rilassamento di un problema di OC.

• Esempi di rilassamenti per il problema del TSP:

– Il rilassamento 1-albero.

– Il rilassamento 2-abbinamento.

• Bound primali per il TSP:

– Nearest Neighbor e Insertion.

– Algoritmi approssimati (Double Tree, Christofides).

• Bound dal rilassamento lineare:

– Il rilassamento lineare del knapsack.

– Bound primali: algoritmo greedy.

• Bound per dualità.

• Formulazioni di PL.

• Formulazioni ideali e matrici TU.

Ottimalità, rilassamenti e bound

Consideriamo il seguente problema

z^* = max {c^Tx : x ∈ X, X ⊆ {0,1}ⁿ }

dove z* è il valore della soluzione ottima x*.

Domanda: In che modo è possibile certificare che la soluzione x*

è ottima?

In generale, se disponessimo di un algoritmo che genera le due sequenze di soluzioni:

z^{UB 1} > z^{UB 2} > …> z^{UB h} > z*

z^{LB 1} < z^{LB 2} < …< z^{LB k} < z*

potremmo fornire come criterio di arresto z^{UB h} - z^{LB k} < ε (> 0)

Lower (upper) bound

Bound primali

Ogni soluzione x ∈ X ammissibile è un lower (upper) bound per un problema di massimizzazione (minimizzazione)

z*

z^{LB 2} z^{LB 1}

z*

z^{UB 1} z^{UB 2}

Upper (lower) bound

Bound duali

Al contrario dei bound primali, trovare upper (lower) bound di buona qualità per problemi di massimo (minimo) è tipicamente difficile.

Buoni bound duali si ottengono attraverso lo studio delle proprietà strutturali del problema di OC.

Le proprietà di un problema di OC si caratterizzano tramite:

1. Rilassamenti del problema

2. Definizione e studio di problemi duali.

Rilassamento

Definizione: Il problema

(RP) z^R = max {f(x) : x ∈ T, T ⊆ Rⁿ } (z^R = min {f(x) : x ∈ T, T ⊆ Rⁿ }) si definisce rilassamento del problema

(P) z = max {c^Tx : x ∈ X, X ⊆ {0,1}ⁿ } (z = min {c^Tx : x ∈ X, X ⊆ {0,1}ⁿ }) se e solo se:

i) X ⊆ T,

ii) f(x) > c^Tx per ogni x ∈ X (f(x) < c^Tx per ogni x ∈ X)

Proprietà 1: Se RP è un rilassamento di P, allora z^R > z^* (z^R < z^*).

Proprietà 2: Se x^R sol. ottima di RP è ammissibile per P allora x^R = x^*.

Esempi di rilassamenti

Problema del commesso viaggiatore (simmetrico).

Dati: grafo G = (V, E); pesi sugli archi c_e per ogni arco e ∈E.

Domanda: trovare il ciclo hamiltoniano di peso minimo.

Definizione: Un 1-albero è un sottografo di G che consiste di due archi adiacenti al nodo 1 più gli archi di un albero ricoprente i nodi {2, …, n}.

1

2

3

5

4 Esempio

Rilassamenti per il TSP

Osservazione: Un ciclo hamiltoniano è un particolare 1-albero.

1

2

3

5

4

Pertanto, il problema

Dati: grafo G = (V,E), pesi sugli archi c_e per ogni arco e ∈E.

Domanda: trovare l’1-albero di peso minimo.

è un rilassamento del problema del TSP, perché l’insieme X di tutti i cicli hamiltoniani è contenuto nell’insieme T di tutti gli 1-alberi.

Definizione: Dato un grafo G = (V, E), un 2-abbinamento su G è un insieme di archi M tale che ogni nodo in V è estremo di esattamente due archi in M.

Rilassamenti per il TSP

1

2

3

6

4

5

Un 2-abbinamento forma un insieme di cicli disgiunti.

Rilassamenti per il TSP

Osservazione: Un ciclo hamiltoniano è un particolare 2- abbinamento, difatti è un 2-abbinamento privo di sottocicli (subtour).

5 1

2

3

6

4

Pertanto, il problema

Dati: grafo G = (V,E), pesi sugli archi c_e per ogni arco e ∈E Domanda: trovare il 2-abbinamento di peso minimo

è un rilassamento del problema del TSP, perché l’insieme X di tutti i cicli hamiltoniani è contenuto nell’insieme T di tutti i 2-abbinamenti.

Un esempio

- 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99 99

10 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

Consideriamo la seguente istanza del problema del Commesso Viaggiatore:

Un esempio

1

2

3

6

4

5

- 99

99 1

1 6

- 10 1

1 99 99

5

99 1

- 1

99 99

4

99 1

1 -

99 10 3

1 99 99

10 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99 99

10 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

Il 2 abbinamento di peso minimo ha valore 6

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99 99

10 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

L’1-albero di peso minimo ha valore 15

Un esempio

1

2

3

6

4

5

- 10 99

99 1

1 6

10 -

1 1

99 99

5

99 1

- 1

99 99

4

99 1

1 -

10 99

3

1 99 99

10 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

Il ciclo hamiltoniano di peso minimo ha valore 24

Un esempio (2)

1

2

3

6

4

5

- 99 5

99 1

1 6

- 5 1 10

99 99

5

99 - 10

99 10 99

4

99 1

- 10 99 5

3

1 99 99

- 5 1

2

1 99 99

99 1

- 1

6 5

4 3

2 1

Il 2 abbinamento di peso minimo ha valore 24

Un esempio (2)

1

2

3

6

4

5

- 5

99 99

1 1

6

5 -

10 1

99 99

5

99 10

- 10 99

99 4

99 1

10 -

5 99 3

1 99 99

5 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

L’1-albero di peso minimo ha valore 19

Un esempio (2)

1

2

3

6

4

5

- 5

99 99

1 1

6

5 -

10 1

99 99

5

99 10

- 10 99

99 4

99 1

10 -

5 99 3

1 99 99

5 -

1 2

1 99 99

99 1

- 1

6 5

4 3

2 1

Il ciclo hamiltoniano di peso minimo ha valore 32

Ricapitolando…

Abbiamo definito per il TSP due lower bound con le seguenti proprietà:

1. Sono lower bound “combinatori”, ovvero si ottengono tramite la soluzione di un problema di OC.

2. Tutti e due i problemi la cui soluzione genera i lower bound sono

“facili”, ovvero hanno complessità polinomiale.

La proprietà 2. è una proprietà chiave per ogni bound duale.

Infatti, se il calcolo del bound fosse un problema NP-completo sappiamo che calcolare il bound diventa almeno tanto difficile quanto risolvere il problema stesso.

Domanda: Come si possono calcolare bound primali (ovvero soluzioni ammissibili di buona qualità) per il problema del TSP?

Algoritmi euristici

Definizione: Un algoritmo A si dice euristico per un problema P se restituisce una soluzione ammissibile z^A che non è garantito essere la soluzione ottima.

Definizione: Sia P un problema di minimizzazione. Un algoritmo euristico si dice δ-approssimato se

1. ha complessità polinomiale, e

2. per ogni istanza I di P con soluzione ottima z*(I), si ha z^A(I) / z*(I) < δ (1)

Osservazione: Se P è un problema di massimo, allora δ < 1 e la condizione (1) vale con il segno di >.

Euristiche per il TSP

Sia G = (V, E) un grafo completo e sia c_uv il costo di ciascun arco uv ∈ E.

Euristiche costruttive: tentano di costruire un “buon” ciclo hamiltoniano a partire da un sottociclo eventualmente vuoto.

Euristiche migliorative: a partire da una soluzione ammissibile, si tenta di migliorarla attraverso miglioramenti

“locali”.

Euristica Nearest Neighbor

Input: G = (V,E).

Output: ciclo hamiltoniano T.

procedure nearest_neighbor ()

Scegli un vertice u ∈∈∈∈ V qualsiasi;

W = V \ {u}, aggiungi u alla lista T while |W| > 0 {

scegli v ∈∈∈ W tale che c∈ _uv = min {c_uj : j ∈∈∈∈ W}

Aggiungi {v} alla lista T W = W \ {v}

u = v }

Esempio Nearest Neighbor

1000

2

1 2

5 4

La soluzione di valore 1005 è ottima?

Esempio Nearest Neighbor

1000

2

1 2

5 4

La soluzione ottima vale 12.

Osservazione: il rapporto z^A(I)/z*(I) può essere reso grande a piacere.

Euristiche di inserimento

Euristiche di inserimento

Euristiche di inserimento

Euristiche di inserimento

Input: G=(V,E).

Output: ciclo hamiltoniano T.

procedure insertion_heuristic ()

Inizializza T con un sottociclo W = V /T;

while (|W| > 0) {

scegli un vertice u ∈∈∈ W;∈

scegli la posizione in cui inserire u in T;

inserisci u in T;

elimina u da W;

}

Selezione del vertice da inserire

Definizione: Si definisce distanza di un vertice u da un ciclo T il peso del più piccolo arco che collega il vertice ad un altro qualsiasi vertice del ciclo.

T = (1, 2, .., k) ⇒ dist (u, T) = min { c_uv: v ∈∈∈∈ T}.

Nearest Insertion:

Inserisci il vertice u che minimizza dist (u, T), u ∉T.

Farthest Insertion:

Inserisci il vertice u che massimizza dist (u, T), u ∉T.

Selezione della posizione di inserimento

Osservazione: Scegliere la posizione equivale a scegliere l’arco da eliminare nel ciclo T. Un vertice può essere inserito in ogni posizione di T.

Siano T = (v₁, v₂, …, v_n) il ciclo corrente e c(T) il costo di T e sia u il nodo da aggiungere al ciclo.

Se c(T(i)) è il costo del ciclo ottenuto da T inserendo il nodo u nella posizione i-esima, il costo di inserimento è pari a

c(T(i)) - c(T).

Si seleziona la posizione che minimizza c(T(i)) - c(T).

Esempio

7

9

6 14 9 2

5

3

12 1

d = 7

d = 1

7

9

6 14 9 2

5

3

12 1

d = 7

d = 1 2

3 1

T = {1, 2, 3}

Esempio

7

9

6 14 9 2

5

3

12 1

2

3 1

C = 21

Esempio

7

9

6 14 9 2

5

3

12 1

2

3 1

C = 16

Esempio

7

9

6 14 9 2

5

3

12 1

2

4 1

C = 7 3

Esempio

Altre regole di selezione del vertice

Random Insertion:

Si sceglie un vertice a caso fra quelli non ancora inseriti nel ciclo.

Cheapest Insertion:

Si sceglie il vertice che può essere aggiunto al ciclo con il minimo aumento di costo.

Una proprietà strutturale

Si dice che la matrice delle distanze di un grafo G soddisfa la disuguaglianza triangolare se comunque prendo un triangolo e₁, e₂, e₃ in G si ha c_ei + c_ej > c_ek per i ≠ j ≠ k, i, j, k

∈ {1, 2, 3}

5

4

7 6

5 4

Richiamo

Definizione: G = (V, E) è un grafo euleriano se e solo se il grado di ogni nodo è pari.

Se G = (V, E) è un grafo euleriano e v è un vertice di G allora è possibile costruire un percorso che inizia e finisce in v e che attraversa ogni arco esattamente una volta.

Teorema: Sia H = (V, F) un grafo completo con la matrice dei costi che soddisfa la disuguaglianza triangolare. Sia G = (V, E) un sottografo euleriano connesso di H. H contiene un ciclo hamiltoniano di lunghezza al più

Σ

Dimostrazione (idea)

1

2

3

4

5

Sottografo euleriano

Come posso ricavare un ciclo hamiltoniano?

Poiché vale la disuguaglianza triangolare, c₂₅ < c₂₃ + c₃₅.

Euristica Double Tree

1. Calcola un minimo albero ricoprente K.

2. Raddoppia gli archi di K, formando un percorso euleriano.

3. Ricava un ciclo hamiltoniano dal percorso euleriano.

Indichiamo con z^H_DT il valore della soluzione che si ottiene applicando l’euristica Double Tree.

Da un percorso euleriano ad un ciclo hamiltoniano

Consideriamo un percorso euleriano (v₁, …, v_k).

procedure obtain_hamiltonian () T = {v₁}, i=2, v = v₁

while |T| < n { if v_i ∉∉ T∉∉

T = T ∪ {v_i} collega v a v_i v = v_i

i ++

}

collega v a v₁

T è un ciclo hamiltoniano.

Esempio

1 2

3

4

5

6 7

11 10 9

8

Tour euleriano (5,4,5,3,2,3,1,3,5,6,5,8,9,8,10,8,7,11,7,8,5)

Tour hamiltoniano (5,4,5,3,2,3,1,3,5,6,5,8,9,8,10,8,7,11,7,8,5)

Proprietà

Double tree è un algoritmo 2-approssimato per il TSP.

Dimostrazione:

1. z* > z_TREE (1-albero è un rilassamento per TSP).

2. Per costruzione, la lunghezza del “doppio albero” è 2 * z_TREE. 3. z^H_DT < 2 * z_TREE.

Pertanto:

z^H_DT / z* < 2 * z_TREE / z_TREE = 2.

Euristica di Christofides

1. Calcola un minimo albero ricoprente K.

2. Sia V ’⊆ V l’insieme dei vertici che hanno grado dispari in K.

3. Trova il matching perfetto M di peso minimo sui nodi V’’.

4. M ∪ K è un percorso euleriano.

5. Ricava un ciclo hamiltoniano dal percorso euleriano.

Indichiamo con z^H_CH il valore della soluzione che si ottiene applicando l’euristica di Christofides.

Esempio

1 2

3

4

5

6 7

11 10 9

8

Tour euleriano (1,2,3,6,5,4,9,8,10,11,7,8,5,3,1) Nodi di grado dispari

Tour hamiltoniano (1,2,3,6,5,4,9,8,10,11,7,8,5,3,1) Matching perfetto

L’algoritmo di Christofides per il TSP è 3/2-approssimato.

Dimostrazione:

1. z* > z_TREE (1-albero è un rilassamento per TSP)

Siano {t₁, t₂, ..., t_2k} i vertici di grado dispari del minimo albero ricoprente etichettati nell’ordine in cui si incontrano nel ciclo hamiltoniano ottimo.

Esempio:

T* = {1, 2, 3, 4, 5, 6}

Min albero ricoprente in rosso {t₁, t₂, ..., t_2k} = {1, 3, 5, 6}

Proprietà

1

2 3

4

6 5

Dimostrazione

Sia C il ciclo formato dai vertici {t₁, t₂, ..., t_2k} e z(C) il suo costo.

Si ha che:

1. C è l’unione di 2 matching perfetti

{t₁t₂, t₃t₄, ... t_2k-1t_2k} ∪ {t₂t₃, t₄t₅, ... t_2kt₁}

e quindi z(C) > 2z_M, con z_M valore del matching perfetto di costo minimo.

2. z(C) < z* per la disuguaglianza triangolare. Difatti ognuno degli archi di C ha un costo minore o uguale al corrispondente sottocammino in T.

Pertanto, z* > z(C) > 2 z_M, ovvero z_M < z*/2.

Quindi:

z^H_CH < z_TREE + z_M < z* + z*/2 < 3/2 z*

Il problema della bisaccia

Avete a disposizione un budget b per gli investimenti dell’anno 2008.

Ad ogni progetto è associato - un costo a_j (> 0)

- un guadagno atteso c_j (>0).

Problema: Scegliere l’insieme di progetti in modo che sia massimizzato il guadagno atteso senza eccedere il budget b.

Se ogni progetto può essere attivato non solo per intero ma anche in parte si parla di knapsack continuo.

Il knapsack continuo

Consideriamo il seguente problema

1 per

1 0

(KRL)

st

max

1

1

, ..., n j

x

b x

a

x c

j n

j j j

n

j j j

=

≤

≤

∑

∑

=

=

KRL è un rilassamento del problema di knapsack 0-1.

Infatti, la collezione degli insiemi ammissibili del problema di knapsack 0-1 è contenuta nella regione ammissibile del problema di knapsack continuo.

Il knapsack continuo

Come si risolve il problema di knapsack continuo?

Essendo formulato come problema di Programmazione Lineare, si può risolvere utilizzando il metodo del simplesso.

In alternativa: Supponiamo di riordinare gli elementi della bisaccia in modo che:

n n

a c a

c a

c ≥ ≥ ... ≥

2 2 1

1

∑

=

>

h

j

j b

a e sia h l’indice minimo per cui 1

La soluzione

è ottima per (KLR).

0 ,...,

0 ,

, 1 ,...,

1 ,

1 _{2 1 1}

1 = x = x_h− = x_h = f x_h+ = x_n = x

h h

j

j

a a b

f











 −

=

∑

= 1

1

con

Dimostrazione

Supponiamo, senza perdita di generalità, che gli elementi del problema soddisfino

e sia x_LP = (x₁, …, x_n) la soluzione ottenuta con la formula precedente. Consideriamo una soluzione x’ ottima, diversa da x_LP. Ora, x’ differisce da x_LP per almeno un elemento x’_k con k > h.

Infatti, se x’ fosse diversa da x_LP soltanto perché x’_h= 0, allora x’

non sarebbe ottima. Ciò significa che esiste un indice i < h tale che x’_i < 1 e un indice k > h tale che x’_k > 0.

Sia

Per costruzione, d > 0. Consideriamo la soluzione:

n n

a c a

c a

c > > ...>

2 2 1

1

{ ' , (1 )}

min a_kx _k a_i x_i

d = −

> > >

Dimostrazione

che si ottiene da x’ sostituendo x’_i e x’_k con:

è ammissibile. Infatti:

Inoltre, . Infatti:

Ma, allora, la soluzione x’ non è ottima (contraddizione).

) ' ,..., ,..,

,..., '

, '

(x₁ x ₂ x_i x_k x _n x =

k k

k a

x d x = ' −

i i

i a

x d x = ' + x

a b d a a

d x a

a x

a

k n k

j

i i j

j n

j j j =

∑

∑

' cx x

c >

∑

∑

∑







 −

+

= ⁿ

j j j

n j

k k i

i j

j n

j j j c x

a c a

d c x

c x

c 1 1

1 ' '

<

Bound primale per il knapsack

Il seguente algoritmo, applicato agli elementi della bisaccia riordinati secondo il criterio

restituisce, invece una soluzione ammissibile per il problema di knapsack:

Algorithm Greedy_knapsack () d = 0; z = 0;

for (j = 1; j < n; j ++) { if (d + a_j < b) then

x_j = 1;

d = d + a_j; z = z + c_j; else x_j = 0;

}

return z;

n n

a c a

c a

c ≥ ≥ ... ≥

2 2 1

1

Ricapitolando

Abbiamo definito per il knapsack 0-1 un upper bound con le seguenti proprietà:

1. L’upper bound è “continuo”, nel senso che si ottiene dalla soluzione di un problema di Programmazione Lineare e non da un problema di OC.

2. L’upper bound può essere calcolato con un algoritmo più efficiente rispetto al metodo del simplesso e polinomiale.

Domanda: Può essere generalizzata questa tecnica di rilassamento?

Sostituendo la “stipula” x ∈ {0, 1} con il vincolo 0 < x < 1 di una formulazione di un problema di PL-{0,1}, si ottiene sempre un rilassamento denominato Rilassamento Lineare.

Dualità

Definizione: Due problemi di ottimizzazione z = max {f(x) : x ∈X}

w = min {g(y) : y ∈Y }

formano una coppia duale “debole” se f(x) < g(y) per ogni x ∈X e y

∈Y.

Se z = w si dice che formano una coppia duale “forte”.

Vantaggio fondamentale rispetto al rilassamento:

Per ottenere un bound attraverso il rilassamento, il problema rilassato va risolto all’ottimo. Invece, per una coppia duale ogni soluzione ammissibile y ∈Y (x ∈X) è un upper (lower) bound per z (w).

Esempi

1. Il problema di trovare un matching di massima cardinalità e quello di trovare un node cover di minima cardinalità formano una coppia duale debole per ogni grafo G.

2. Il problema di trovare un insieme stabile di massima cardinalità e quello di trovare un edge cover di minima cardinalità formano una coppia duale debole per ogni grafo G.

Entrambe queste coppie di problemi godono della dualità forte se G è bipartito (Teorema di Konig e Teorema di Gallai).

Formulazioni

Consideriamo il seguente problema di Knapsack 0-1 max (5x₁ + 2x₂)

st

3x₁ + 4x₂ < 6 x ∈ {0,1}²

Insiemi ammissibili

F = {(0, 0), (0, 1), (1, 0)}

Rappresentiamo sul piano gli insiemi ammissibili.

Insiemi ammissibili

x₁ x₂

(0, 0) (0, 1)

(1, 0)

(1, 1)

Formulazione

Un poliedro P è una formulazione di un problema di OC se e solo se P ∩ {0,1}ⁿ = F

x₁ x₂

Il rilassamento lineare …

Il problema di knapsack 0-1

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

x₁ < 1 x₂ < 1

x₁ > 0

x₂ > 0

… è un poliedro …

3x₁ + 4x₂ < 6

x₁ x₂

… ovvero, è una formulazione

x₁ x₂

Gerarchia di formulazioni

Quando una formulazione è “migliore” di un’altra?

Definizione: Se un poliedro P₁, formulazione di F, è contenuto in P₂, formulazione di F, diciamo che P₁ è migliore di P₂.

In generale

P₁ ⊆ P₂ ⊆ P₃ …

Esiste una formulazione “ideale”?

Formulazione ideale

“Geometricamente” la formulazione ideale coincide con il più piccolo poliedro contenente F.

Come si ottiene la formulazione ideale?

x₁ x₂

Proprietà

Osservazione: Ogni vertice del poliedro associato alla

“formulazione ideale” è in corrispondenza biunivoca con un insieme ammissibile.

Definizione: Dati due vettori x₁ e x₂ di Rⁿ si definisce combinazione convessa il vettore

y = λx₁ + (1 – λ) x₂ con λ ∈ [0, 1]

Esempio:

x₁

x₂ y

Involucro convesso

Definizione: L’insieme di tutte le possibili combinazioni convesse di un insieme di vettori X di Rⁿ prende il nome di involucro convesso e si indica con conv(X).

Osservazione: conv(X) è un poliedro.

Pertanto, la formulazione ideale di F è conv (F).

Calcolo di conv ( F ₎

In linea di principio …

Dati gli insiemi ammissibili

F = {(0, 0), (0, 1), (1, 0)}

y ∈ conv(F) se e solo se si può esprimere come

0 ,

,

1

0 1 1

0 0

0

3 2

1

3 2

1

3 2

1 2

1

≥

= +

+



 

 + 



 

 + 



 



= 









λ λ

λ

λ λ

λ

λ λ

y

λ

y

… a questo punto

Attenzione: questo sistema è nello spazio R^n+m, se m sono gli insiemi ammissibili.

Quindi per ottenere la formulazione ideale è necessario

“proiettare” il sistema nello spazio Rⁿ.

A questo scopo è possibile utilizzare l’algoritmo di Fourier- Motzkin che consente di “eliminare” le variabili λ.

Punto della situazione

Dato un problema di OC

1. Elenco tutti gli insiemi ammissibili.

2. Rappresento gli insiemi ammissibili come vettori a componenti in {0,1}.

3. Scrivo l’involucro convesso applicando la definizione.

4. Con l’algoritmo di Fourier-Motzkin elimino i coefficienti della combinazione convessa e ottengo una formulazione ideale nello spazio Rⁿ.

5. Applico il metodo del simplesso e trovo la soluzione ottima.

È efficiente questo algoritmo?

Efficienza del calcolo di conv(F)

Problemi del precedente algoritmo

1. Gli insiemi ammissibili sono tipicamente in numero esponenziale.

2. L’algoritmo di Fourier-Motzkin non ha complessità polinomiale.

Però sappiamo che una formulazione ideale esiste sempre e quindi

1. Caso MOLTO fortunato: abbiamo una formulazione che è proprio la formulazione ideale.

2. Tentiamo di approssimare la formulazione ideale costruendo una gerarchia di formulazioni a partire da una formulazione iniziale.

Gerarchia di formulazioni

Quando una formulazione è “migliore” di un’altra?

Definizione: Se un poliedro P₁, formulazione di F, è contenuto in P₂, formulazione di F, diciamo che P₁ è migliore di P₂.

In generale, una gerarchia di formulazioni è costituita da un insieme di poliedri P₁ ⊆ P₂ ⊆ P₃ …

Esempio

Consideriamo un problema di knapsack con il vincolo che l’oggetto k può essere scelto se e solo se nella bisaccia sono stati scelti gli oggetti i e j.

Formulazione 1. Formulazione 2.

n j

k

i k

x

x x

x x

b ax

x c

} 1 , 0 { st

max ^T

∈

≤

≤

≤

n

j i

k

x

x x

x

b ax

x c

} 1 , 0 { 2

st

max ^T

∈

+

≤

≤

Esempio (II)

Il rilassamento lineare della Formulazione 1 è migliore di quello della Formulazione 2.

Infatti, il vincolo

è implicato dai vincoli

j k

i k

x x

x x

≤

≤

j i

k x x

x ≤ +

2

Quindi, P₁ ^⊆ P_2.

Formulazione ideale

La formulazione del problema di knapsack NON è una formulazione ideale.

Domanda: Esistono casi “fortunati” in cui la formulazione coincide con la formulazione ideale?

E’ possibile “caratterizzare” le formulazioni ideali in modo da riconoscerle in tempo polinomiale?

Il caso “fortunato”

Consideriamo il seguente problema di PL in forma standard, in cui A è una matrice intera e b è un vettore intero:

min c^Tx Ax = b

x > 0 con rg (A) = m < n.

Se il problema ammette soluzione ottima finita, allora il metodo del simplesso restituisce la soluzione ottima in corrispondenza di una SBA del tipo:











=







=

0

-1

* B b

x x x

N B

Il caso “fortunato” (II)

Osservazione: Se la base ottima B ha determinante det(B )= + 1, allora RL ha una soluzione intera.

Infatti:

B^–1 = B^a/det(B), dove B^a è la matrice aggiunta. Gli elementi di B^a sono tutti prodotti di termini di B.

Pertanto B^a è una matrice intera e, poiché det(B)=+1, B^–1 è ancora intera.

Pertanto la soluzione di base x_B = B^–1b è intera per ogni intero b.

Matrici unimodulari

Definizione: Una matrice A intera m × n (m < n) si dice unimodulare se ogni sua sottomatrice B di dimensioni m × m ha det(B) = {-1, 0, +1}.

Dall’osservazione precedente si ottiene il seguente risultato:

Teorema: Se A è una matrice unimodulare e b è un vettore intero, il poliedro P = {Ax = b, x > 0} è intero.

Matrici totalmente unimodulari

min c^Tx

Ax ≥ b (P )

x > 0

Per portare questo problema in forma standard bisogna inserire le variabili di slack y:

min c^Tx

Ax –I_{y = b (P’)}

x, y > 0

Consideriamo ora il rilassamento lineare di una formulazione di PL-{0,1}. In generale, sarà del tipo:

Matrici totalmente unimodulari

Definizione: Una matrice A si dice TOTALMENTE UNIMODULARE (TU) se ogni sottomatrice quadrata di A ha determinante {0, +1, -1}.

Proprietà delle matrici TU

Una matrice A è TU se e solo se

i) la matrice trasposta A^T è TU.

ii) la matrice (A, I_{) è TU.}

Teorema

Teorema (Hoffman-Kruskal [1956]):

Sia A una matrice intera. Il poliedro P definito da Ax ≥ b, x ≥ 0 è intero per ogni vettore intero b se e solo se A è TU.

Attenzione: Il teorema non vale se P = {x ∈ Rⁿ; Ax = b}.

Infatti, in questo caso P può essere intero ma A può non essere TU.

Condizioni per la TU

Osservazione: Se A è TU, allora a_ij ∈{-1, 0, 1}.

Teorema: A è TU se i) a_ij∈{-1, 0, 1}

ii) Ogni colonna ha al più due coefficienti non nulli

iii) Esiste una partizione (M₁, M₂) dell’insieme delle righe M tale che ogni colonna j contenente due coefficienti non nulli soddisfa

∑

∑

⁼

2

1 i M ij

M

i

a

a

Osservazione:

- se la colonna j contiene due elementi a_ij ≠ 0 e a_kj ≠ 0 dello stesso segno allora i∈ M₁ e k∈ M₂.

- se la colonna j contiene due elementi a_ij ≠ 0 e a_kj ≠ 0 di segno opposto allora i, k ∈ M₁ oppure i,k ∈ M₂.

Dimostrazione

Dobbiamo dimostrare che ogni sottomatrice quadrata B di A ha det(B)∈{–1, 0, 1}.

Procediamo per induzione:

Se B è una sottomatrice 1×1, banalmente det(B)∈{–1,0,1}.

Supponiamo ora che la tesi valga per ogni sottomatrice di A di dimensioni (n – 1)×(n – 1) e consideriamo una sottomatrice B n×n.

• Se B contiene una colonna nulla, det(B) = 0.

• Se ogni colonna di B contiene due elementi ≠ 0, dall’ipotesi si ottiene

Questo implica che det(B) = 0.

∑

∑

⁼

2

1 i M ij

M

i

a

a

• Se B contiene una colonna con un unico elemento diverso da zero, allora det(B) = +det(B’), dove B’ è di ordine (n – 1)×(n – 1).

Pertanto, dall’ipotesi induttiva, det(B)∈{–1,0,1}.

Dimostrazione