Equivalence of minimum cost circulation problem and minimum cost max flow problem

Question

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 sink t to the network, without any edges to the rest of the network. The maximum flow in this network is 0, 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.

Answer 1

Does that mean the minimum circulation problem has zero flow on every edge of the original network?

No, it does not means that, unless the lower bound capacity of every edge is equal to zero.

You need to remove the lower bound capacity. You can use the transformation done in Ahuja, page 39.