COMP9334 Revision Problems for Week 10A – Solution
1. The decision variables are
Chun Tung Chou March 8, 2021
if a controller is to be placed at node i otherwise
•
•
1 yi = 0
xij =
The optimisation problem is:
subject to
1 if the controller at node i is to control the switch at node j 0 otherwise
n minyi
i=1
n
xij = 1∀j=1,..,n (1)
i=1
xijdij ≤ Dyi ∀i,j=1,..,n (2)
xij ∈ {0,1} (3) yi ∈ {0,1} (4)
Equation 1 enforces the constraint that a switch is associated with only one controller. Equation 2 ensures that: (i) If yi = 0, i.e. there is no controller at node i, then xij = 0; (ii) If yi = 1, then any switch that is connected to the controller at node i must have a communication delay of less than D. Equation 2 has combined (i) and (ii) into a set of inequalities. Alternatively, you can use
xij ≤ yi ∀i,j=1,..,n (5) xijdij ≤ D ∀i,j=1,..,n (6)
to separately enforce the conditions (i) and (ii).
1