# Minimum cost flow problem with negative cost arcs

As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc with the negative cost, we can't get to node 4 or node 1. How do you think I should approach this?

No, making the change you describe could make the problem infeasible, as you observed for this instance. Instead, just think of the negative cost as a reward. If using the arc will reduce the overall cost, then the solver will exploit that.

• Caveat: This works when there are no negative cycles, which is true here. If you change the cost of arc (3, 4) to, say, -6, you will get an infinite flow (or one hapless unit of flow doing the 1 -> 3 -> 4 -> 1 loop for the rest of eternity). If you are stuck with a negative cycle, you could be saved by bounds on the flows (but would still have to explain flow taking laps through the negative cycles). Jan 13 at 23:46