In this network flow problem we deal with two distinct commodities, each commodity being identified by a pair of source and sink nodes. The problem consists of maximizing the total flow (biflow) of the two commodities. It is solved by an inductive algorithm which starts with a maximal multiterminal flow from the set of sources to the set of sinks in the network, yields the value of the maximal biflow and terminates with the construction of the maximal biflow itself. Computational experience shows that this algorithm can also be used in the three-commodity flow problem to obtain a good lower bound for the value of a maximal three-commodity flow.
PDF