Principles of Mathematics in Operations Research

Solutions 259

In our example instance, «i is node A and £3 is node /. If we enumerate
paths (some of them is given in Figure S.14), we have

Comm. Path# Path

1 ai->fh^hh^mi->p

5 ai-»&i-»di-»/i->ji->/jh->mH-»p

6 ai->/i-»<7h->-6h->-dh->/i-».7'i->-/i>->-mi->p

7 o

8 o

9 o

10 o

11 o

M- n

H-> n

t-4 n

i-> n

>-»Zi->-ji->/ii->e>-->-c

i->ei->'(ii->Zh->-jh->-5i->6i->c

12 k

13 A;

14 jfe

15 k

16

17

18 k

19 fc

20 A;

4J4li4ra^pi->o^n4i

i->-j^/ii->ei->c!H->TOH->ni-»z

1—^- y 1—>• ^ 1—>• 6 1—>• rf i—>- m 1—> n *-> i

Fig. S.14. Some paths in our multi-commodity flow instance