Previous Next 
MincostFlow ReductionsMincost flow is a general problemsolving model that can encompass a variety of useful practical problems. In this section, we substantiate this claim by proving specific reductions from a variety of problems to mincost flow. The mincostflow problem is obviously more general than the maxflow problem, since any mincost maxflow is an acceptable solution to the maxflow problem. Specifically, if we assign to the dummy edge a cost 1 and to all other edges a cost 0 in the construction of Screenshot, any mincost maxflow minimizes the flow in the dummy edge and therefore maximizes the flow in the original network. Therefore, all the problems discussed in that reduce to the maxflow problem also reduce to the mincostflow problem. This set of problems includes bipartite matching, feasible flow, and mincut, among numerous others. More interesting, we can examine properties of our algorithms for the mincostflow problem to develop new generic algorithms for the maxflow problem. We have already noted that the generic cyclecanceling algorithm for the mincostmaxflow problem gives a generic augmentingpath algorithm for the maxflow problem. In particular, this approach leads to an implementation that finds augmenting paths without having to search the network (see Exercises 22.133 and 22.134). On the other hand, the algorithm might produce zeroflow augmenting paths, so its performance characteristics are difficult to evaluate (see reference section). The mincostflow problem is also more general than the shortestpaths problem, by the following simple reduction: Property 22.29 The singlesource–shortestpaths problem (in networks with no negative cycles) reduces to the mincost–feasibleflow problem. Proof: Given a singlesource–shortestpaths problem (a network and a source vertex s), build a flow network with the same vertices, edges, and edge costs; and give each edge unlimited capacity. Add a new source vertex with an edge to s that has cost zero and capacity V1 and a new sink vertex with edges from each of the other vertices with costs zero and capacities 1. This construction is illustrated in Screenshot. Screenshot Reduction from shortest pathsFinding a singlesource–shortestpaths tree in the network at the top is equivalent to solving the mincostmaxflow problem in the flow network at the bottom. Solve the mincost–feasibleflow problem on this network. If necessary, remove cycles in the solution to produce a spanningtree solution. This spanning tree corresponds directly to a shortestpaths spanning tree of the original network. Detailed proof of this fact is left as an exercise (see Exercise 22.138). Thus, all the problems discussed in that reduce to the singlesource–shortestpaths problem also reduce to the mincostflow problem. This set of problems includes job scheduling with deadlines and difference constraints, among numerous others. As we found when studying maxflow problems, it is worthwhile to consider the details of the operation of the network simplex algorithm when solving a shortestpaths problem using the reduction of Property 22.29. In this case, the algorithm maintains a spanning tree rooted at the source, much like the searchbased algorithms that we considered in , but the node potentials and reduced costs provide increased flexibility in developing methods to choose the next edge to add to the tree. We do not generally exploit the fact that the mincostflow problem is a proper generalization of both the maxflow and the shortestpaths problems, because we have specialized algorithms with better performance guarantees for both problems. If such implementations are not available, however, a good implementation of the network simplex algorithm is likely to produce quick solutions to particular instances of both problems. Of course, we must avoid reduction loops when using or building networkprocessing systems that take advantage of such reductions. For example, the cyclecanceling implementation in Program 22.9 uses both maxflow and shortest paths to solve the mincostflow problem (see Exercise 21.96). Next, we consider equivalent network models. First, we show that assuming that costs are nonnegative is not restrictive, as we can transform networks with negative costs into networks without them. Property 22.30 In mincostflow problems, we can assume, without loss of generality, that edge costs are nonnegative. Proof: We prove this fact for feasible mincost flows in distribution networks. The same result is true for mincost maxflows because of the equivalence of the two problems proved in Property 22.22 (see Exercises 22.143 and 22.144). Given a distribution network, we replace any edge uv that has cost x < 0 and capacity c by an edge vu of the same capacity that has cost –x (a positive number). Furthermore, we can decrement the supplydemand value of u by c and increment the supplydemand value of v by c. This operation corresponds to pushing c units of flow from u to v and adjusting the network accordingly. For negativecost edges, if a solution to the mincostflow problem for the transformed network puts flow f in the edge vu, we put flow c – f in uv in the original network; for positivecost edges, the transformed network has the same flow as in the original. This flow assignment preserves the supply or demand constraint at all the vertices. The flow in vu in the transformed network contributes fx to the cost and the flow in uv in the original network contributes –cx + fx to the cost. The first term in this expression does not depend on the flow, so the cost of any flow in the transformed network is equal to the cost of the corresponding flow in the original network plus the sum of the products of the capacities and costs of all the negativecost edges (which is a negative quantity). Any minimalcost flow in the transformed network is therefore a minimalcost flow in the original network. This reduction shows that we can restrict attention to positive costs, but we generally do not bother to do so in practice because our implementations in s 22.5 and 22.6 work exclusively with residual networks and handle negative costs with no difficulty. It is important to have some lower bound on costs in some contexts, but that bound does not need to be zero (see Exercise 22.145). Next, we show, as we did for the maxflow problem, that we could, if we wanted, restrict attention to acyclic networks. Moreover, we can also assume that edges are uncapacitated (there is no upper bound on the amount of flow in the edges). Combining these two variations leads to the following classic formulation of the mincostflow problem: Transportation Solve the mincostflow problem for a bipartite distribution network where all edges are directed from a supply vertex to a demand vertex and have unlimited capacity. As discussed at the beginning of this chapter (see Screenshot), the usual way to think of this problem is as modeling the distribution of goods from warehouses (supply vertices) to retail outlets (demand vertices) along distribution channels (edges) at a certain cost per unit amount of goods. Property 22.31 The transportation problem is equivalent to the mincostflow problem. Proof: Given a transportation problem, we can solve it by assigning a capacity for each edge higher than the supply or demand values of the vertices that it connects and solving the resulting mincost–feasibleflow problem on the resulting distribution network. Therefore, we need only to establish a reduction from the standard problem to the transportation problem. For variety, we describe a new transformation, which is linear only for sparse networks. A construction similar to the one that we used in the proof of Property 22.16 establishes the result for nonsparse networks (see Exercise 22.148). Given a standard distribution network with V vertices and E edges, build a transportation network with V supply vertices, E demand vertices, and 2E edges, as follows: For each vertex in the original network, include a vertex in the bipartite network with supply or demand value set to the original value plus the sum of the capacities of the outgoing edges; and for each edge uv in the original network with capacity c, include a vertex in the bipartite network with supply or demand value c (we use the notation [uv] to refer to this vertex). For each edge uv in the original network, include two edges in the bipartite network: one from u to [uv] with the same cost, and one from v to [uv] with cost 0. The following onetoone correspondence preserves costs between flows in the two networks: An edge uv has flow value f in the original network if and only if edge u[uv] has flow value f, and edge v[uv] has flow value cf in the bipartite network (those two flows must sum to c because of the supply–demand constraint at vertex [uv]. Thus, any mincost flow in one network corresponds to a mincost flow in the other. Since we have not considered direct algorithms for solving the transportation problem, this reduction is of academic interest only. To use it, we would have to convert the resulting problem back to a (different) mincostflow problem, using the simple reduction mentioned at the beginning of the proof of Property 22.31. Perhaps such networks admit more efficient solutions in practice; perhaps they do not. The point of studying the equivalence between the transportation problem and the mincostflow problem is to understand that removing capacities and restricting attention to bipartite networks would seem to simplify the mincostflow problem substantially; however, that is not the case. We need to consider another classical problem in this context. It generalizes the bipartitematching problem that is discussed in detail in . Like that problem, it is deceptively simple. Assignment Given a weighted bipartite graph, find a set of edges of minimum total weight such that each vertex is connected to exactly one other vertex. For example, we might generalize our jobplacement problem to include a way for each company to quantify its desire for each applicant (say by assigning an integer to each applicant, with lower integers going to the better applicants) and for each applicant to quantify his or her desire for each company. Then, a solution to the assignment problem would provide a reasonable way to take these relative preferences into account. Property 22.32 The assignment problem reduces to the mincostflow problem. Proof: This result can be established via a simple reduction to the transportation problem. Given an assignment problem, construct a transportation problem with the same vertices and edges, with all vertices in one of the sets designated as supply vertices with value 1 and all vertices in the other set designated as demand vertices with value 1. Assign capacity 1 to each edge, and assign a cost corresponding to that edge's weight in the assignment problem. Any solution to this instance of the transportation problem is simply a set of edges of minimal total cost that each connect a supply vertex to a demand vertex and therefore corresponds directly to a solution to the original assignment problem. Reducing this instance of the transportation problem to the mincostmaxflow problem gives a construction that is essentially equivalent to the construction that we used to reduce the bipartitematching problem to the maxflow problem (see Exercise 22.158). This relationship is not known to be an equivalence. There is no known way to reduce a general mincostflow problem to the assignment problem. Indeed, like the singlesource–shortestpaths problem and the maxflow problem, the assignment problem seems to be easier than the mincostflow problem in the sense that there are algorithms known that solve it that have better asymptotic performance than the best known algorithms for the mincostflow problem. Still, the network simplex algorithm is sufficiently well refined that a good implementation of it is a reasonable choice for solving assignment problems. Moreover, as with maxflow and shortest paths, we can tailor the network simplex algorithm to get improved performance for the assignment problem (see reference section). Our next reduction to the mincostflow problem brings us back to a basic problem related to paths in graphs like the ones that we first considered in . As in the Eulerpath problem, we want a path that includes all the edges in a graph. Recognizing that not all graphs have such a path, we relax the restriction that edges must appear only once. Mail carrier Given a network (weighted digraph), find a cyclic path of minimal weight that includes each edge at least once (see Screenshot). Recall that our basic definitions in make the distinction between cyclic paths (which may revisit vertices and edges) and cycles (which consist of distinct vertices, except the first and the final, which are the same). Screenshot Mail carrier's problemFinding the shortest path that includes each edge at least once is a challenge even for this small network, but the problem can be solved efficiently through reduction to the mincostflow problem. The solution to this problem would describe the best route for a mail carrier (who has to cover all the streets on her route) to follow. A solution to this problem might also describe the route that a snowplow should take during a snowstorm, and there are many similar apps. The mail carrier's problem is an extension of the Eulertour problem that we discussed in : The solution to Exercise 17.92 is a simple test for whether a digraph has an Euler tour, and Program 17.14 is an effective way to find an Euler tour for such digraphs. That tour solves the mail carrier's problem because it includes each edge exactly once—no path could have lower weight. The problem becomes more difficult when indegrees and outdegrees are not necessarily equal. In the general case, some edges must be traversed more than once: The problem is to minimize the total weight of all the multiply traversed edges. Property 22.33 The mail carrier's problem reduces to the mincostflow problem. Proof: Given an instance of the mail carrier's problem (a weighted digraph), define a distribution network on the same vertices and edges, with all the vertex supply or demand values set to 0, edge costs set to the weights of the corresponding edge, and no upper bounds on edge capacities, but all edge capacities constrained to be greater than 1. We interpret a flow value f in an edge uv as saying that the mail carrier needs to traverse uv a total of f times. Find a mincost flow for this network by using the transformation of Exercise 22.146 to remove the lower bound on edge capacities. The flowdecomposition theorem says that we can express the flow as a set of cycles, so we can build a cyclic path from this flow in the same way that we built an Euler tour in an Eulerian graph: We traverse any cycle, taking a detour to traverse another cycle whenever we encounter a node that is on another cycle. A careful look at the mail carrier's problem illustrates yet again the fine line between trivial and intractable graph algorithms. Suppose that we consider the twoway version of the problem where the network is undirected, and the mail carrier must travel in both directions along each edge. Then, as we noted in , depthfirst search (or any graph search) will provide an immediate solution. If, however, it suffices to traverse each undirected edge in either direction, then a solution is significantly more difficult to formulate than is the simple reduction to mincost flow that we just examined, but the problem is still tractable. If some edges are directed and others undirected, the problem becomes NPhard (see reference section). These are only a few of the scores of practical problems that have been formulated as mincostflow problems. The mincostflow problem is even more versatile than the maxflow problem or shortestpaths problems, and the network simplex algorithm effectively solves all problems encompassed by the model. As we did when we studied maxflow, we can examine how any mincostflow problem can be cast as an LP problem, as illustrated in Screenshot. The formulation is a straightforward extension of the maxflow formulation: We add equations that set a dummy variable to be equal to the cost of the flow, then set the objective so as to minimize that variable. LP models allow addition of arbitrary (linear) constraints. Some constraints may lead to problems that still may be equivalent to mincostflow problems, but others do not. That is, many problems do not reduce to mincostflow problems: In particular, LP encompasses a much broader set of problems. The mincostflow problem is a next step toward that general problemsolving model, which we consider in Part 8. Screenshot LP formulation of a mincostmaxflow problemThis linear program is equivalent to the mincostmaxflow problem for the sample network of Screenshot. The edge equalities and vertex inequalities are the same as in Screenshot, but the objective is different. The variable c represents the total cost, which is a linear combination of the other variables. In this case, c = –9x_{50} + 3x_{01} + x_{02} + x_{13} + x_{14} + 4x_{23} + 2x_{24} + 2x_{35} + x_{45}. There are other models that are even more general than the LP model; but LP has the additional virtue that, while LP problems are in general more difficult than mincostflow problems, effective and efficient algorithms have been invented to solve them. Indeed, perhaps the most important such algorithm is known as the simplex method: The network simplex method is a specialized version of the simplex method that applies to the subset of LP problems that correspond to mincostflow problems. Understanding the network simplex algorithm is a helpful first step in understanding the simplex algorithm. Exercises

Previous Next 