Solving the Convex Cost Integer Dual Network Flow Problem
研究一类凸成本整数对偶网络流问题，其目标函数为可分凸函数之和，约束类似最小成本流问题的对偶形式。作者描述了该问题在拨召公交、逆生成树、项目管理和回归分析中的应用，并开发了基于网络流的算法，利用拉格朗日松弛将其转化为凸成本原始网络流问题，在O(n m log(n^2/m) log(nU))时间内求解。
In this paper 1 , we consider an integer convex optimization problem where the objective function is the sum of separable convex functions (that is, of the form ∑ (i,j)ϵQ F̄ ij (w ij ) + ∑ iϵP B̄ i (μ i )), the constraints are similar to those arising in the dual of a minimum cost flow problem (that is, of the form μ i − μ j ≤ w ij , (i,j)∈Q), with lower and upper bounds on variables. Letn= |P|,m= |Q| , andUbe the largest magnitude in the lower and upper bounds of variables. We call this problemthe convex cost integer dual network flow problem. In this paper, we describe several applications of the convex cost integer dual network flow problem arising in a dial-a-ride transit problem, inverse spanning tree problem, project management, and regression analysis. We develop network flow-based algorithms to solve the convex cost integer dual network flow problem. We show that using the Lagrangian relaxation technique, the convex cost integer dual network flow problem can be transformed into a convex cost primal network flow problem where each cost function is a piecewise linear convex function with integer slopes. Its special structure allows the convex cost primal network flow problem to be solved inO(nmlog(n 2 /m)log(nU)time. This time bound is the same time needed to solve the minimum cost flow problem using the cost-scaling algorithm, and is also is best available time bound to solve the convex cost integer dual network flow problem.