Network Optimization
- Questions 2 3 4 Please Network Optimization 1 (55.43 KiB) Viewed 23 times
questions 2 +3 +4 please : Network Optimization
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
questions 2 +3 +4 please : Network Optimization
questions 2 +3 +4 please :
Network Optimization
4.8 Exercises 1. Let (4.30) be the flow-path formulation of the routing that minimizes the worse case link utilization, and let *, , and be optimum multipliers for the problem, and optimum congestion. the min p subject to: 4.30a 38 λ: Σχ=h veD 4.30b PEP 4.30c 2 x ≤ ₂. Vee E PEP, 1:20. PEP 4.30d Answer true of false, justify your answer: a. If a path p does not carry traffic, then>0. b. If a path p carries traffic, then its weight according to equals c. If a link e has an utilization , <", then it could happen that >0. d. If a link e is a bottleneck (p = p), then it could happen that , = 0. 12. For the problem in formulation (4.30), prove that the expression: , where is the number of links in the shortest path of demand d, is a lower bound to the optimal congestion p*. Hint: Show that this is the solution of the relaxed problem for multipliers 13. For the problem in formulation (4.30), assume that a given path P is constrained to carry at least a traffic > 0. Let (p.x...") be a primal dual optimal solution to the original problem. Use it to compute a lower bound to the network congestion when the new constraint is added. 14. For the problem in formulation (4.30), where all the paths are admissible, prove that a necessary optimality condition is that every path in the network should traverse at least a bottleneck link.
Network Optimization
4.8 Exercises 1. Let (4.30) be the flow-path formulation of the routing that minimizes the worse case link utilization, and let *, , and be optimum multipliers for the problem, and optimum congestion. the min p subject to: 4.30a 38 λ: Σχ=h veD 4.30b PEP 4.30c 2 x ≤ ₂. Vee E PEP, 1:20. PEP 4.30d Answer true of false, justify your answer: a. If a path p does not carry traffic, then>0. b. If a path p carries traffic, then its weight according to equals c. If a link e has an utilization , <", then it could happen that >0. d. If a link e is a bottleneck (p = p), then it could happen that , = 0. 12. For the problem in formulation (4.30), prove that the expression: , where is the number of links in the shortest path of demand d, is a lower bound to the optimal congestion p*. Hint: Show that this is the solution of the relaxed problem for multipliers 13. For the problem in formulation (4.30), assume that a given path P is constrained to carry at least a traffic > 0. Let (p.x...") be a primal dual optimal solution to the original problem. Use it to compute a lower bound to the network congestion when the new constraint is added. 14. For the problem in formulation (4.30), where all the paths are admissible, prove that a necessary optimality condition is that every path in the network should traverse at least a bottleneck link.