# Defining multi commodity flows as polytopes

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.

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.