Risposte alle domande di esame Ottimizzazione Combinatoria 2 - Sassano

N=

3. Oppure concludi che non esiste vincolo metrico violato da y* quindi y*∈NL(r)

0 =}

Ciò deriva dalla seguente proprietà: se y*≥ il problema min{(y*-r)Tμ: μ∈ ammette soluzione

ottima μ*. La dimostrazione si fa per assurdo: supponiamo che il problema sia illimitato, esiste μ’∈

′

( −) ( ∗)′,

= ℎ ∗ < −1, > 1 + ≥ 0 0,

ma poiché y*,μ′ allora (y*)Tμ’≥

=

quindi rTμ’>1. Questa è una contraddizione perché μ’∈ implica rTμ’=1. Allora possiamo riscrivere

=},

l’oracolo nel seguente modo: Risolvi min{(y*-r)Tμ: μ∈ sia μ* la soluzione ottima, se (y*-r)Tμ*<0

7

0, 0 =

restituisci il vincolo violato (y-r)Tμ*≥ altrimenti (y-r)Tμ*≥ per ogni μ∈ e concludiamo che

non esiste vincolo metrico violato da y*.

 Problema di separazione vincoli semi-metrici

∑

min ( ∗ −)

∈

− + ≥ 0 , , ∈ , ≠ ≠

{ ∑ = 1

∈

≥ 0 ∈

 Definire formalmente il concetto di semimetrica e cono poliedrale e dire perché METn è un cono

poliedrale 0||

Dato un grafo orientato completo G(N,A) con lunghezze sugli archi l≥ , L (l) lunghezza del cammino

uv

0

minimo (rispetto a l) da u a v. l≥ è una semimetrica se e solo se luv=Luv(l) per ogni uv∈ (ovvero la

lunghezza luv di uv è pari alla lunghezza del cammino minimo da u a v usando l come vettore delle

lunghezze degli archi). ((tutte le semimetriche hanno la proprietà che le lunghezze dei cammini minimi sono

sempre uguali al valore scritto sugli archi diretti)) ||

Un cono poliedrale è l’insieme di soluzioni di un sistema di disequazioni lineari omogenee. METn⊆ è

||

un cono poliedrale in quanto è definito dalle semimetriche l∈ soluzioni del sistema di disequazioni

≤ + = − − ≤ 0 , , ∈ , ≠ ≠

{

lineari omogenee: ed è detto cono

≥ 0 ∈ ∈

metrico. ((la struttura di METn è quella di un cono poliedrale infatti gode della proprietà: per ogni l̅

≥ 0 ℎ ∈ )) Le soluzioni di questo sistema sono semimetriche (rispettano la

disuguaglianza triangolare).

 Dimostrare il teorema giapponese:

Dato un grafo G(N,A) completo orientato 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. DIM:

SOLO SE: il problema multicommodity flow ammette soluzione allora per ogni semimetrica μ∈METn= si ha

(c-r)Tμ≥0. Se μ* ottima e (D ) è un problema di minimo: cTμ*≥1 allora cTμ>=1 per ogni μ∈METn=. Se

μ ∑ = 1 = 1).

μ∈METn= allora μ soddisfa il vincolo (rT Sottraendo rTμ=1 da cTμ≥1

abbiamo: cTμ-rTμ≥0 per ogni μ∈METn= allora (c-r)Tμ≥0 per ogni μ∈METn=. Seconda parte: SE: (c-r)Tμ≥0

per ogni μ∈METn= allora il problema ammette soluzione: μ∈METn= allora μ soddisfa il vincolo

∑ = 1 (rTμ=1) (1), (c-r)Tμ≥0 per ogni μ∈METn= (2). Sommando la 1 e la 2 cTμ≥1 per ogni

μ∈METn= allora la soluzione ottima μ* di (Dμ) è tale che cTμ*≥1, quindi il problema ammette soluzione.

 Dimostrare che il vettore di incidenza di un taglio (S,T) è una semimetrica

,

Dato un grafo orientato H(N,A) e un insieme di nodi W⊆ un taglio associato a W è l’insieme

+ A

: ∈ , ∈ − }.

δ (W)={(u,v)∈ Se y∈{0,1} è vettore di incidenza di un taglio allora y è una

semimetrica. DIM: per assurdo supponiamo che y non sia una semimetrica, allora esistono tre archi

(u,v),(u,z) e (z,v) tali che yuv>yuz+yzv. Affinchè la disuguaglianza triangolare non sia soddisfatta yuv=1 e

∈ ∈ − .

necessariamente yuz=yzv=0. Se yuv=1 abbiamo che Se yuz deve valere 0 z dovrebbe

appartenere a W come u, se yzv deve valere 0 allora anche v dovrebbe appartenere a W, ciò contraddice

− ).

quanto detto prima (v∈ Allora y è una semimetrica.

 Scrivere la formulazione capacità ∑

min

∈

( )

{ − ≥ 0 ∀ ∈ =

Credo sia questa: le yuv∈ sono le capacità installabili, il problema è:

+ ||

∈ +

METn= è il METn più il vincolo che rTμ=1 8

Flusso multicommodity

 Definire il problema del flusso multicommodity ||

0||,

Dati un grafo orientato G(N,A), un vettore capacità c≥ una matrice domanda D∈ dove p è il

||

k ∈ ∈

numero di beni K={1,..p}, x uv∈ è il flusso multicommodity di (G,c,D).

||

Detti w∈ i costi associati alle coppie arco-commodity, il problema consiste nel trovare il flusso

multicommodity di costo minimo

∑ ∑

min ∗

∈ ∈

∑ ∑

− = ∀ ∈ , ∀ ∈ ( )

S:{ − +

∈ () ∈ ()

∑

0 ≤ ≤ ∈ (à)

∈

 Descrivere rilassamento lagrangiano R(μ) del problema flusso multicommodity

Sulle slide al posto di u c’è λ, dovrebbe essere la stessa cosa.

∑ ∑ ∑ (∑

+ − )

R(μ) min dove μ∈R |A| vettore di penalità.

+

∈ ∈ ∈ ∈

() ∑ ∑ ∑

( +) − . Abbiamo quindi:

∈ ∈ ∈

∑ ∑ ∑

+ min ( +)

L(μ)=- con

∈ ∈ ∈

∑ ∑

− = ∀ ∈ , ∀ ∈

− +

∈ () ∈ ()

Q={

0 ≤ ≤ ∀ ∈



Dimostra che per ogni u≥ R(u) è un lower bound per il problema di flusso multicommodity

(teorema del lower bound lagrangiano) ∗.

Se definiamo con z* lìottimo di P allora per ogni μ∈R |A| abbiamo che L(μ)≤ Dim: se chiamiamo x̅

+ ∗∈

{

l’ottimo del problema R(μ) e x* quello di P allora: x*∈

∑ − ) ≤ 0 ∀ ∈

∈

∑ ∑ ∑ ∑ ∑

+ ( +) ≤ ( +

dunque per μ∈R |A|: L(μ)= )=-

+ ∈ ∈ ∈ ∈ ∈

∑ ∑

) ∗ ≤ ∗ = ∗

∈ ∈

 Teorema del lower bound lagrangiano ∈Q⊆Rn}

dato il problema di Ottimizzazione: P:z*=min{wTx: Ax≥b, x dove A(mxn), dove il rilassamento

lagrangiano per ogni vettore di moltiplicatori u≥0m è R(u): L(u)=min{wTx+uT(b-Ax): x∈Q⊆Rn} il teorema

dice che per ogni u≥0m abbiamo L(u)≤z*. DIM: x̅ ottima per R(u) allora L(u)= wTx̅ + uT(b-Ax). X* ottima per

∗≥ ( − ∗) ≤ 0 () ( ) +(

{ = + − ≤ ∗ −

P allora allora

())

∗∈ ( ∗

∗)

≤ ∗= ∗

 Definisci subgradiente, subdifferenziale, sequenza di passi che garantisce l’arresto del metodo del

subgradiente ()

≥ ∀ ∈

Subgradiente: i vettori s∈ tali che g(u̅ )+sT(u-u̅ ) sono i subgradienti di g in u̅

(pendenze della retta tangente nel punto). (̅) { ̅}.

= ∈ : è

Subdifferenziale: insieme di tutti i vettori s:

 O criterio di arresto oppure scelta di θi e criterio di arresto (chiedi quale vuole). Criterio di arresto,

teorema: se g è una funzione concva in Rm, u* è una soluzione ottima per il problema max{g(u):

( ∗). ( ∗) ( ∗) 0( ∗) ()

↔ + − ≥ ∀ ∈

u∈Rm} se e solo se 0m∈ dim: 0m∈

( ∗) ()

↔ ≥ ∀ ∈ . Il criterio di arresto vale per qualsiasi u, se 0m appartiene al sub

gradiente allora la soluzione è ottima. Scelta di θi: θ(i)=R/i è una sequenza ottima di passi poiché

∑ ( )

) θ i = infinito

lim(per i→ θ(i)=0 e , oppure θ(i+1)=θ(i)/2 e ci fermiamo quando

=1

Ɛ,

θ(i+1)≤ il numero di iterazioni dipenderà dal logaritmo.

9

 Descrivi algoritmo subgradiente applicato al duale lagrangiano

1. Scegli Ɛ, θ(0), u(0) e poni i:=0, Lbest:=-infinito

2. Passo i: k k̅ k̅

) ∈

3. Trova L(u(i))=min(k∈ L (u(i))=wTx +(b-A x )Tu(i) c