COMP9334 Revision Problems for Week 10B – Solution
Chun Tung Chou March 8, 2021
1. Following the hint given in the question, we define the following decision variables:
•
•
xij uv
=
1 if the traffic from Node u to Node v uses link (i,j) 0 otherwise
1 ifalinkoftypekistobebuiltfromnodeitonodej 0 otherwise
yijk =
In addition, we define the following:
• N = {1,2,3,4} (i.e. the set of nodes)
• E = {(i, j) ∈ N × N : i ̸= j} (i.e. the set of all possible links)
• ck =thecostoflinkoftypek(asgiveninTable2)
• bk = the capacity of link of type k (as given in Table 2)
• fuv = the traffic demand from city u to city v (as given in Table 1) • An indicator function
The optimisation problem is:
subject to
j :(i,j )∈E
xijuv −
xjiuv = j :(j,i)∈E
δiu−δiv ∀i∈N,(u,v)∈E (1)
3
1 ifp=q
0 otherwise
3
min yijkck (i,j)∈E k=1
δpq =
xijuvfuv ≤ 3
yijk ≤ k=1
xij uv ∈ yij k ∈
bkyijk ∀(i, j) ∈ E (2) (u,v)∈E k=1
1
1∀(i,j)∈E (3)
{0, 1} (4) {0, 1} (5)
Note:
• Equation 1 is equivalent to
1 ifi=u xijuv− xjiuv = 0 ifi̸=u,v
j:(i,j)∈E j:(j,i)∈E −1 if i = v
The expression δiu − δiv evaluates to the expression on the right-end-side of the
above equation.
• Equation 2 ensures: (1) There is enough capacity in the link if it is built; and (2) If a link is not built (i.e. all yijk = 0 for k = 1,2,3), no traffic is routed in (i,j) (i.e. xijuv = 0).
• Equation 3 ensures that only one type of link is chosen.
The AMPL code is given in carrier.mod, carrier.dat and carrier_batch.
The optimised network has a cost of 58 units. It has 4 links of type 1 and they are (1,4), (2,3), (3,1), (3,2). It also has a link of type 2 for link (4,3). No links of type 3 is used. Traffic from node 1 to node 2 follows the path (1,4),(4,3),(3,2). Traffic from node 2 to node 3 follows the path (2,3). These can be read from xijuv. See the file carrier-solution where you can read out the paths for the other traffic demands.
Note that there are multiple networks (with different links and routes) which also gives the minimum cost of 58 units. These alternatives are also acceptable.
2