Ottimizzazione Combinatoria 2 - uniroma1.itsassano/Slides/OCO2_2016/OCO2_Network_L… · uz + l zv...

1

Il problema del Network Loading

Ottimizzazione Combinatoria 2

Prof. Antonio Sassano

Dipartimento di Informatica, Automatica e Gestionale “Antonio Ruberti”

Università di Roma “Sapienza”

A.A. 2016

Il problema del network loading• Progettare una rete consiste nel determinare quali «connessioni tra

oggetti» attivare e quale capacità assegnare a tali connessioni.

• Assunzione: grafo G(N, A) completo (è possibile attivare una connessione

fra ogni coppia di nodi), senza loop.

• Assunzione: per ogni coppia di nodi distinti u, v N, esiste una

commodity k=uv = {u,v,ruv} (eventualmente con domanda ruv nulla).

• Assunzione: 𝒓 ≠ 𝟎|𝑨| (la domanda è non-nulla per qualche coppia di nodi).

• I flussi tra una coppia di nodi u, v N sono indistinguibili (unico bene).

𝒅𝒖𝒗 =

𝟎−𝒓𝒖𝒗⋮𝒓𝒖𝒗𝟎

𝒖

𝒗𝒖 𝒗

𝒅𝒗𝒖 =

𝟎𝒓𝒗𝒖⋮

−𝒓𝒗𝒖𝟎

𝒖

𝒗

Il problema del network loading (..)

•Sono noti i costi di installazione wuv 0 per ogni unità di

capacità aggiuntiva sull’arco uvA.

• Il problema è descritto dalla tripla (N,r,w)

• Le capacità installabili 𝒚𝒖𝒗 hanno valori interi 𝒚𝒖𝒗 ∈ 𝒁+(o sono disponibili in quantità discrete 𝒒𝟏, 𝒒𝟐, … , 𝒒𝒕 )

Aggiungere mezzi di trasporto (bus, vagoni, aerei)

Aumentare la capacità di un collegamento (𝒒𝟏=64K,

𝒒𝟐=128K, 𝒒𝟑=256K, …)

Semimetriche e cono metrico

Semimetriche

• Grafo orientato completo G(N,A) con lunghezze sugli archi l 0|A|

Semimetrica

Luv(l) Lunghezza cammino minimo (rispetto a l) da u a v.

(ovvero: la lunghezza luv di uv è pari alla lunghezza del cammino minimo

da u a v usando l come vettore delle lunghezze degli archi)

3

1

2

2

23

3

1

2

Def: l 0|A| è una semimetrica se e solo se luv = Luv(l) per ogni uv A

3

1

2

2

23

3

1

5

Non Semimetrica

• Lunghezza cammino minimo da 2 a 1 = 4

• l21 = 5 > L21 = 4

Semimetriche e disuguaglianza triangolare

luv

u

v

luz z

lzv

• Teorema 1. l 0|A| è una semimetrica se e solo se,

per ogni tripla di nodi distinti u, v, z, si ha che

luv luz + lzv (disuguaglianza triangolare)

Solo Se (necessità).

Dim. (assurdo).

luv luz + lzv per ogni tripla di nodi distinti u, v, z

luv > luz + lzv

l 0|A| semimetrica

l 0|A| semimetrica luv = Luv(l)

l(P) = luz + lzv < luv = Luv(l)

contraddizione

Sia l semimetrica ma esistono tre nodi distinti u, v, z per cui

lunghezza di P < lunghezza del cammino minimo da u a v,

Consideriamo il cammino P = {u, uz, z, zv, v}


Se (sufficienza).

Soddisfa disuguaglianza triangolare l è una semimetrica

Dim. (per assurdo). Supponiamo l non sia una semimetrica

Esistono archi ij per cui lij > Lij(l). Sia E l’insieme di questi archi.

• Sia uv E, tale che il cammino minimo P*uv da u a v (rispetto a l)

contenga il minor numero di archi

(per ogni altro arco ij E ogni cammino minimo P*ij da i a j ha un

numero di archi non inferiore a quello di P*uv )

u

v

P*uv

luv > Luv(l) = l (P*uv)

luv

luv > l (P*uv)Luv(l) = l (P*

uv)

ogni xy per cui un cammino minimo P*xy contiene meno archi di P*

uv

non appartiene ad E (ovvero lxy = Lxy(l))

l R|A| , l > 0|A|


Se (sufficienza).

luv > Luv(l) = l (P*uv)

u

v

P*uv

luv

luv > l (P*uv)

Sia zv l’ultimo arco su P*uv

u

v

P*uz

luv

z

lzv

P*uz sottocammino di P*

uv da u a z

P*uz cammino minimo da u a z

luv

u

v

P*uz

luzz

lzvP*

uz contiene meno archi di P*uv

luz = l(P*uz)

Da luv luz + lzv

contraddizioneluv luz + lzv = l(P*uz) + lzv = l(P*

uv)

l(P*uv) = l(P*

uz) + lzv

P*uv contiene almeno due archi, altrimenti P*

uv

coincide con (u,v) e l (P*uv) = luv

Il cono metrico

In particolare METN 𝑹 𝑨 è l’insieme di soluzioni (vettori) l 𝑹 𝑨

del sistema di disequazioni lineari:

luv luz + lzv luv - luz - lzv 0 u, v, z N, u v z

luv 0 uv A

ed è detto cono metrico (METN )

