SGT

1

Determine all variables, this would be $f_{u,v}^q\text{ where }q\in 1,\dots ,k\text{ and }u,v\in V$ i.e. $f_{ab}^1,f_{ab}^2,f_{ab}^3,f_{a,q}^1,\dots$

And $\lambda$ is upper bound on congestion of edges.

Minimise $\lambda$, subject to:

• The flow conservation constraints:

  This is equivalent to ${\sum }_{v\in V}{f}_{uv}^q-{\sum }_{v\in V}{f}_{vu}^q=d_{qu}$ for each $q=1,\dots ,k$ and $u\in V$

  • Commodity $1$: $f_{bc}^1+f_{bp}^1-f_{ab}^1=3$ (node $b$) $-f_{cd}^1-f_{pd}^1=-3$ (node $d$) $f_{pd}^1+f_{pq}^1-f_{bp}^1=0$ (node $p$) .. etc
  • Commodity $2$: as above
  • Commodity $3$: as above
• The congestion constraints, one constraint for each edge:

  This is equivalent to $f_{uv}-h(u,v)\lambda \le 0$ for each $u,v\in V$

  • $f_{ab}^1+f_{ab}^2+f_{ab}^3-5\lambda \le 0$ (edge $a,b$)
  • .. etc
• Force non-negative flows:

  This is equivalent to $f_{uv}^q\ge 0$ for each $u,v\in V,q=1,2,3$

  • $f_{ab}^1\ge 0$
  • $f_{ab}^2\ge 0$
  • $f_{ab}^3\ge 0$
  • $f_{aq}^1\ge 0$
  • .. etc

2

By transitivity, we can ensure they all sum to $0$:

$$\begin{array}{rl}{f}_{bp}^1-f_{bp}^2& =0\\ f_{bp}^1-f_{bp}^3& =0\end{array}$$

3

This would only let commodity $3$ use edge $(b,p)$:

$$\begin{array}{r}{f}_{bp}^1+f_{bp}^2=0\end{array}$$

But we want only ‘one’ commodity (so any of them):

1. We define binary variables $x_1$, $x_2$, $x_3$ (which commodity is selected).
2. Then we add a constraint to enforce only one is selected: $x_1+x_2+x_3\le 1$
3. Finally, we add constraints to allow one of the commodities to use the edge: $\begin{array}{rl}{f}_{bp}^1-3x_1& \le 0\\ f_{bp}^2-7x_1& \le 0\\ f_{bp}^3-4x_1& \le 0\end{array}$

Using binary variables is a standard way to add this sort of control flow in optimisation problems.