1
$\begingroup$

In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka terminals).

For example, if $\left| S \right| = 3$ we have $\binom{3}{2} = 3$ possible pairs of sinks. A demand can be of the type $\left< 1, 0,\frac{1}{2}\right>$. It translates to "Need flow $1$ for the first couple" and "need $0$ flow for the second couple" and "need $\frac{1}{2}$ for the third couple". All $3$ conditions are to be satisfied simultaneously.

For a given flow network a demand is said to be feasible if we can find a flow function to achieve it, while maintaining the capacity constraints and all normal flow rules.

We define the set of all feasible demands as $D = \left\{ d \in \mathbb{R}^{k} | d \text{ is feasible}\right\}$.

I have recently came across a statement which says $D$ can be seen as a polytope in $\mathbb{R}^{k}$, yet I find this statement a bit puzzling. Is there a proof for this, or even perhaps an intuition behind it?

(Perhaps, it is easy to show for the example of $\left| S \right| = 3$)

Note: full definitions can be seen here.

$\endgroup$

1 Answer 1

0
$\begingroup$

It is a polytope because it can be expressed as a system of linear inequalities. See https://en.wikipedia.org/wiki/Multi-commodity_flow_problem. In particular, let $d$ be a demand and $f$ a flow; there is a system of linear inequalities on $d,f$ that capture the condition that $f$ is a legal flow that achieves $d$. It follows that the set

$$S = \{(d,s) \mid f \text{ is a legal flow that achieves } d\}$$

is a convex polytope. Moreover, the set $D$ has the form $D = \{d \mid (d,s) \in S\}$, and the projection of any polytope onto fewer dimensions is itself a polytope. Therefore, $D$ is a polytope.


If that sounds like a lot to absorb, here is an elementary proof that $D$ is convex, which might help give some partial intuition:

Suppose $d_1,d_2$ are two feasible demands. Let $f_1$ be a legal flow that achieves demand $d_1$, and $f_2$ a legal flow that achieves $d_2$. Let $\lambda$ be any real number with $0 \le \lambda \le 1$. Define $d_3 = \lambda d_1+ (1-\lambda) d_2$ and $f_3 = \lambda f_1 + (1-\lambda) f_2$. It is easy to verify that $f_3$ is a legal flow, and that it achieves demand $d_3$. It follows that $d_1,d_2 \in D$, then $\lambda d_1 + (1-\lambda) d_2 \in D$, for all $\lambda$ with $0 \le lambda \le 1$. This proves that the region $D$ is convex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.