Progetto di Reti di Telecomunicazione Modelli in Programmazione Lineare Problemi di flusso

Progetto di Reti di Telecomunicazione Modelli in Programmazione Lineare

Problemi di flusso

Flusso di costo minimo

E dato un grafo direzionato G = (N, A). Ad ogni arco (i, j) ∈ A `` e associato il costo c_ij di instradare un’unit`a di flusso sull’arco stesso. Inoltre, ad ogni arco (i, j) ∈ A sono associate una quantit`a di flusso minima l_ij e massima u_ij che pu`o transitare sull’arco stesso. Ad ogni nodo i ∈ V `e associato un bilancio di flusso b_i: se b_i > 0 il nodo offre del flusso alla rete ed

`

e detto nodo sorgente, se b_i < 0 il nodo richiede flusso dalla rete ed `e detto nodo pozzo, infine se b<sub>i</sub> = 0 il nodo non richiede ne offre flusso ed `e detto nodo di transito. Il problema richiede di inviare flusso dai nodi sorgente ai nodi pozzo, in modo che il bilancio di ciascun nodo a costo minimo, rispettando i limiti inferiori e superiori di flusso su ogni arco.

Modello Variabili:

• x_ij ∀(i, j) ∈ A : flusso sull’arco (i, j) ∈ A Funzione obiettivo:

min X

(i,j)∈A

c_ijx_ij Vincoli:

• bilanciamento ai nodi:

X

(i,j)∈A

x_ij + X

(j,i)∈A

x_ji = b_i, ∀i ∈ V

• capacit`a degli archi:

x_ij ≤ u_ij, ∀(i, j) ∈ A

• limite inferiore di flusso sugli archi:

x_ij ≥ l_ij, ∀(i, j) ∈ A Dominio delle variabili:

• x_ij ≥ 0

Variante

Viene modificato il vincolo sul flusso inferiore richiedendo che se l’arco (i, j) viene usato, il flusso instradato sia almeno pari a l_ij. A differenza che nel caso precedente, per`o, viene lasciata la possibilit`a di non usare l’arco.

E necessario aggiungere una variabile binaria per formulare il problema.`

• y_ij = 1 se sull’arco (i, j) ∈ A passa un flusso non nullo, cio`e se l’arco `e usato.

La variabile yij deve essere collegata alla variabile di flusso con un vincolo di big M, che fissa ad 1 il valore di y_ij se la variabile x_ij`e strettamente positiva:

x_ij ≤ u_ijy_ij, ∀(i, j) ∈ A.

Il nuovo vincolo pu`o sostituire il vincolo di capacit`a dell’arco.

Il vincolo sul limite inferiore del flusso diventa:

x_ij ≥ l_ijy_ij, ∀(i, j) ∈ A

Cammino minimo

Il problema di trovare, dato un grafo G = (V, A), con costi c_ij sugli archi, e un nodo sorgente s, il percorso di costo minimo tra s e tutti gli altri nodi pu`o essere formulato come un problema di flusso di costo minimo.

Ogni percorso `e visto come un flusso unitario che deve essere inviato dalla sorgente al nodo destinazione. Il problema pu`o essere formulato come un flusso di costo minimo con:

b_i =

(|V | − 1 se i `e il nodo sorgente,

−1 altrimenti.

Flusso multiprodotto

E dato un grafo orientato con costi c` <sub>ij</sub> sugli archi e capacit`a degli archi u_ij. Sulla rete sono presenti K domande di traffico, ciascuna caratterizzata da un nodo sorgente sk, un nodo destinazione tk e una quantit`a di traffico che deve essere instradata d<sub>k</sub>. Non ci sono due domande che abbiano la stessa coppia sorgente-destinazione. Si richiede di instradare tutte le domande a costo minimo, rispettando le capacit`a degli archi. (Problema di routing)

Modello con flussi sugli archi Variabili (definiscono i flussi sugli archi):

• x^k_ij ∀(i, j) ∈ A : flusso sull’arco (i, j) ∈ A relativo alla domanda k Funzione obiettivo:

minX

k∈K

X

(i,j)∈A

c_ijx^k_ij Vincoli:

• bilanciamento ai nodi:

X

(i,j)∈A

x^k_ij+ X

(j,i)∈A

x^k_ji =







d_k se i = s_k,

−d_k se i = t_k 0 se i 6= s_k, t_k,

∀i ∈ V, ∀k ∈ K

• capacit`a degli archi:

X

k∈K

x^k_ij ≤ u_ij, ∀(i, j) ∈ A

Dominio delle variabili:

• x^k_ij ≥ 0

Dimensione della formulazione:

• Numero di variabili : |A||K|

• Numero di vincoli : |N ||K| + |A|

Modello con flussi sui cammini

La formulazione si basa sul flusso associato a ciascun cammino invece che al flusso sugli archi. Indichiamo con P l’insieme di tutti i possibili cammini che collegano nodi del grafo, con Pki cammini che collegano gli estremi della domanda k e con P_ij i cammini che passano per l’arco (i, j). Il costo di un cammino `e definito come c_p =P

(i,j)∈pc_ij. Variabili (definiscono i flussi sui cammini):

• x_p ∀p ∈ P : flusso sul cammino p ∈ P Funzione obiettivo:

minX

p∈P

c_px_p Vincoli:

• instradamento delle domande:

X

p∈Pk

x_p = d_k ∀k ∈ K

• capacit`a degli archi:

X

p∈Pij

x_p ≤ u_ij, ∀(i, j) ∈ A

Dominio delle variabili:

• x_p ≥ 0

• Numero di variabili : esponenziale

• Numero di vincoli : |K| + |A|