Laboratorio 5 Fondamenti di Ricerca Operativa

(1)

Laboratorio 5 Fondamenti di Ricerca Operativa

Prof. E. Amaldi

Problema di Instradamento di Pacchetti

Ci sono n = 10 flussi di dati che devono essere instradati dal nodo s al nodo t seguendo soltanto uno di m = 2 link possibili, con capacit`a rispettivamente u

1

= 1Mbps e u

2

= 2Mbps.

PSfrag replacements

s t

link 1

link 2

La tabella seguente riporta la quantit`a di risorse consumate dall’i-esimo flusso, e il costo di instradare l’i-esimo flusso sui due link.

Flusso Risorse richieste (Mbps) Costo sul link 1 Costo sul link 2

1 0.3 200 270

2 0.2 200 250

3 0.4 250 310

4 0.1 150 200

5 0.2 200 210

6 0.2 200 210

7 0.5 700 1000

8 0.1 150 210

9 0.1 150 210

10 0.6 900 1400

Si formuli in AMPL (con relativo file di dati) il problema di minimizzare il costo di instradamento totale dei flussi rispettando le capacit`a dei link.

Documento preparato da Pietro Belotti e Leo Liberti

1

(2)

Laboratorio 5 Fondamenti di Ricerca Operativa

Prof. E. Amaldi

Soluzione

Formulazione

• Indici:

1. sia i un indice sull’insieme dei flussi F = {1, . . . , n}.

2. sia j un indice sull’insieme dei link L = {1, . . . , m}.

• Parametri:

– a

_i

`e la quantit`a di risorsa consumata dal flusso i (∀i ∈ F );

– c

ij

`e il costo di instradamento del flusso i sul link j (∀i ∈ F );

– u

j

`e la capacit`a del link j (∀j ∈ L).

• Variabili:

x

ij

vale 1 se il pacchetto i `e instradato sul link j (∀i ∈ F, j ∈ L).

• Funzione obiettivo:

min X

m j=1

X

n i=1

c

ij

x

ij

.

• Vincoli:

– ∀i ∈ F ( P

m j=1

x

ij

= 1);

– ∀j ∈ L ( P

n i=1

a

i

x

ij

≤ u

j

).

Modello AMPL

# instradamento di pacchetti (problema di bi-zaino) param n > 0;

param m > 0;

set F := 1..n;

set L := 1..m;

param a{F} >= 0;

param c{F,L} >= 0;

param u{L} >= 0;

var x{F,L} binary;

minimize objfun :

2

(3)

Laboratorio 5 Fondamenti di Ricerca Operativa

Prof. E. Amaldi

sum{i in F, j in L} c[i,j]*x[i,j];

subject to assegnamento {i in F} : sum{j in L} x[i,j] = 1;

subject to zaino {j in L} : sum{i in F} a[i]*x[i,j] <= u[j];

Dati AMPL param n := 10;

param m := 2;

param a :=

1 0.3 2 0.2 3 0.4 4 0.1 5 0.2 6 0.2 7 0.5 8 0.1 9 0.1 10 0.6 ;

param c : 1 2 :=

1 200 270 2 200 250 3 250 310 4 150 200 5 200 210 6 200 210 7 700 1000 8 150 210 9 150 210 10 900 1400;

param u :=

1 1 2 2 ;

Soluzione CPLEX

CPLEX 7.1.0: optimal integer solution; objective 3600 7 MIP simplex iterations

0 branch-and-bound nodes objfun = 3600

x :=

1 1 0

3

(4)

Laboratorio 5 Fondamenti di Ricerca Operativa

Prof. E. Amaldi

1 2 1

2 1 0

2 2 1

3 1 0

3 2 1

4 1 1

4 2 0

5 1 0

5 2 1

6 1 0

6 2 1

7 1 0

7 2 1

8 1 1

8 2 0

9 1 1

9 2 0

10 1 1 10 2 0 ;

4