Proprietà di 𝑴𝑬𝑻𝑵: Per ogni ҧ𝒍 ∈ 𝑴𝑬𝑻𝑵 e ogni k 0 anche 𝒌 ҧ𝒍 ∈ 𝑴𝑬𝑻𝑵

METN

origine

Le semimetriche l R|A| , l ≥ 0|A| definiscono il cono poliedrale METN

Dx = 0p , Ax < 0m

soluzioni di un sistema di equazioni e/o disequazioni lineari omogenee

La semimetrica dei cammini minimi

Semimetrica dei

cammini minimi

• Preso un grafo H(N,A) fortemente connesso (esiste un cammino

orientato da ogni nodo a ogni altro nodo) con lunghezza uv , uv A

• Per ogni u,v N, u v definisco luv = Luv() (lunghezza cammino

minimo P*uv da u a v calcolato con lunghezze degli archi )

• Poiché Luv() Luz() +Lzu() (l soddisfa la disuguaglianza triangolare)

segue che l è una semimetrica

3

1

2

13

7

2

4

H(N,A)

4

4

1

3

1

2

5

1

3

5

2

4

4

6

4

46

19

u

v

z

P*uv

P*uz

P*zv

Una semimetrica 0,1: i tagli

• Dato un grafo orientato H(N,A) e un insieme di nodi W N, definiamo

taglio (associato a W) l’insieme +(W) = {(u,v)A: u W, v N-W}

• y {0,1}A vettore d’incidenza di un taglio

y semimetrica

H(N,A)

W

3

1

2

4• Per assurdo, supponiamo y non sia una semimetrica

Esistono tre archi (u,v), (u,z), (z,v) tali che yuv > yuz + yzv

yuv = 1, yuz = yzv = 0

u W, v N-Wyuv = 1 z Wyuz = 0

v Wyzv = 0 contraddizione.

.. dalle slides di Ottimizzazione Combinatoria I

Tre proprietà utili

• Grafo orientato G(N,A), con lunghezze degli archi uvR+ , uv A

lv – lu uv per ogni uv A

ls = 0

• Fissato s N, consideriamo l’insieme di soluzioni l ∈ 𝑹+𝑵

del sistema di

vincoli:

• Proprietà 1: lv = Lsv() è una soluzione ammissibile, per ogni v N.

• Proprietà 2: l ammissibile lv Lsv() per ogni v N.

• Proprietà 3: L() è una semimetrica (la semimetrica dei cammini minimi):

Luv() Luz() + Lzv() per ogni tripla di nodi distinti u,v,z N.

Vincoli del problema

duale cammino minimo

Dimostrata nel Teorema della Condizione di Illimitatezza (slide precedente)

𝑳𝒔𝒗 𝝁 = 𝝁𝒔𝒖𝟏 + 𝝁𝒖𝟏𝒖𝟐 + 𝝁𝒖𝟐𝒖𝟑 +⋯+ 𝝁𝒖𝒑𝒗 ≥

≥ l𝒖𝟏

– l𝒔 + l𝒖𝟐

– l𝒖𝟏

+ l𝒖𝟑

– l𝒖𝟐

+⋯+ l𝒗– l𝒖𝒑

= l𝒗

Il problema del network loading

Network Loading: formulazione naturale

G(N, A) grafo orientato completo (senza loop)

A uvZy

NA, z uvx

A uvyx

z u,NN, uzrxx

ywmin

uv

z

uv

uv

Nz

z

uv

