Solving the convex cost integer dual network flow problem
Abstract
In this paper, we consider an integer convex optimization problem where the objective function is the sum
of separable convex functions (that is, of the form \sum _{(i,j)}
F_{ij}(w_{ij}) + \sum _j B_j(x_j) ), the constraints are similar to
those arising in the dual of a minimum cost flow problem (that is, of
the form x_i - x_j \leq wij), with lower and upper bounds on variables.
Let n = |P|, m = |Q|, and U be the largest magnitude in the lower and
upper bounds of variables. We call this problem the 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 dial-a-ride transit problems, 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 to 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 in O(nm log n log(nU)) time using a cost-scaling algorithm,
which is the best available time bound to solve the convex cost integer
dual network flow problem.
Download Information
Click on the following title to view and download the paper in PostScript format.
No download available, as per copyrights contract.
hochbaum@ieor.berkeley.edu
10/30/02