Domande esame Ottimizzazione combinatoria 1 (Bruni-Sassano)

Algoritmo di Christofides

1. Cos'è il TSP metrico?
2. Perché si può definire α-approssimato?
3. Perché la soluzione dell'algoritmo può essere di ordine 2-approssimato
4. Algoritmo Christofides

1) Il TSP metrico è quella classe di problemi TSP che dato un grafo G(V,E) non orientato, completo, con costi c sugli archi, se c_uv > 0 ∀ u,v ∈ E e c_uv = 0 se e solo se u = v, allora c è tale che per ogni tripla di nodi distinti u,v,z si ha c_uv ≤ c_uz + c_zv [disuguaglianza triangolare]; si dice che c induce una metrica.

2) Per un problema di ottimizzazione Q: min {c(F): F ∈ S} = ν(Q), come possiamo definire la qualità della soluzione prodotta da un algoritmo? Sia A un algoritmo che garantisce un'approssimazione α (ossia α-approssimato) se c(F) ≤ α ν(Q).

3) Dato un grafo G(V,E) non orientato, completo, con costi C dati da una semimetrica, l’algoritmo di Christofides trova un ciclo hamiltoniano di costo al più doppio rispetto al ciclo di costo minimo: trova un albero ricoprente T di G; raddoppia ogni arco di T così da trovare un grafo euleriano; costruisce un ciclo euleriano e di questo grafo; sceglie un nodo iniziale U in E e visita E a partire da U; costruisce una permutazione π dei nodi V ; restituisce il ciclo hamiltoniano H associato a π.

4) Th 2: Sia H^# il ciclo hamiltoniano di costo minimo e sia H il ciclo ritornato dall’algoritmo di Christofides. Allora c(H) ≤ 2c(H^#)

Dimostra: E è ottenuto da T^* raddoppiando gli archi (c(E) = 2 c(T^*)); H è ottenuto da E saltando forse anche qualche nodo (c(H) ≤ c(E) = 2 c(T^*)). Sappiamo da un altro teorema che c(T^*) ≤ c(H^#) quindi c(H) ≤ 2 c(T^*) ≤ 2 c(H^#). L’algoritmo di Christofides è quindi 2-approssimato.

max Y_t

Y_v - Y_u ≤ c_uv   ∀ uv ∈ A

-Y_s = 0

3) Teorema F₃ (Ammissibilita' Duale): Il problema duale ammette soluzioni (primal non è illimitato) se e solo se il grafo G(N, A) non ha cicli orientati di costo totale negativo.

Dimostraz. Se: sia P_u^* il cammino minimo da s ad un generico u ∈ N - {s}. Ponendo Y_v = c(P_v^*): se Y'_v - Y'_u ≤ c_uv Y' è una soluzione duale, se invece Y'_v - Y'_u > c_uv ⇒ c(P_v^*) - c(P_u^*) > c_uv ⇒ c(P_v^*) > c(P_u^*) + c_uv

Se V ≠ P^* ⇒ P' è un cammino con c(P'_u) = c(P_u^*) + c_uv < c(c(P_v^*)) ⇒ contraddizione!

Quindi V ∈ P_u^*!

Detto P'il sotto-cammino di P_u^* da v a u:

C = P' ∪ {uv} è un ciclo.

c(P_v^*) > c(P_v) + c(P') + c_uv ⇒ 0 > c(P') + c_uv = c(C) ciclo negativo!

Dimostraz. solo se: Supponiamo per assurdo che C = (1, 12, 2, ..., k, k', 1) sia un ciclo di G(N, A) con costo totale c(C) negativo. Poiché Y' è soluzione duale abbiamo che 0 ≤ c(C) < 0 che è una contraddizione!

Localizzazione di Impianti

1. Definire il problema di localizzazione di impianti.
2. Descrivere la formulazione forte e la formulazione debole.
3. Spiegare come si possono risolvere e che caratteristiche hanno.
4. Spiegare un possibile meccanismo di generazione vincoli.

1) Il problema detto di localizzazione di impianti rientra nella classe dei problemi di distribuzione: bisogna trasportare beni da una o più origini a una o più destinazioni, minimizzando il costo di trasporto e rispettando vincoli quali la capacità dei veicoli, la raggiungibilità delle destinazioni.

