1. (a)
COMP9334 Solution to Revision Problems for Week 9B
Chun Tung Chou March 8, 2021
The decision variables are
• xij1 = 1 if the primary path uses link (i,j), otherwise 0 • xij2 = 1 if the backup path uses link (i,j), otherwise 0
The object is to minimise
subject to
j :(i,j )∈E
cij(xij1 + xij2) (i,j )∈E
1 ifi=n1
= 0 ifi∈N−{n1,n2}
−1 ifi=n2 ≤ dmax
≤ dmax
≤ rij
≤ 1
∈ {0,1} for all (i,j) ∈ E,k = 1,2
(1)
k=1,2
xijk −
(i,j )∈E
dijxij2
(i,j )∈E
(xij1 + xij2)b
xij1+xij2 xij k
j :(j,i)∈E
dijxij1
xjik
(b) The paths are 1−6−5−4 and 1−2−6−3−4. AMPL files are in disjoint_hw.dat, disjoint_hw.mod and disjoint_hw_batch
1