Domande di teoria ed esercizi di esami di OC2

Esercizio 1:

Applicare l'algoritmo primale-duale relativo al Node-Cover per trovare la soluzione 2-approssimata del problema. Individuare pertanto la sequenza di voli che garantisca il minimo costo.

Sono dati i seguenti pairings ammissibili:

1. Berlino - Amsterdam - Atene {1, 2, 3}
2. Roma - Budapest {4, 5}
3. Roma - Amsterdam - Helsinki {4, 2, 6}
4. Helsinki - Londra {6, 7}
5. Berlino - Londra {1, 7}
6. Atene - Budapest {3, 5}

Abbiamo I = {F₁, F₂, ..., F₇} ∀ servizio h = 1, .., 7. F_n ⊆ J sono insiemi che contengono lo stesso servizio h J = {1, .., 6} pairings ammissibili

Svolgimento:

• Determino gli F_n:
• F₁ = {1, 5}
• F₂ = {1, 4, 3}
• F₃ = {1, 6}
• F₄ = {2, 3}
• F₅ = {2, 6}
• F₆ = {3, 4}
• F₇ = {4, 5}
• T ⊆ J è un cover (⇔) |F_i ∩ T| ≥ 1 ∀ F_i ∈ I

Nodi := pairings ammissibili

Archi := F_i

Vogliamo che ogni arco sia coperto

• Vogliamo trovare il cammino a costo minimo

C = [1 1 1 1]

• Definisco primale e duale

Primale

min CT u

• Σ u_e ≥ 1 ; e ∈ F
• u_e ≥ 0

Dual

max 1^T y

• Σ y_f ≤ c_e; e ∈ J
• y_f ≥ 0; f ∈ I

+ y_F0 + y_F7

min u₁ + u₂ + u₃ + u₄ + u₅ + u₆

1. y_F1 + y_F2 + y_F3 ≤ 1
2. y_F4 + y_F5 ≤ 1

F₁ u₁ + u₅ ≥ 1

u₁, ..., u₆ ≥ 0

• Passo ϕ: Scelgo una soluzione iniziale

y̅ = 0; J̅ = ∅; T̅ = ∅

• Passo 1: Scelgo una F̅; F̅ = F₂ t.c. non interseca J̅

F̅ = F₂ = {1, 3} ∧ J̅ = ∅

Aggiorno ỹ_F̅: ỹ_F̅ = ỹ_F2 + min{c_e - Σ y̅_F̅}

= 0 + min {1, 1} = 1

Scrivo i problemi:

Primal

min CTu

Δne ≥ 1 Fe ∈ I ue ≥ 0 e ∈ J

• min u1 + u2 + u3 + u4 + u5 + u6
• F1 u1 + u5 ≥ 1
• F2 u2 + u3 ≥ 1
• F3 u1 + u3 ≥ 1
• F4 u3 + u4 ≥ 1
• F5 u1 + u6 ≥ 1
• F6 u2 + u6 ≥ 1
• F7 u4 + u5 ≥ 1
• u1, ..., u6 ≥ 0

Dual

max ΔTy

Δyf ≤ ce, ee ∈ J yf ≥ 0 Fe ∈ I

• max y1f1 + y2 + y1f3 + y1f4 + y1f5 + y1f6 + y1f7
• 1 yf1 + yf3 + yf5 ≤ 1
• 2 yf2 + yf6 ≤ 1
• 3 yf2 + y3f4 ≤ 1
• 4 y4 + y7 ≤ 1
• 5 y1 + y7 ≤ 1
• 6 yf5 + yf6 ≤ 1

• Paso Φ: Scelgo F̅ + c. |F̅ ∧ J̅⁻| = Φ ∅ Fe ∈ I J̅ = Φ, T = Φ, ϓ̅ = Φ|I+1
• Paso 1: Scelgo F̅ = F1 = {1, 5}
• infatti |F̅1 ∧ J̅⁻| = Φ⁻
• → Aggiungo ϓ̅f = ϓ̅f1 = ϓ̅f1 + min{(ee - ∑ yf), fe ∈ F, F: fe ∉ F̅}
• = 0 + min{1 - yf1 - yf3 - yf5, 1 - yf1 - yF7} = 0 + min{1, 1} = 1
• → Aggiungo J̅⁻ = J̅c ∪ {1, 5} = {1, 5}
• → Aggiungo yf4 = 1
• → Aggiungo T = J̅⁻

Esercizio 6: Network Loading

Se il vettore:

è ottimo per il problema "cose", e

la domanda è data dal vettore:

cosa risponde l’oracolo di separazione?

Svolgimento:

• Definiamo il Problema di separazione:

• Otteniamo quindi il seguente problema:

X_AB + X_BA ≤ 1 X_BA + X_AC + X_CB ≤ 2 X_CB + X_BA + X_AC ≤ 2

Separazione di vettori {0,1} da Pc Elimino gli archi con λ̂_uv = 0

Cerco un ciclo C, a costo negativo, nel grafo zedotto (Floyd-Warshall)

