In this problem, we consider a variant of the minimum-cost-flow problem from Section 29.2 in which we are not given a demand, a source, or a sink. Instead, we are given, as before, a flow network and edge costs a(u, ν). A flow is feasible if it satisfies the capacity constraint on every edge and flow conservation at every vertex. The goal is to find, among all feasible flows, the one of minimum cost. We call this problem the minimum-cost-circulation problem.

a. Formulate the minimum-cost-circulation problem as a linear program.

b. Suppose that for all edges (u, ν) ∈ E, we have a (u, ν) > 0. Characterize an optimal solution to the minimum-cost-circulation problem.

c. Formulate the maximum-flow problem as a minimum-cost-circulation problem linear program. That is given a maximum-flow problem instance G = (V, E) with source s, sink t and edge capacities c, create a minimum-cost-circulation problem by giving a (possibly different) network G′ = (V′, E′) with edge capacities c′ and edge costs a′ such that you can discern a solution to the maximum-flow problem from a solution to the minimum-cost-circulation problem.

d. Formulate the single-source shortest-path problem as a minimum-cost-circulation problem linear program.