Telcom 2110 Network Design Homework #1 Fall 2003



Telcom 2110 Network Design Optimization Examples

1. Consider the five node network shown below, (a) write the linear program formulation to find the maximum flow from node 1 to node 5 using the end-to-end arc path approach. The free capacity of each link is shown next to each link. (b) Using a linear program solver (e.g., Excel, AMPL, Matlab, etc.) solve the problem and determine the amount of flow on each path.

[pic]

There six distinct routes between nodes 1 and 5 labeled as shown in the table below

|Flow |Route |

|f1 |1-2-4-5 |

|f2 |1-2-3-5 |

|f3 |1-3-5 |

|f4 |1-3-2-4-5 |

|f5 |1-2-5 |

|f6 |1-3-2-5 |

Following the formulation in Slides 5 the optimization formulation is

Maxamize f1 + f2 + f3 + f4 + f5 + f6

Subject to f1 + f2 + f5 [pic] 13 Constraint link 1-2

f3 + f4 + f6 [pic] 4 Constraint link 1-3

f2 + f4 + f6 [pic] 3 Constraint link 2-3

f1 + f4 [pic] 12 Constraint link 2-4

f2 + f3 [pic] 8 Constraint link 3-5

f1 + f4 [pic] 7 Constraint link 4-5

f5 + f6 [pic] 5 Constraint link 2-5

fi [pic]0 for i=1,2,…6

Using a linear program solver we get the solution

In Matlab formulate LP problems as

Minimize fx

s.t. Ax >f = [-1 -1 -1 -1 -1 -1];

>>% This denotes the objective function – not all the values are negative since

Matlab assumes minimization

>>% In writing the constraints the first 7 rows in the A matrix represent the link

constraints –the last 6 rows denote the requirement that the flows be greater

than or equal to 0

>>A = [1 1 0 0 1 0;

0 0 1 1 0 1;

0 1 0 1 0 1;

1 0 0 1 0 0;

0 1 1 0 0 0;

1 0 0 1 0 0;

0 0 0 0 1 1;

-1 0 0 0 0 0;

0 -1 0 0 0 0;

0 0 -1 0 0 0;

0 0 0 -1 0 0;

0 0 0 0 -1 0;

0 0 0 0 0 -1];

>> b = [13;

4;

3;

12;

8;

7;

5;

0;

0;

0;

0;

0;

0];

>> [x,fval] = linprog(f,A,b)

Optimization terminated.

x =

5.9836

2.5071

3.7894

0.0746

4.5093

0.1360

fval = -17

Thus the result the objective function is 17 – that is 17 units of flow/bandwidth with

the following assignment of flows to routes.

f1 = 5.9836, f2 = 2.5071, f3= 3.7894, f4 = 0.0746, f5 = 4.5093, f6 = 0.136

