Domande esame Ottimizzazione combinatoria 1 (Bruni-Sassano)

Algoritmo di Christofides

Cos'è il TSP metrico?

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.

Perché si può definire α-approssimato?

Per un problema di ottimizzazione Q, c = min {c(F): F ∈ S} = v(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) ≤ α v(Q).

Perché la soluzione dell'algoritmo può essere di ordine 2-approssimato?

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 π.

Algoritmo di Christofides

Th 2: Sia H* il ciclo hamiltoniano di costo minimo e sia H il ciclo ritornato dall'algoritmo di Christofides. Allora c(H) ≤ 2 c(H*).

Dimostrazione: 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.

Formulazioni e rilassamenti lineari

Definizione di formulazioni di un problema di PL01

Una formulazione di un problema di programmazione lineare (PL01) consiste nel rappresentare il problema con equazioni e vincoli lineari.

Definizione di rilassamento lineare

Il rilassamento lineare di un problema di ottimizzazione è ottenuto rimuovendo o allentando alcuni dei vincoli del problema originale, solitamente quelli di integrità.

Definizione di "Lower Bound" e di "gap"

Il "Lower Bound" è un limite inferiore sul valore ottimale di un problema. Il "gap" rappresenta la differenza tra il valore della soluzione ottenuta e il valore ottimale teorico.

Definizione di qualità di una formulazione

La qualità di una formulazione si misura in base alla sua capacità di avvicinarsi al valore ottimale del problema originale.

Definizione di formulazione ottima

Una formulazione ottima di un problema è quella che permette di trovare la soluzione migliore in termini di costo o valore obiettivo.

Definizione di rilassamento della formulazione ottima

Il rilassamento della formulazione ottima si riferisce al processo di semplificazione della formulazione ottima per facilitare il calcolo, mantenendo il più possibile il valore della soluzione originale.

Fornire un esempio numerico di formulazione naturale e di formulazione ottima per un problema di pianificazione degli investimenti su singolo periodo

Se abbiamo X^eS soluzione ammissibile di un problema di minimo e non conosciamo X^*, possiamo avvalerci di alcune tecniche per il calcolo del Lower Bound. Una di queste è "Rilassamento Lineare" che si divide in "formulazione lineare" e "teoria della dualità".

Dato un problema di PL01 min{c^Tx: x^eS} e il poliedro P={x^eR^m: Ax...}