I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient algorithms that solve this problem directly, so I am trying to think of a way to transform the problem so that it can be passed to standard max-flow algorithms that assume all arc capacities are non-negative.
The only hint I could find online was a question in a 1999 homework assignment which asks students to "Show how to reduce the problem of maximum flow with possibly negative capacities to two maximum flow problems both with nonnegative capacities." (The original can be seen here: http://www.cs.cmu.edu/afs/cs/academic/class/15750-s99/www/homeworks/hw4.ps )
How can this be done?
Edit #1: I should explain the origin of these ((u,v),(v,u)) pairs. What I am really trying to do is solve an s-t maximum flow in a graph that is essentially undirected. By "essentially undirected" I mean a graph that is undirected except for arcs with source s and target in the undirected graph, and arcs with source in the undirected graph and target t. Of course, this kind of "partially directed" graph must be translated into a normal directed graph for any s-t max flow algorithm. To do this, I am applying the standard transformation of replacing every undirected edge (u<->v) (with weight c) with a pair of directed arcs (u->v) and (v->u) with weight c. Since the original graph sometimes has negative edge weights, these ((u,v),(v,u)) pairs with equal negative weights arise.
Best Answer
The correspondence between max flow with lower capacities and max flow with negative capacities as described in the linked homework problem is based on the convention that $f(u,v)=-f(v,u)$ for all arc pairs $\{(u,v),(v,u)\}$. http://computingscience.nl/docs/vakken/an/an-maxflow.ppt contains a reduction of max flow with lower capacities to the solution of two standard max flow problems, thus solving the homework question. If I understand your problem correctly, it is a bit more complicated: A weight of $-7$ on an (undirected) edge $\{u,v\}$ means that you want to send at least 7 units of flow either from $u$ to $v$ or from $v$ to $u$. As far as I can see, for this problem the standard transformation of replacing the edge by an arc pair does not work. In the standard case only one of the arcs $(u,v)$ and $(v,u)$ is used in an optimal solution, and its flow value can be used as the value for the undirected edge. But how would you transfer $f(u,v)=-9$, $f(v,u)=-12$ back to the undirected model?
Practically, the first thing I would try is to write the original problem as a mixed integer program (I guess you have to model the choices for the arc directions with binary variables) and throw it into a general purpose solver (Cplex, Gurobi, http://zibopt.zib.de, http://www.coin-or.org/ ).