zu

)u(Nv

z

uv

)u(Nv

z

vu

Auv

uvuv

0

Vincoli di capacità

Vincoli di domanda

capacità installabile in quantità discrete 𝒒𝟏, … , 𝒒𝒕 su uv A

Rx z

uv quantità di flusso originato da z N che transita sull’arco uv A

variabili

Zyuv

domanda commodity zu, per ogni z,u N, z uRx z

uv

costo unitario installazione capacità su uv, per ogni uv AZyuv

𝒚𝒖𝒗 =

𝒊=𝟏

𝒕

𝒛𝒖𝒗𝒊 𝒒𝒊

𝒊=𝟏

𝒕

𝒛𝒖𝒗𝒊 = 𝟏

𝒛𝒖𝒗𝒊 ∈ 𝟎, 𝟏

sostituendo 𝒚𝒖𝒗 con:

abbiamo un

Problema di PL01

Il problema di ammissibilità (singola commodity)• Dato un problema (N,r,w) e un vettore di capacità c𝑹 𝑨 , esiste una

condizione per decidere se le capacità consentono un flusso

multicommodity che soddisfa la domanda?

Si può estendere al flusso multicommodity ?

Caso singola «commodity»: Teorema Massimo flusso/ Minimo Taglio

𝜹+ 𝑺, 𝑻 = 𝒖𝒗 ∈ 𝑨: 𝒖 ∈ 𝑺, 𝒗 ∈ 𝑻 taglio

𝒄 𝑺, 𝑻 =

𝒖𝒗∈𝜹+(𝑺,𝑻)

𝒄𝒖𝒗 capacità del taglio

𝒄 𝑺, 𝑻 ≥ 𝒓𝒔𝒕 ∀ taglio s−t 𝜹+ 𝑺, 𝑻 𝐬 ∈ 𝑺, 𝒕 ∈ 𝑻

Domanda 𝒓𝒔𝒕 soddisfatta se e solo se:

3

1

3 3

3

2

1s

1

2 3

4

t

1

𝑺

𝑻𝒅 =

−𝑟𝑠𝑡𝑟𝑠𝑡0000

𝑠𝑡1234

Ammissibilità per il Flusso MultiCommodity

• Eppure …… il problema Multi-Commodity non ammette soluzione!

- ha capacità c 𝑺, 𝑻 = 𝟏

Ogni taglio 𝜹+ 𝑺, 𝑻 - soddisfa r 𝑺, 𝑻 ≤ 𝟏.

Nell’esempio precedente:

• Estensione “naturale” del Massimo-Flusso-Minimo-Taglio:

per ogni partizione (S,T) di N, la capacità c(S,T) del taglio 𝜹+ 𝑺, 𝑻 deve

essere almeno pari alla somma delle domande associate alle commodity che

hanno origine in S e destinazione in T («attraversano il taglio»).

𝒄 𝑺, 𝑻 ≥ r 𝑺, 𝑻 ∀ taglio 𝜹+ 𝑺, 𝑻

03

1

2

0

11

1

0

𝒄

0

0

3

1

2

10

1

0

r

𝒄 𝑺, 𝑻 = 𝒄 𝟑 , 𝟐, 𝟏 = 𝟏 𝒓 𝑺, 𝑻 = 𝒓 𝟑 , 𝟐, 𝟏 = 𝟏

domanda che «attraversa» il taglio

𝒓 𝑺, 𝑻 =

𝒖𝒗∈𝜹+(𝑺,𝑻)

𝒓𝒖𝒗

Necessario ma

non sufficiente

Massimo flusso concorrente

• * 1 c sufficiente

• * < 1 c insufficiente

• r 0, c 0 (MCF) è ammissibile (x = 0, = 0 sol. ammissibile)

0

0

NA, z uvx

A uvcx

u z,NN, uzrxx

max

z

uv

Nz

z

uv

zu

)u(Nv

z

uv

)u(Nv

z

vu

uv

(MCF)

• Problema del Massimo Flusso Concorrente (MCF).

• Stabilire quale frazione della domanda r (non nulla) può essere

soddisfatta con un dato vettore di capacità c ≥ 0|A|

• c finito, r non nullo MCF è limitato ammette sol. ottima (* x*)

Duale del massimo flusso concorrente

(MCF) ha sol. ottima (D) ha sol. ottima di uguale valore

• Variabile duale uv per ogni uv A

uv

• Variabile duale lzu per ogni z N, u N (anche z = u) (fissa luu = 0)

lzu

xzuv

𝒍𝒛𝒖

𝒍𝒛𝒗

𝝁𝒖𝒗

t = v

𝒕∈𝑵+ 𝒖

𝒙𝒖𝒕𝒛 −

𝒕∈𝑵− 𝒖

𝒙𝒕𝒖𝒛 + 𝜶𝒓𝒛𝒖 ≤ 𝟎

𝒕∈𝑵+ 𝒗

𝒙𝒗𝒕𝒛 −

𝒕∈𝑵− 𝒗

𝒙𝒕𝒗𝒛 + 𝜶𝒓𝒛𝒗 ≤ 𝟎

𝒛∈𝑵

𝒙𝒖𝒗𝒛 ≤ 𝒄𝒖𝒗

t = u

𝒖 ≠ 𝒗 ≠ 𝒛 ∈ 𝑵

𝒎𝒂𝒙 𝜶

𝒕∈𝑵+(𝒖)


𝒕∈𝑵−(𝒖)

𝒙𝒕𝒖𝒛 + 𝜶𝒓𝒛𝒖 ≤ 𝟎 𝒛 ∈ 𝑵, 𝒖 ∈ 𝑵, 𝒛 ≠ 𝒖

𝒛∈𝑵

𝒙𝒖𝒗𝒛 ≤𝒄𝒖𝒗 𝒖𝒗 ∈ 𝑨

𝒙𝒖𝒗𝒛 ≥ 𝟎 𝒖𝒗 ∈ 𝑨, 𝒛 ∈ 𝑵𝜶 ≥ 𝟎

(MCF)

𝒎𝒊𝒏

𝒛∈𝑵

𝒄𝒖𝒗𝝁𝒖𝒗

𝝁𝒖𝒗 − 𝒍𝒛𝒗 + 𝒍𝒛𝒖 ≥ 𝟎 𝒖 ≠ 𝒗 ≠ 𝒛 ∈ 𝑵 (𝒊)

𝒛∈𝑵

𝒖∈𝑵

𝒓𝒛𝒖 𝒍𝒛𝒖 ≥ 𝟏 (𝒊𝒊)

𝒍𝒛𝒖 ≥ 𝟎 𝒛 ∈ 𝑵,𝒖 ∈ 𝑵 (𝒊𝒊𝒊)𝒍𝒖𝒖 = 𝟎 𝒖 ∈ 𝑵 (𝒊𝒗)𝝁𝒖𝒗 ≥ 𝟎 𝒖𝒗 ∈ 𝑨 (𝒗)

(D)

𝒙𝒖𝒗𝒛 tre volte nei vincoli primali

Duale del massimo flusso concorrente

*

Auv

*

uvuvc

Sol. Ottima di (D) : (* l*)

1Auv

*

uvuvc c sufficiente

1Auv

*

uvuvc c insufficiente

Sol. Ottima (* x*)

• La soluzione ottima di (D) ha valore * (teorema forte della dualità)

𝒎𝒂𝒙 𝜶

𝒕∈𝑵+(𝒖)


𝒕∈𝑵−(𝒖)

𝒙𝒕𝒖𝒛 + 𝜶𝒓𝒛𝒖 ≤ 𝟎 𝒛 ∈ 𝑵, 𝒖 ∈ 𝑵, 𝒛 ≠ 𝒖

𝒛∈𝑵

𝒙𝒖𝒗𝒛 ≤𝒄𝒖𝒗 𝒖𝒗 ∈ 𝑨

𝒙𝒖𝒗𝒛 ≥ 𝟎 𝒖𝒗 ∈ 𝑨, 𝒛 ∈ 𝑵𝜶 ≥ 𝟎

(MCF)

* 1 c sufficiente a servire

* < 1 c insufficiente a servire

𝒎𝒊𝒏

𝒛∈𝑵

𝒄𝒖𝒗𝝁𝒖𝒗

𝝁𝒖𝒗 − 𝒍𝒛𝒗 + 𝒍𝒛𝒖 ≥ 𝟎 𝒖 ≠ 𝒗 ≠ 𝒛 ∈ 𝑵 (𝒊)

𝒛∈𝑵

𝒖∈𝑵


𝒍𝒛𝒖 ≥ 𝟎 𝒛 ∈ 𝑵,𝒖 ∈ 𝑵 (𝒊𝒊𝒊)𝒍𝒖𝒖 = 𝟎 𝒖 ∈ 𝑵 (𝒊𝒗)𝝁𝒖𝒗 ≥ 𝟎 𝒖𝒗 ∈ 𝑨 (𝒗)

(D)

Natura del vincolo duale (i)

• Possiamo riscrivere i vincoli duali (i) raggruppandoli per la stessa z

lzv – lzu uv per ogni uv A, z N• Riordiniamo i vincoli duali di tipo (i)

• Consideriamo il blocco per z=k, aggiungendo il corrispondente vincolo (iv)

• Le variabili tipo lku appaiono solo nel blocco di vincoli associati a z = k

lkv – lku uv per ogni uv A (z = k)

lkk = 0

• Stessa forma dei vincoli del duale del cammino minimo, con nodo

k (invece di s) come nodo iniziale.

Se rinomino lkv = yv per ogni vN

yv – yu uv per ogni uv A

yk = 0

l1v – l1u uv per ogni uv A (z = 1)

l2v – l2u uv per ogni uv A (z = 2)

lnv – lnu uv per ogni uv A (z = n)

⋮

Estensione proprietà duale del cammino minimo

• Grafo orientato G(N,A), con lunghezze degli archi uvR+ , uv A

Fissato z N, consideriamo il sottosistema con k = z :

• Proprietà 1: yv = Lzv() è una soluzione ammissibile, per ogni v N.

yv – yu uv per ogni uv A

yz = 0 Vincoli del duale del cammino minimo

• Per il blocco di vincoli duali con z fissato abbiamo (lzv = yv per ogni vN)

• lzv – lzu uv per ogni uv A

lzz = 0

• Proprietà 1: lzv = Lzv() è una soluzione ammissibile, per ogni v N.

• Proprietà 2: y ammissibile yv Lzv() per ogni v N.

• Proprietà 2: l ammissibile lzv Lzv() per ogni v N.

Dunque:

Proprietà soluzione duale

• Lemma 2. Sia ( , l ) ottima per (D). La soluzione ( , l* ) , con

l*zu = Lzu( ) per ogni z N, uN, è ottima per (D)

(per ogni z, l*zu è pari alla lunghezza del cammino minimo da z a u

quando le lunghezze degli archi sono )

• Proprietà 1

• Per ogni z : 0 Lzu( ) 0 per ogni uN, e Lzz( ) = 0

( , l*) soddisfa (iii), (iv) e (v)

Lzu( ) soddisfa i vincoli (i), per ogni z:

Lzv( ) – Lzu( ) uv per ogni uv A

( , l* ) soddisfa i vincoli (i)

1. Ammissibilità di ( , l* )

Vincoli (i) 𝝁𝒖𝒗 − 𝒍𝒛𝒗 + 𝒍𝒛𝒖 ≥ 𝟎 𝒖 ≠ 𝒗 ≠ 𝒛 ∈ 𝑵 (𝒊)

Vincoli (iii), (iv), (v) 𝒍𝒛𝒖 ≥ 𝟎 𝒛 ∈ 𝑵,𝒖 ∈ 𝑵 (𝒊𝒊𝒊)𝒍𝒖𝒖 = 𝟎 𝒖 ∈ 𝑵 (𝒊𝒗)𝝁𝒖𝒗 ≥ 𝟎 𝒖𝒗 ∈ 𝑨 (𝒗)

Proprietà della soluzione duale

lzv – lzu uv per ogni uv A

lzz = 0

( , l ) ammissibile per (D) l soddisfa (i) per ogni z:

• Proprietà 2 lzu Lzu( ) = l*zu per ogni u N.

( , l*) soddisfa (ii)

2. Ottimalità di ( , l* )

• La funzione obiettivo di (D) dipende solo dalle

variabili che non sono mutate rispetto a ( , l )

Vincoli (ii)

𝒛∈𝑵

𝒖∈𝑵


r 0

𝒛∈𝑵

𝒖∈𝑵

𝒓𝒛𝒖 𝒍𝒛𝒖∗ ≥

𝒛∈𝑵

𝒖∈𝑵

𝒓𝒛𝒖 𝒍𝒛𝒖′ ≥ 𝟏


• Lemma 3. Sia ( , l*) ottima per (D), con l*zu = Lzu( ) per ogni z,u N.

Allora (*, l*) , con *uv = l*

uv per ogni uv A, è ottima per (D).

Se z = u

l*zv – l*

zu

uv uvA, zN (Vincolo (i))

l*uv

uv uvA

( , l*) ammissibile per (D)

*uv

uv uvA

c 0

Auv

'

uvuv

Auv

*

uvuv cc (*, l*) ottima per (D)

1. Ottimalità di (*, l*)

l*uu = 0


Lzv( ) Lzu( )+Luv( )Proprietà 3 l*zv l*

zu+ l*uv

l*uv- l*

zv+ l*zu 0 *

uv- l*zv+ l*

zu 0

(*, l*) ammissibile per (D)

2. Ammissibilità di (*, l*)

l* 0 * 0 Vincolo (v)

Vincoli (ii, iii, iv) dipendono solo da l*

soddisfatti per ipotesi

z

v

u

Lzv

Lzu

Luv

𝒛∈𝑵

𝒖∈𝑵

𝒓𝒛𝒖 𝒍𝒛𝒖∗ ≥ 𝟏 (𝒊𝒊)

𝒍𝒛𝒖∗ ≥ 𝟎 𝒛 ∈ 𝑵,𝒖 ∈ 𝑵 (𝒊𝒊𝒊)𝒍𝒖𝒖∗ = 𝟎 𝒖 ∈ 𝑵 (𝒊𝒗)𝝁𝒛𝒖∗ ≥ 𝟎 𝒖𝒗 ∈ 𝑨 (𝒗)

Vincolo (i) 𝝁𝒛𝒖∗ − 𝒍𝒛𝒗

∗ + 𝒍𝒛𝒖∗ ≥ 𝟎 𝒖 ≠ 𝒗 ≠ 𝒛 ∈ 𝑵

Proiezione

• Possiamo quindi effettuare la sostituzione (rimuovendo anche le variabili

luu che sono fissate a 0 per ogni u).

• La forma equivalente di problema duale, nelle sole variabili

A uv

r

zvu,Nz,v, u

cmin

uv

Auv

uvuv

zuzvuv

Auv

uvuv

0

1

0

(D)

Il valore ottimo di (D) è uguale al valore ottimo di (D)

è una semimetrica !!

• Il lemma precedente assicura che, nel risolvere il problema (D) all’ottimo,

possiamo limitarci a considerare soluzioni per le quali

uv = luv per ogni uv A


Poniamo *uv = uv/K per ogni uv A

K ≥ 1

Auv

uvuv

Auv

uvuv

Auv

uvuv

Auv

uvuv ccK

Kcc 1*

c 0, 0 0Auv

uvuvc

Lemma 4. Per ogni soluzione ammissibile 𝝁′ di (D) esiste una

soluzione ammissibile 𝝁∗ di (D) con:

(a)

𝒖𝒗∈𝑨

𝒓𝒖𝒗𝝁𝒖𝒗∗ = 𝟏

(b)

𝒖𝒗∈𝑨

𝒄𝒖𝒗𝝁𝒖𝒗∗ =

𝑢𝑣∈𝐴

𝑐𝑢𝑣𝜇𝑢𝑣′ /

𝑢𝑣∈𝐴

𝑟𝜇𝑢𝑣′ ≤

𝒖𝒗∈𝑨

𝒄𝒖𝒗𝝁𝒖𝒗′

Sia soluzione ammissibile di (D) con

𝒖𝒗∈𝑨

𝒓𝒖𝒗𝝁𝒖𝒗′ = 𝑲DIM.

( Ovvero: esiste sempre una soluzione ottima 𝝁∗ di (D) con )

𝒖𝒗∈𝑨



’ 0 * 0

11

Auv

'

uvuv

Auv

'

uvuv

Auv

*

uvuv rK

Krr

'

zu

'

zv

'

uv 0

Per ogni u,v, z N, u v z

K/)( '

zu

'

zv

'

uv 0 *

zu

*

zv

*

uv 0

*uv = ’

uv/K per ogni uv A, K ≥ 1 Abbiamo dunque:

A uv

r

zvu,Nz,v, u

uv

Auv

uvuv

zuzvuv

0

1

0

(D)

Dimostriamo ora che 𝜇∗ è ammissibile per D e soddisfa

𝒖𝒗∈𝑨


𝒖𝒗∈𝑨

𝒄𝒖𝒗𝝁𝒖𝒗∗ =

𝑢𝑣∈𝐴

𝑐𝑢𝑣𝜇𝑢𝑣′ /𝑲 ≤

𝒖𝒗∈𝑨

𝒄𝒖𝒗𝝁𝒖𝒗′

Il cono metrico “normalizzato”

(D=)

A uv

r

zvu,Nz,v, u

cmin

uv

Auv

uvuv

zuzvuv

Auv

uvuv

0

1

0

• Poiché esiste sempre una soluzione ottima che soddisfa il vincolo (i)

all’uguaglianza, possiamo definire un nuovo problema duale (D=)

ottenuto da (D) sostituendo il vincolo (i) con un vincolo di uguaglianza.

• Per i tre lemmi precedenti, il valore della soluzione ottima di (D=) è

uguale al valore della soluzione ottima di (D)

• L’insieme delle soluzioni ammissibili di (D=) indicato con METN= è

dato dall’intersezione del cono metrico METN con l’iperpiano

1Auv

uvuvr

1Auv

uvuvr

METN=

Dualità del massimo flusso concorrente

* 1 c sufficiente a servire

* < 1 c insufficiente a servire

** Auv

uvuvc

Soluzione Ottima di (D=) : *

1* Auv

uvuvc c sufficiente

1* Auv

uvuvc c insufficiente

soluzione ottima (*,x*)

A uv

r

zvu,Nz,v, u

cmin

uv

Auv

uvuv

zuzvuv

Auv

uvuv

0

1

0

(D=)

• La soluzione ottima di (D) ha valore * (dualità forte)

• La soluzione ottima di (D=) ha lo stesso valore dell’ottimo di (D)

0

0

Nz,A uvx

A uvcx

zu,NN, u zrxx

max

z

uv

uv

Nz

z

uv

zu

}u{N

z

vu

}u{N

z

uv 0vv

Il teorema “giapponese”

Il problema multicommodity flow ammette soluzione

• Teorema 5. Dato il grafo orientato completo G(N,A), con capacità c 0|A|

e domanda r 0|A| , il problema multicommodity flow ammette soluzione

se e solo se per ogni semimetrica METN= si ha:

(c – r)T 0

• * ottima e (D=) è un problema di minimizzazione:

cT 1 per ogni METN= (1)

Sottraendo rT = 1 da cT 1 abbiamo:

METN=1

Auv

uvuvr soddisfa il vincolo (rT = 1) (2)

cT - rT 0 per ogni METN=(c – r)T 0 per ogni METN=

Solo se

per ogni semimetrica METN= si ha (𝒄 − 𝒓)𝑻𝝁 ≥ 𝟎

cT* 1

Dimostrazione:

Il teorema “giapponese”

Sommando la (1) alla (2) otteniamo:

cT 1 per ogni METN=

(c – r)T 0 per ogni METN= (2)

Se Il problema ammette soluzione

METN=1

Auv

uvuvr soddisfa il vincolo (rT = 1) (1)

la soluzione ottima * di (D=) è tale che cT* 1

(c – r)T 0 per ogni METN=

Il problema ammette soluzione

Dimostrazione:

Il problema di ammissibilità

Esiste METN= tale che (c – r)T < 0

Problema inammissibile

1

0

0

0

1

0

32

31

23

21

13

12

r

0

1

1

0

0

1

32

31

23

21

13

12

c

1

1

1

0

1

1

32

31

23

21

13

12

rc

21

0

0

0

21

21

32

31

23

21

13

12

A uv

zvu

zvu

zvu

zvu

zvu

zvu

uv

0

1

)1,2,3(0

)2,1,3(0

)1,3,2(0

)3,1,2(0

)2,3,1(0

)3,2,1(0

3213

131232

232131

121323

323121

212313

313212

METN=

T111011

21

0

0

0

21

21

(c – r)T= -1/2 < 0

3

1

2

0

1/2

0

0

1/2

1/2

0

0

3

1

2

10

1

0

r

3

1

2

0

1 1

1

0

0

c

semimetrica


• Il Teorema 5 (“giapponese”) dice che un vettore di capacità c è

sufficiente a servire una domanda r se e solo se:

(c – r)T 0 per ogni METN=

• Nel problema di network loading le capacità (intere) sono variabili

decisionali yuv Z+ , per ogni uv A.

|A|

N

T

Auv

uvuv

Zy

MET μ )ry(

ywmin

0

• Problema di programmazione lineare intera nelle sole variabili y

Problema di Network Loading

• Il costo per installare un’unità di capacità sull’arco uv A è pari a wuv

• y sufficiente a servire r se e solo se (y – r)T 0 per ogni METN=

• y ammissibile se e solo se (y – r)T 0 per ogni METN=


• Problema di programmazione lineare intera: risolto con Branch&Bound

• Metodo del simplesso dinamico (generazione di vincoli)

• A ogni nodo di branching viene risolto il rilassamento lineare:

• Ingrediente principale: oracolo di separazione per NL(r)

• Difficoltà: il problema ha un vincolo per ogni METN=


Auvy

MET μ )ry(

ywmin

uv

N

T

Auv

uvuv

0

0NL(r)

Rilassamento

Lineare problema

Network Loading

|A|

N

T

Auv

uvuv

Zy

MET μ )ry(

ywmin

0

Metodo del Simplesso Dinamico

^ai x > bi

x̂POracolo di

Separazione

di P

xRn^

^x P

min cTx : xP ={x Rn: Ax b}

Risolve un problema di Programmazione Lineare:

Due ingredienti:

x* soluzione ottima

problema illimitato

nessuna soluzione (P =

Metodo del

Simplesso

min cTx

Ax bAssunzione

• Per semplicità consideriamo solo problemi non illimitati39

Definizione del

problema “core”

non illimitatoA

D0 d0

b

Oracolo di

Separazione

di P

x* P

aiTx>bi

x*P

x* ottima (in Q)

x* ottima

Nuova D e nuovo d

D d

Q=

P=

D=D0 ; d=d0

Metodo del

Simplesso

min cTx

x Q = Dx<d,

(P Q)

aiT bi

Aggiunta del vincolo violato 40

Oracolo di separazione

Oracolo di separazione per NL(r). Dato y* R|A| determina se y* NL(r)

oppure restituisce un vincolo di NL(r) violato da y* .

NL(r) = {y R|A| : (y-r)T 0 per ogni METN= , 𝒚 ≥ 𝟎 𝑨 }

• Identificare un vincolo 𝒚 ≥ 𝟎 𝑨 violato da y* è facile (ispezione diretta):

basta verificare se esiste una componente negativa di y*

• Identificazione vincolo metrico violato da y*

Trova * METN= tale che (y* -r)T * < 0

Oppure concludi che un tale * non esiste


NL(r) = {y R|A| : (y-r)T 0 per ogni METN= , 𝒚 ≥ 𝟎 𝑨 }

Dato 𝒚∗ ≥ 𝟎 𝑨

Trova * METN= tale che (y* - r)T * < 0 ( y* NL(r) )

Oppure concludi che non esiste ( y* NL(r) )

Proprietà: se 𝒚∗ ≥ 𝟎 𝑨 il problema min{ (y*-r)T : METN=}

ammette soluzione ottima * (problema non illimitato).

Dim. Per assurdo. Se problema illimitato, esiste METN=

tale che (y*-r)T < -1 rT > 1 + (y*)T

rT > 1y* , 0 (y*)T 0

contraddizione (perché METN= rT = 1)

Ovvero: poliedro dei vettori capacità che soddisfano la domanda r

ORACOLO DI SEPARAZIONE per NL(r)


A uv

r

zvu,Nz,v, u

)ry(min

uv

Auv

uvuv

zuzvuv

Auv

uvuv

*

uv

0

1

0

Dato 𝒚∗ ≥ 𝟎 𝑨

Trova * METN= tale che (y* -r)T * < 0

Oppure concludi che non esiste

Risolvi min { (y* -r)T : METN= }. Sia * la soluzione ottima

Se: (y* - r)T * < 0 restituisci il vincolo violato (y - r)T * 0

Altrimenti (y* - r)T (y* - r)T * 0 per ogni METN= e non

esiste un vincolo metrico violato da y*

Problema di separazione

vincoli semi-metrici

Esempio di Network Loading

• Primo problema core: solo vincoli di non-negatività

2

0

0

0

3

0

32

31

23

21

13

12

r3

1

2y21y12

y32

y23

y31

y13

3

1

4

2

3

2

32

31

23

21

13

12

w

Auvy

MET μ ry

yw

uv

N

T

Auv

uvuv

ogniper 0

ogniper 0)(

min

• Soluzione Ottima y* = 0|A|

Auvy

yw

uv

Auv

uvuv

ogniper 0

min

0

0

0

0

0

0

32

31

23

21

13

12

*y

• w 0 problema core non illimitato

0

0

3

1

2

20

3

0

r

Esempio di separazione

• Primo problema di separazione

A uv

r

zvuNzv u

ry

uv

Auv

uvuv

zuzvuv

Auv

uvuvuv

0

1

,,,0

)(min *

A uvuv

0

123

0

0

0

0

0

0

23min

3213

131232

232131

121323

323121

212313

313212

3213

0

0

0

0

0

0

32

31

23

21

13

12

*y

2

0

0

0

3

0

32

31

23

21

13

12

r

21

21

0

0

0

21

32

31

23

21

13

12

*

(y-r)T * 0

• Valore Soluzione Ottima = -1 < 0

• Vincolo violato:

1/2 y12 + 1/2 y31 + 1/2 y32 1

y12 + y31 + y32 2

2

0

0

0

3

0

32

31

23

21

13

12

* ry

Soluzione Ottima


• Secondo problema core

A uvuv

0

123

0

0

0

0

0

0

223min

3213

131232

232131

121323

323121

212313

313212

323113

0

0

31

0

31

31

32

31

23

21

13

12

*

Auvy

yyy

yw

uv

Auv

uvuv

ogniper 0

2

min

323112

• Soluz. Ottima

0

2

0

0

0

0

32

31

23

21

13

12

*y

3

1

2

2

• Secondo Problema di separazione

2

2

0

0

3

0

32

31

23

21

13

12

* ry

2

0

0

0

3

0

32

31

23

21

13

12

r

• Valore Sol. Ottima = -1 < 0


1/3 y12 + 1/3 y13 + 1/3 y23 1

y12 + y13 + y23 3


A uvuv

0

123

0

0

0

0

0

0

233min

3213

131232

232131

121323

323121

212313

313212

321213

21

21

0

0

0

0

32

31

23

21

13

12

*

• Terzo problema core

Auvy

yyy

yyy

yw

uv

Auv

uvuv

ogniper 0

3

2

min

231312

323112

• Soluz. Ottima

0

0

0

0

0

3

32

31

23

21

13

12

*y

3

1

2

3

• Terzo Problema di separazione

2

0

0

0

3

3

32

31

23

21

13

12

* ry

2

0

0

0

3

0

32

31

23

21

13

12

r


1/2 y31 + 1/2 y32 1

y31 + y32 2



• Quarto problema core

A uvuv

0

123

0

0

0

0

0

0

2233min

3213

131232

232131

121323

323121

212313

313212

32311213

0

0

31

0

31

0

32

31

23

21

13

12

*

Auvy

yy

yyy

yyy

yw

uv

Auv

uvuv

ogniper 0

2

3

2

min

3231

231312

323112

• Soluz. Ottima

0

2

0

0

0

3

32

31

23

21

13

12

*y

3

1

2

32

• Quarto Problema di separazione

2

2

0

0

3

3

32

31

23

21

13

12

* ry

2

0

0

0

3

0

32

31

23

21

13

12

r


1/3 y13 + 1/3 y23 1

y13 + y23 3



• Quinto problema core

Auvy

yy

yy

yyy

yyy

yw

uv

Auv

uvuv

ogniper 0

3

2

3

2

min

2313

3231

231312

323112

• Soluz. Ottima

0

2

0

0

3

0

32

31

23

21

13

12

*y

• Quinto Problema di separazione

A uvuv

0

123

0

0

0

0

0

0

22min

3213

131232

232131

121323

323121

212313

313212

3231

2

2

0

0

0

0

32

31

23

21

13

12

* ry

21

0

0

0

0

21

32

31

23

21

13

12

*

3

1

2

3

2


1/2 y12 + 1/2 y32 1

y12 + y32 2


2

0

0

0

3

0

32

31

23

21

13

12

r


• Sesto problema core

Auvy

yy

yy

yy

yyy

yyy

yw

uv

Auv

uvuv

ogniper 0

2

3

2

3

2

min

3212

2313

3231

231312

323112

• Soluzione Ottima

0

2

0

0

3

2

32

31

23

21

13

12

*y

• Sesto Problema di separazione

A uvuv

0

123

0

0

0

0

0

0

222min

3213

131232

232131

121323

323121

212313

313212

323112

2

2

0

0

0

2

32

31

23

21

13

12

* ry

21

21

0

0

0

0

32

31

23

21

13

12

*

3

1

2

3

22

Valore Sol. Ottima = 0

• y* soluzione ottima del

rilassamento lineare del

Network Loading Problem

• Nessun Vincolo violato:

2

0

0

0

3

0

32

31

23

21

13

12

r

Il problema del network loading (B&B)

|A|

N

T

Auv

uvuv

Zy

MET μ )ry(

ywmin

0


• Sappiamo dunque calcolare un Lower Bound di buona qualità

risolvendo il rilassamento lineare del problema di Network Loading

|A|

N

T

Auv

uvuv

Ry

MET μ )ry(

ywminLB

0

Rilassamento Lineare

• Possiamo applicare l’algoritmo di Branch&Bound

• Migliorando la formulazione il Lower Bound cresce e l’algoritmo di

Branch&Bound diviene più efficiente

• Come migliorare (ulteriormente) la formulazione?

Formulazione «rounded metric»


Vincoli metrici

• Migliore formulazione ma quale Oracolo di Separazione?

• Euristica: trova il vincolo violato e poi aggiungilo arrotondato

𝒎𝒊𝒏

𝒖𝒗∈𝑨

𝒘𝒖𝒗 𝒚𝒖𝒗

𝝁𝑻𝒚 ≥ 𝝁𝑻𝒓 = 𝟏 𝝁 ∈ 𝑴𝑬𝑻𝑵=

𝒚 ∈ 𝒁+|𝑨|

Per ogni 𝜸 positivo e non intero tale

che ഥ𝝁 = 𝜸𝝁 ha tutte componenti

intere, abbiamo ഥ𝝁𝑻𝒚 intero e:

𝒎𝒊𝒏

𝒖𝒗∈𝑨


(𝒚 − 𝒓)𝑻𝝁 ≥ 𝟎 𝝁 ∈ 𝑴𝑬𝑻𝑵=𝒚 ∈ 𝒁+

|𝑨|

ഥ𝝁𝑻𝒚 ≥ ഥ𝝁𝑻𝒓 ഥ𝝁𝑻𝒚 ≥ ഥ𝝁𝑻𝒓

𝜸𝝁𝑻𝒚 ≥ 𝜸𝝁𝑻𝒓 = 𝜸

𝒎𝒊𝒏

𝒖𝒗∈𝑨


𝝁𝑻𝒚 ≥𝜸

𝜸> 𝟏 𝝁 ∈ 𝑴𝑬𝑻𝑵=

𝒚 ∈ 𝒁+|𝑨| «rounded metrics»

Costo minimo della capacità da installare

per servire la domanda r quando il costo è

Formulazione ottima del network loading


Formulazione ottima !!

Oracolo di separazione?

Si può fare meglio ?

𝒎𝒊𝒏

𝒖𝒗∈𝑨


𝝁𝑻𝒚 ≥𝜸

𝜸𝝁 ∈ 𝑴𝑬𝑻𝑵=, 𝜸𝝁 ∈ 𝒁+

|𝑨|

𝒚 ∈ 𝒁+|𝑨| «rounded metrics»

𝒎𝒊𝒏

𝒖𝒗∈𝑨


𝝁𝑻𝒚 ≥ 𝝆𝝁 ∀𝝁 ∈ 𝑴𝑬𝑻𝑵=

𝒚 ∈ 𝒁+|𝑨|

𝝆𝝁 = 𝒎𝒊𝒏

𝒖𝒗∈𝑨

𝝁𝒖𝒗 𝒚𝒖𝒗

𝝀𝑻𝒚 ≥ 𝝀𝑻𝒓 𝝀 ∈ 𝑴𝑬𝑻𝑵=𝒚 ∈ 𝒁+

|𝑨|

Teorema di Avella, Mattia, S.

Ottimizzazione Combinatoria 2 - uniroma1.itsassano/Slides/OCO2_2016/OCO2_Network_L… · uz + l zv...

Documents

Transcript of Ottimizzazione Combinatoria 2 - uniroma1.itsassano/Slides/OCO2_2016/OCO2_Network_L… · uz + l zv...