Thomas Kunz
Systems and Computer Engineering
5
Sample Linear Program
max: Z_A Z_A: flow from A to C
Flow Balance
constraints (per node): X_I,J:
flow over link from I to J
X_A,B = Z_A +
X_B,A
nX_B,A + X_B,C =
X_A,B + X_C,B Flow Balance
Constraint: as much
nX_C,B + Z_A =
X_B,C flows into each node
as out
nCapacity
Constraints (per link) Capacity
Constraint: no link can
X_A,B <=
LINK_BW exceed link
bandwidth
X_B,A <=
LINK_BW
X_B,C <=
LINK_BW Solution:
Z_A = X_A,B = X_B,C = 1 (assuming
LINK_BW=2)
X_C,B <=
LINK_BW X_B,A
= X_C,B = 0
n L1 = L3 = 0.5, L2 = L4 = 0
nScheduling
Constraints Scheduling
Constraints: model
nL1 + L2 + L3 + L4
<= 1 interference. Idea is
based on
X_A,B <=
LINK_BW * L1 scheduling
transmission over non-
X_B,A <=
LINK_BW * L2 interfering
links by determining
X_B,C <=
LINK_BW * L3 maximum sets of
non-interfering
X_C,B <=
LINK_BW * L4 links.