0
$\begingroup$

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?

enter image description here

New contributor
diabolik is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – prubin yesterday

Your Answer

diabolik is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.