COMP9334 Revision Problems for Week 9B
Chun Tung Chou March 8, 2021
1. A network is represented as a directed graph G = (N, E) where N = {1, 2, …, n} is the set of nodes and E is the set of directed edges. The cost of using link eij ∈ E is cij and the remaining capacity on link eij is rij. The propagation delay of link eij is dij. A customer of the network wants the network to carry a flow of size b for it. The customer has the following requirements:
• The flow’s source and destination are respectively node n1 ∈ N and node n2 ∈ N
• The network must provide 2 different paths with for the flow. The flow normally
uses only the first path but if it fails, it is switched to the second (or backup) path.
• Both paths begin at the source and end at the destination.
• All the links of both path must have at least a capacity b, i.e. links with a residual capacity less than b cannot be used.
• The total propagation delay in each path must not be greater than dmax
• The two paths must not have any common link.
• The total cost of the two paths is minimised.
(a) Formulate an integer programming problem which solves for both paths simulta- neously.
(b) Using the data given below, find the paths for the customer.
• Number of nodes = 6. The nodes and edges in the network are defined overleaf in AMPL format.
• The cost, propagation delay and residual bandwidth are given overleaf in AMPL format.
• Source node = 1. Destination node = 4;
• b = 2.
• dmax = 8.
1
You will find the following pre-ample useful if you are using AMPL. In the ”mod” file:
set NODES; #set of nodes
set EDGES within {i1 in NODES,i2 in NODES: i1 <> i2}; #set of edges
param cost {(i,j) in EDGES};
param delay {(i,j) in EDGES};
param remaining_bandwidth {(i,j) in EDGES};
In the ”dat” file:
set NODES := 1,2,3,4,5,6;
set EDGES := (1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,6),(6,5),
(1,6),(6,1),(2,6),(6,2),(2,5),(5,2),(3,6),(6,3),(3,5),(5,3);
param: cost delay remaining_bandwidth :=
[1,2] 1 5 9
[2,1] 3 1 6
[2,3] 2 4 4
[3,2] 3 3 3
[3,4] 2 1 4
[4,3] 3 3 7
[4,5] 3 3 4
[5,4] 2 4 4
[5,6] 4 3 5
[6,5] 1 1 6
[1,6] 3 3 3
[6,1] 4 4 4
[2,6] 2 1 5
[6,2] 3 2 6
[2,5] 1 2 7
[5,2] 2 2 9
[3,6] 1 2 3
[6,3] 3 1 4
[3,5] 2 3 1
[5,3] 2 3 3;
2