Principles of Mathematics in Operations Research

8.4

Solutions 257

Fig. S.13. A multi-commodity flow instance

Let us take the instance given in Figure S.13, where K = 3 and

V = {l,2,3,4,5,6,A,C,I,K,OP},

A - {a, b, c, d, e, f, g, h, i, j, k,l,m, n, o, p}.

Let us fix all capacities at 10 and all positive supplies/demands at 10 with

unit carrying costs.

a)

Cka'Eka

k a

S.t.

/ J %ka / J %ka — U*ki

aET(i) a£H(i)

k

•Kka — l^ka

Xka > 0 (integer)

In general, we have mK variables, m + nK constraints and mK simple
bounds other than the nonnegativity constraints. In our example instance, we
have