I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that graph.

Once I found the maximum possible flow I can have for my graph with the Ford-Fulkerson algorithm, do I use this information to get a basic solution for the simplex method? A basic solution is a partial tree that is linked to all the nodes in the graph, right?

Because I have multiple sources and multiple destinations in my graph. I made a super source and a super destination and then applied the Ford-Fulkerson algorithm. When trying to find the basic solution what do I do with these nodes? Do I simply revert back to the original graph?

  • $\begingroup$ This is not an answer but it is interesting that are no answers to this question after two years. I am having a similar issue and was hoping to find some answers. Seems that I will have to go back to my old notes (who knows where they are!) of Operations Research to find out how this was done. If I get them I will post it here. $\endgroup$ Commented Dec 4, 2022 at 14:27
  • $\begingroup$ Like Warm-start? $\endgroup$ Commented Dec 4, 2022 at 17:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.