Abstract:
A transport network has to connect a specified set of drains with the source. The network is allowed to branch only in the source and drain points and the dependence of the cost of a network element on the flow through it is unknown in advance. A dynamic programming algorithm is proposed whereby the cost determination is an element are operation. When the cost depends linearly on the flow, a branch-and-bound algorithm of dynamic programming is used.