29-5 Minimum-cost circulation

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, v)\) 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, v) \in E\), we have \(a(u, v) > 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.

a. This is exactly the linear program given in equations \(\text{(29.51)}\)-\(\text{(29.52)}\) except that the equation on the third line of the constraints should be removed, and for the equation on the second line of the constraints, \(u\) should be selected from all of \(V\) instead of from \(V \backslash \\{s, t\\}\).

b. If \(a(u, v) > 0\) for every pair of vertices, then, there is no point in sending any flow at all. So, an optimal solution is just to have no flow. This obviously satisfies the capacity constraints, it also satisfies the conservation constraints because the flow into and out of each vertex is zero.

c. We assume that the edge \((t, s)\) is not in \(E\) because that would be a silly edge to have for a maximum flow from \(s\) to \(t\). If it is there, remove it and it won't decrease the maximum flow. Let \(V' = V\) and \(E' = E \cup \\{(t, s)\\}\). For the edges of \(E'\) that are in \(E\), let the capacity be as it is in \(E\) and let the cost be \(0\). For the other edge, we set \(c(t, s) = \infty\) and \(a(t, s) = -1\). Then, if we have any circulation in \(G'\), it will be trying to get as much flow to go across the edge \((t, s)\) in order to drive the objective function lower, the other flows will have no affect on the objective function. Then, by Kirchhoff's current law (a.k.a. common sense), the amount going across the edge \((t, s)\) is the same as the total flow in the rest of the network from \(s\) to \(t\). This means that maximizing the flow across the edge \((t, s)\) is also maximizing the flow from \(s\) to \(t\). So, all we need to do to recover the maximum flow for the original network is to keep the same flow values, but throw away the edge \((t, s)\).

d. Suppose that \(s\) is the vertex that we are computing shortest distance from. Then, we make the circulation network by first starting with the original graph, giving each edge a cost of whatever it was before and infinite capacity. Then, we place an edge going from every vertex that isn't \(s\) to \(s\) that has a capacity of \(1\) and a cost of \(-|E|\) times the largest cost appearing among all the edge costs already in the graph. Giving it such a negative cost ensures that placing other flow through the network in order to get a unit of flow across it will cause the total cost to decrease. Then, to recover the shortest path for any vertex, start at that vertex and then go to any vertex that is sending a unit of flow to it. Repeat this until you've reached \(s\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用