Se ∃ C : ∑_e∈C R_e <0 allora il vincolo di Pc ∑_u∈C X̂_uv ≤ |C| - 1 è violato da X̂ ∈ {0,1}^|A| ⇒ ∑ X̂_uv = |C|

Se ∄ C, allora X̂ ∈ Pc

PASSO 5: Θ₄ = 5 Θ₄ = ¹/₁₆

• CALCOLO L(Ĝ) = min{[L(Ĝ)^δ] = L^-2}
• NON AGGIORNO L₈
• POSSIBILI SUBGRADIENTI
• L(Ĝ₄) ≥ {A·B-A·X} = {0}
• SCELGO UN SUBGRADIENTE: s = ϕ
• AGGIORNO
  • U₅ = U₄ + Θ₈ ¹/₁₆ · ϕ = ⁵/₈
  • Θ₄ = ¹/₃₂ = ¹/₃₂

STOP U_B = ¹/₂ → SOLUZIONE EURISTICA

ESEMPIO LAGRANGIAN MULTIPLIER PROBLEM:

max {V: V ∈ W(P) + U(T(P) - T, ∀ P ∈ P, u ≥ 0 }

- UT + min {W(P) + U(Z(P)), P∈P} → P* = Path u

PER U FISSATO TROVIAMO IL CAMMINO MINIMO CON PESI (W_ij + U_ij)

• Per U = 0 → W_ij mi aumenta dei tempi di transito → spendo poco ma arrivo in ritardo.
• Per U = -2.1 ho una alternativa migliore perché ho un numero intermedio qualunque.
• Per U = M >> 0 → W_ij + M_ij ≫ M_ij Big M rende trascurabili tutta gli altri numeri.

∀ U ho una DIVERSA ISTANZA del cammino minimo in quanto cambiano solo i pesi.

13)

Scrivere Pc le cui sol. ammissibili sono i vettori di incidenza degli insiemi di archi la cui rimozione disconnette il grafo.

Pc =

• a + b ≤ 1
• a + c ≤ 1
• a + d ≤ 1
• b + d ≤ 1
• b + c ≤ 1
• d + c ≤ 1
• a, b, c, d ≥ 0

14)

Trasforma Pc in set covering

Psc =

• a + b ≥ 1 F₁
• a + c ≥ 1 F₂
• a + d ≥ 1 F₃
• b + d ≥ 1 F₄
• b + c ≥ 1 F₅
• d + c ≥ 1 F₆
• a, ..., d ≥ 0

15)

APPLICA PRIMALE DUALE

PAS_SO Φ_1:

J̅ = Φ, T̅ = Ø, Y̅_f = Ø

1: ∃ F̅ : [F̅ ∧ J̅] = Ø

F̅ = F₄

Y̅_A = Y̅_12 + min(1 - 0, 1 - 0) = 1

J̅ = J̅ ∪ {1, 2, 3} , Tᵀ = J₅

c(J̅) = 4, d = 2

PAS_SO 2:

F̅ = F₇₄

Y̅₇₄ = Y̅₃₄ + min(1, 1) = 1

J̅ = {1, 2, 3, 4}

8) Dimostra il Teorema di Rado-Edmonds

Secondo questo Teorema l'Algoritmo greedy trova una soluzione ottima <=> S è una matroide.

· S è matroide => r₂(X) = 2(X)

· Poiché q( S ) ∈ [r₂(X), < C(T _u) ≤ 1]

C(2X) C(T^F)

· Allora r_K(C(T _u) ≤ 1 allora necessariamente C(T_u) = C(T^F)

· Se X non fosse una matroide r₂(X)< r₂(X)

· allora ∃ B₁, B₂ ∈ T, tale che B₁ = T_u, B₂ = T^F*

e B₁ ∡ F*-allora si avrebbe:

e_i ∈ ℓ + ɸ ∉ e_i ∈ B₁, ɸ_∅ ∈ 5 |B₂−1|−|B₁|

|B₁|

e_i ∈ 1 ∈ e_i ∈ B₂

e_i ∈ 0 ∈ e_i ∉ B₂ ⊂ e_i

=> C(T_u) = C(B_R) |B₁|+δ|B₁|C|B₁+|∏B₁|✓|B₂|

|B₂ ≤ 5|B₂|+δ|B₁∧B₂|− C(B₂) = C(T^F)|

=> C C(T_u) < C(T^F) se S è una matroide.

9) Definire il concetto di ALGORITMO e FORMULAZIONE APPROSSIMATA

ALGORITMO APPROSSIMATO: Un algoritmo si definisce approssimato quando genera una soluzione

α-approssimata ∀ istanza (S,C) di Π.

FORMULAZIONE APPROSSIMATA: Una formulazione si dice approssimata

<=> genera un integral gap

pari ad α per ogni istanza (S,C) di Π.

Procediamo che l' istanza (S,C) è l' insieme delle soluzioni

ammissibili S a capacita C e t.c.

S = {o_i, jⁿⁱ | , C ∈ R}^U

dove u^¯ ∉ {o_i, j^η} è la sol. ottima di (S,C)

PLO-1 z^¯= u^¯ miu c^{T _u}

w∈S∈{o_i, j^u}