Solving the Convex Cost Integer Dual Network Flow Problem

Ravindra K. Ahuja (), Dorit S. Hochbaum () and James B. Orlin ()
Additional contact information
Ravindra K. Ahuja: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Dorit S. Hochbaum: Department of IE and OR, and Haas School of Business, University of California, Berkeley, California 94720
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Management Science, 2003, vol. 49, issue 7, 950-964

Abstract: 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 \sum (i,j)\epsilonQ F\bar ij (w ij ) + \sum i\epsilonP B\bar i (\mu i )), the constraints are similar to those arising in the dual of a minimum cost flow problem (that is, of the form \mu i - \mu j \le w ij , (i,j)\in 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.

Keywords: Minimum Cost Flow; Convex Cost Flow; Lagrangian Relaxation; Scaling Algorithm; Duality Theory; Integer Programming (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.49.7.950.16384 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:49:y:2003:i:7:p:950-964

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().