Premium
Solving the undirected minimum cost flow problem with arbitrary costs
Author(s) -
SedeñoNoda A.,
GonzálezMartín C.,
Alonso S.
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20042
Subject(s) - minimum cost flow problem , multi commodity flow problem , flow (mathematics) , mathematical optimization , flow network , maximum flow problem , property (philosophy) , integer (computer science) , computer science , mathematics , philosophy , geometry , epistemology , programming language
We address the undirected minimum cost flow problem with arbitrary arcs costs. Any optimal solution for this problem is characterized by the property that the flow of each arc with negative cost must be equal to its capacity. That is, the flow can be nonzero in both directions. This situation implies that the flow can take values that are integer multiple of ½. Therefore, this single commodity flow problem does not satisfy the unimodularity property. However, using a reformulation of the original problem, we develop an easy method for solving it using any classical minimum‐cost flow problem algorithm. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 1–3 2005