Optimal Two-Commodity Flows with Non-Linear Cost Functions
研究了在共享容量约束下运输两种商品的问题，每种商品有非线性成本，提出了针对两种成本函数（绝对值成本和二次函数）的高效算法。
AbstractWe consider networks in which two different commodities have to be transported across undirected arcs, subject to a shared capacity on the arcs. For each arc and commodity there is an associated non-linear cost that depends on the amount of the commodity transported across the arc. The aim is to minimize the sum of the costs over all arcs and commodities. Efficient algorithms for solving this problem for two types of objective functions will be presented: in the first the cost depends on the absolute value of the flow and in the second the cost is a quadratic function of the flow. Previous work on multi-commodity flow has concentrated on linear cost problems or tackled non-linear cost problems with Lagrangian relaxation methods and other more general techniques. The algorithms in this paper, on the other hand, provide a very efficient way of dealing with two types of non-linear two-commodity optimal flow problems.Keywords: networksoptimizationquadratic programmingtwo-commodity flow