COMP9334 Revision Problems for Week 10B
Chun Tung Chou March 8, 2021
1. A carrier is planning to build a network between 4 cities, which are labelled as Cities 1,2,3 and 4. The amount of traffic flowing between these cities are given in Table 1. To build this network, the carrier can choose between three different types of links with different cost-capacity combinations, as showed in Table 2. Note that:
• Each link is directed, i.e. it only carries traffic in one direction.
• The decision to build links (i,j) and (j,i) are independent. In other words, if the
carrier chooses to build link (i,j), it does not have to build link (j,i).
• Each link, if built, must have sufficient capacity to carry the traffic assigned to it.
• Each flow, i.e. the traffic between a pair of cities, can only use one path.
The carrier aims to build a network with the minimum cost. Formulate an integer programming problem and solve it using AMPL/CPLEX to determine:
(a) Which links the carrier should build and what type should it be? (b) How the traffic is to be routed in the network?
To
City 1 City 2 City 3 City 4
City1 – 1 2 3 From City2 3 – 2 1 City3 2 4 – 2 City4 1 5 3 –
Table 1: Amount of traffic between cities.
Type of link Capacity Cost 1 10 10 2 20 18 3 30 25
Table 2: Capacity and cost for different types of links.
1
Hint
Define decision variables
1 if the traffic from Node u to Node v uses link (i,j)
xij uv = 0 otherwise
1 ifalinkoftypekistobebuiltfromnodeitonodej
yijk = 0 otherwise
If all yij1,yij2 and yij3 are zero, then this means a link won’t be built from node i to
node j. Impose constraints that if there isn’t a link, no traffic can use that link etc.
2