First of all, a multicommodity flow problem is not NP-complete
provided that the individual flows are an order of magnitude or so
smaller than the link capacities so that you can use a fluid approximation.
Moreover, you can come up with a heuristic that works pretty well. I believe
you
must have heard of greedy algorithms.
It is **so** easy to label a problem NP complete these days.
Bora