2. Consider the network diagram below with the potential links shown in the figure. Using the simple network design formulation in the Slide set 5 (slides 63-64). Find the minimum cost design. The traffic matrix in Mbps is given below - traffic is assumed symmetric and the demand pairs are list in order from the matrix. The links are labeled 1 through 7 as shown in the figure. The cost of bandwidth on each link is shown below. The maximum capacity on any link is 5 Mbps. The set of potential paths for any source –destination pair should be limited to the four shortest paths. For example from node 1 to 2 the path set P1 = {1}, {5,6}, {5,4,7}{5,4,3,2}, for demand pair 1-4 is given by P4 = {1,2}, {5,4,3},{5,6,2}, {1,7,3}. Note that the (edp values are determined from the path set.

[pic]

Traffic Demand Matrix

|Node |1 |2 |3 |4 |5 |

|1 | |2 |1 |1 |2 |

|2 | | |3 |.5 |.5 |

|3 | | | |1 |3 |

|4 | | | | |1 |

Cost of Capacity

|Link |1 |2 |3 |4 |5 |6 |7 |

|Cost |.2 |.5 |.4 |.5 |.25 |1 |.1 |

Using the optimization problem formulation of on slides 6 and 7 of class slides 13

Define the set of demand pairs d, their path sets P , and offered traffic demand hd we have

| d |Source - Destination | Traffic demand hd|Path Set |

| | | |1 |2 |3 |4 |

|1 |1-2 |2 |1 |5,6 |5,4,7 |5,4,3,2 |

|2 |1-3 |1 |5 |1,6 |1,7,4 |1,2,3,4 |

|3 |1-4 |1 |1,2 |1,7,3 |5,4,3 |5,6,2 |

|4 |1-5 |2 |1,7 |5,4 |1,2,3 |5,6,7 |

|5 |2-3 |3 |6 |1,5 |7,4 |2,3,4 |

|6 |2-4 |0.5 |2 |7,3 |6,4,3 |1,5,4,3 |

|7 |2-5 |0.5 |7 |2,3 |6,4 |1,5,4 |

|8 |3-4 |1 |4,3 |6,2 |4,7,2 |6,7,3 |

|9 |3-5 |3 |4 |6,7 |6,2,3 |5,1,7 |

|10 |4-5 |1 |3 |2,7 |2,6,4 |2,1,5,4 |

Note that the link cost (e is given in the table above and the link indicator variables (edp can be found from the path table above. The optimization problem from the notes can be written out as below

minimize F(y) = Σe (eye

subject to

Σp xdp = hd d=1,2,…,D

Σd Σp (edpxdp ≤ ye e=1,2,…,E

ye ≤ ce e=1,2,…,E

0 ≤ ye , 0 ≤ xdp for all e and d,p

minimize F(y) = .2 y1 + .5 y2 +.4 y3 +.5 y4 +.25 y5 +1y6 +.1 y7

subject to

x11 +x12 +x13 +x14 = 2

x21 +x22 +x23 +x24 = 1

x31 +x32 +x33 +x34 = 1

x41 +x42 +x43 +x44 = 2

x51 +x52 +x53 +x54 = 3

x61 +x62 +x63 +x64 = 0.5

x71 +x72 +x73 +x74 = 0.5

x81 +x82 +x83 +x84 = 1

x91 +x92 +x93 +x94 = 3

x101 +x102 +x103 +x104 = 1

x11 +x31 +x41 +x22 +x32 +x52 +x23 +x43 + x24 +x64 +x74 +x94+x104 ≤ y1

x31 +x61 +x72 +x82 +x102 +x43 +x83 +x93 + x103 +x14 +x24 +x34+x54 +x104 ≤ y2

x81 +x101 +x32 +x62 +x72 +x33 +x43 +x53 + x93 +x14 +x24 +x54+x64+x84 ≤ y3

x81 +x91 +x42 +x13 +x23 +x33 +x53 +x63 + x73 +x83 +x103 +x14+x24 +x54 +x64 +x74 +x104 ≤ y4

x21 +x12 +x42 +x52 +x13 +x33 +x14 +x34 + x44 +x64 +x74 +x94+x104 ≤ y5

x51 +x12 +x22 +x82 +x92 +x63 +x73 +x93 + x103 +x34 +x44 +x84 ≤ y6

x41 +x71 +x32 +x62 +x92 +x102 +x13 +x23 + x53 +x83 +x44 +x84+x94 ≤ y7

y1 ≤ 5 , y2 ≤ 5, y3 ≤ 5 , y4 ≤ 5, y5 ≤ 5 , y6 ≤ 5 , y7 ≤ 5

0 ≤ y1 , 0 ≤ y2 , 0 ≤ y3 , 0 ≤ y4 , 0 ≤ y5 , 0 ≤ y6 , 0 ≤ y7

0 ≤ x11 , 0 ≤ x12 , 0 ≤ x13 , 0 ≤ x14 ,

0 ≤ x21 , 0 ≤ x22 , 0 ≤ x23 , 0 ≤ x24 ,

0 ≤ x31 , 0 ≤ x32 , 0 ≤ x33 , 0 ≤ x34 ,

0 ≤ x41 , 0 ≤ x42 , 0 ≤ x43 , 0 ≤ x44 ,

0 ≤ x51 , 0 ≤ x52 , 0 ≤ x53 , 0 ≤ x54 ,

0 ≤ x61 , 0 ≤ x62 , 0 ≤ x63 , 0 ≤ x64 ,

0 ≤ x71 , 0 ≤ x72 , 0 ≤ x73 , 0 ≤ x74 ,

0 ≤ x81 , 0 ≤ x82 , 0 ≤ x83 , 0 ≤ x84 ,

0 ≤ x91 , 0 ≤ x92 , 0 ≤ x93 , 0 ≤ x94 ,

0 ≤ x101 , 0 ≤ x102 , 0 ≤ x103 , 0 ≤ x104 ,

Using a linear program solver we get the solution

F = 7.65

With y1 = 5, y2 = 1.5 y3 = 2 y4 = 5 y5 = 1 y6 = 2 y7 = 3.5

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download