In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow:
...
The second part of the proof is showing that min-cost circulation reduces to min-cost max-flow.
Consider a network G for which we want to find a min-cost circulation. Add a source
s
and a sinkt
to the network, without any edges to the rest of the network. The maximum flow in this network is0
, therefore the min-cost max-flow is actually a min-cost circulation.
In theory, I don't understand how this works. If we add disconnected source and sink nodes, the maximum flow is trivially 0
as claimed. Does that mean the minimum circulation problem has zero flow on every edge of the original network? This seems to violate the lower bound requirement on the edges of min-cost circulation networks.
In practice, I don't know how to implement a min-cost circulation solver using a min-cost max-flow solver such as the one in Boost Graph Library (BGL) here :
#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include "../test/min_cost_max_flow_utils.hpp"
int main() {
boost::SampleGraph::vertex_descriptor s,t;
boost::SampleGraph::Graph g;
boost::SampleGraph::getSampleGraph(g, s, t);
boost::edmonds_karp_max_flow(g, s, t);
boost::cycle_canceling(g);
int cost = boost::find_flow_cost(g);
assert(cost == 29);
return 0;
}
The above BGL example solves a small min-cost max-flow problem. I can't figure out how to change the network to include lower bounds of edges as required in the min-circulation problem. Simply adding additional, disconnected dummy source and sink node gives zero flows on all edges (as expected) and solves nothing.
My questions are:
Am I missing something in the above proof?
How should I adapt the BGL min-cost max-flow solver above to solve min-circulation problems?
I'd really appreciate a concrete example with cycle canceling (or another algorithm) in BGL to verify and illustrate the reduction.