Si ha l’insieme I di m clienti da servire e l’insieme J di n impianti che posso attuare. L’impianto j costa f_j, il collegamento i-j costa c_ij: si vogliono minimizzare le spese.

La soluzione ammissibile deve rispettare dei vincoli: un cliente può essere assegnato ad un impianto solo se esso è attivato (y_j ≤ x_j). Ogni cliente deve essere assegnato ad un solo impianto ( ^Σ_jy_ij = 1 ).

Il modello del problema quindi prende la forma di:

min ^Σ_j f_jx_j + ^Σ_j ^Σ_i c_ijy_ij

^Σ_j y_ij = 1 ,   x_j - y_ij ≥ 0

y_ij ∈ {0,1},   x_j ∈ {0,1},   i ∈ I   j ∈ J

Si tratta di un problema della classe NP, per risolverlo serve il suo rilassamento lineare (LP).

2) Dal rilassamento lineare si ottiene la formulazione forte che modifica il vincolo x_j - y_ij ≥ 0 in: ^Σ_i y_ij ≤ |I|x_j, cioè la somma sui clienti dei vincoli di attivazione, e pone poi y_ij ≥ 0   x_j ≥ 0.

3)

L = P₀ , X^o indefinito, UB = +∞

L = Ø ?

Sì : X^o è l'ottimo X* cercato e STOP

No : scegli P_i ∈ L → calcola LB_i e X(S_i) con rilass.

LB_i < UB?

Sì → X(P_i) intero?

Sì → aggiorna UB := LB_i e X^o := X(P_i)

4)

Inizializzo L = P₀, X^o indefinito e UB = +∞: se L = Ø allora X^o è l'ottimo X* che cercavo e mi fermo; se L ≠ Ø scelgo un P_i ∈ L e mi calcolo LB_i e X(S_i) con il rilassamento: LB_i < UB? Se no faccio "branching" L = L ∪ { P_i+1 , P_i+2 } e ricomincio; se sì allora: X(P_i) intero? Se sì aggiorno UB = LB_i e X^o = X(P_i) e riparto da analizzare L = Ø?

5)

Bisogna operare delle scelte come P_i ∈ L; quello con il minimo lower bound, o il LIFO, o il FIFO. La scelta di X_k: la variabile più intera? Più frazionaria? O seguire un ordine predefinito? Non esiste una scelta che sia la migliore per tutti i problemi.

RICERCA LOCALE CON INTORNI ESPONENZIALI PER TSP

1. Definire l'euristica di Ricerca Locale
2. Commentare l'importanza della scelta del sistema di Intorni
3. Spiegare in cosa consiste l'intorno di "ASSIGN" per il TSP
4. Illustrare dettagliatamente come risolvere un problema di TSP usando tale tipo d'intorno.

1) L'euristica di Ricerca Locale è un'euristica migliorativa, ossia ha bisogno di una soluzione di partenza, per questo viene solitamente effettuata dopo un greedy (tecnica che a partire dall'insieme vuoto aggiunge ad ogni passo l'elemento che produce una soluz. parziale di minimo costo).

La Ricerca Locale, a partire da una soluzione ammiss. T₀, vuole costruire una sequenza di soluz. ammiss. T₀, T₁, T₂, ... individuando al passo k la soluzione di minimo costo T_k appartenente all'intorno H(T_k-1) della soluzione corrente T_k-1, e arrestandosi quando ogni valore appartenente a H(T_k-1) ha un valore peggiore della funzione obiettivo, ovvero c(T_k-1) < c(T_k).

2) Gli intorni sono fondamentali: se costituiti da pochi elementi generarli ed esaminarli è veloce, ma si hanno basse possibilità di miglioramento; se costituiti da molti elementi si hanno buone possibilità di miglioramento ma generarli ed esaminarli è più costoso. Ogni iterazione dell'algoritmo LS consiste nel risolvere un problema di ottimizz. locale, ossia un problema con insieme delle soluz. ammiss. più piccolo.