Previous Next 
Mincost FlowsIt is not unusual for there to be numerous solutions to a given maxflow problem. This fact leads to the question of whether we might wish to impose some additional criteria for choosing one of them. For example, there are clearly many solutions to the unitcapacity flow problems shown in Screenshot; perhaps we would prefer the one that uses the fewest edges or the one with the shortest paths, or perhaps we would like to know whether there exists one comprising disjoint paths. Such problems are more difficult than the standard maxflow problem; they fall into a more general model known as the mincostflow problem, which is the subject of this section. As with the maxflow problem, there are numerous equivalent ways to pose the mincostflow problem. We consider one standard formulation in detail in this section, then consider various reductions in . Specifically, we use the mincostmaxflow model: We define an edge type that includes integer costs, use the edge costs to define a flow cost in a natural way, then ask for a maximal flow of minimal cost. As we learn, not only do we have efficient and effective algorithms for this problem, but also the problemsolving model is of broad applicability. Definition 22.7 The flow cost of an edge in a flow network with edge costs is the product of that edge's flow and cost. The cost of a flow is the sum of the flow costs of that flow's edges. We continue to assume that capacities are positive integers less than M. We also assume edge costs to be nonnegative integers less than C. (Disallowing negative costs is primarily a matter of convenience, as discussed in .) As before, we assign names to these upperbound values because the running times of some algorithms depend on the latter. With these basic assumptions, the problem that we wish to solve is trivial to define. Mincost maxflow Given a flow network with edge costs, find a maxflow such that no other maxflow has lower cost. Screenshot illustrates different maxflows in a flow network with costs, including a mincost maxflow. Certainly, the computational burden of minimizing cost is no less challenging than the burden of maximizing flow with which we were concerned in s 22.2 and 22.3. Indeed, costs add an extra dimension that presents significant new challenges. Even so, we can shoulder this burden with a generic algorithm that is similar to the augmentingpath algorithm for the maxflow problem. Screenshot Maxflows in flow networks with costsThese flows all have the same (maximal) value, but their costs (the sum of the products of edge flows and edge costs) differ. The maxflow in the center has minimal cost (no maxflow has lower cost). Numerous other problems reduce to or are equivalent to the mincostmaxflow problem. For example, the following formulation is of interest because it encompasses the merchandisedistribution problem that we considered at the beginning of the chapter. Mincost feasible flow Recall that we define a flow in a network with vertex weights (supply if positive, demand if negative) to be feasible if the sum of the vertex weights is negative and the difference between each vertex's outflow and inflow. Given such a network, find a feasible flow of minimal cost. To describe the network model for the mincost–feasibleflow problem, we use the term distribution network for brevity to mean "capacitated flow network with edge costs and supply or demand weights on vertices." In the merchandisedistribution app, supply vertices correspond to warehouses, demand vertices to retail outlets, edges to trucking routes, supply or demand values to the amount of material to be shipped or received, and edge capacities to the number and capacity of the trucks available for the various routes. A natural way to interpret each edge's cost is as the cost of moving a unit of flow through that edge (the cost of sending a unit of material in a truck along the corresponding route). Given a flow, an edge's flow cost is the part of the cost of moving the flow through the network that we can attribute to that edge. Given an amount of material that is to be shipped along a given edge, we can compute the cost of shipping it by multiplying the cost per unit by the amount. Doing this computation for each edge and adding the results together gives us the total shipping cost, which we would like to minimize.
Property 22.22 The mincost–feasibleflow problem and the mincostmaxflow problems are equivalent. Proof: Immediate, by the same correspondence as Property 22.18 (see also Exercise 22.76). Because of this equivalence and because the mincost–feasibleflow problem directly models merchandisedistribution problems and many other apps, we use the term mincost flow to refer to both problems in contexts where we could refer to either. We consider other reductions in . To implement edge costs in flow networks, we add an integer pcost private data field to the Edge class from and a method cost() to return its value to clients. Program 22.8 is a utility method that computes the cost of a flow in a graph built with references to such edges. As when we work with maxflows, it is also prudent to implement a method to check that inflow and outflow values are properly related at each vertex and that the data structures are consistent (see Exercise 22.12). The first step in developing algorithms to solve the mincostflow problem is to extend the definition of residual networks to include costs on the edges. Definition 22.8 Given a flow in a flow network with edge costs, the residual network for the flow has the same vertices as the original and one or two edges in the residual network for each edge in the original, defined as follows: For each edge uv in the original, let f be the flow, c the capacity, and x the cost. If f is positive, include an edge vu in the residual with capacity f and cost x; if f is less than c, include an edge uv in the residual with capacity cf and cost x. This definition is nearly identical to Definition 22.4, but the difference is crucial. Edges in the residual network that represent backward edges have negative cost. To implement this convention, we use the following method in the edge class: int costRto(int v) { return from(v) ? pcost : pcost; } Traversing backward edges corresponds to removing flow in the corresponding edge in the original network, so the cost has to be reduced accordingly. Because of the negative edge costs, these networks can have negativecost cycles. The concept of negative cycles, which seemed artificial when we first considered it in the context of shortestpaths algorithms, plays a critical role in mincostflow algorithms, as we now see. We consider two algorithms, both based on the following optimality condition. Property 22.23 A maxflow is a mincost maxflow if and only if its residual network contains no negativecost (directed) cycle. Proof: Suppose that we have a mincost maxflow whose residual network has a negativecost cycle. Let x be the capacity of a minimalcapacity edge in the cycle. Augment the flow by adding x to edges in the flow corresponding to positivecost edges in the residual network (forward edges) and subtracting x from edges corresponding to negativecost edges in the residual network (backward edges). These changes do not affect the difference between inflow and outflow at any vertex, so the flow remains a maxflow; but they change the network's cost by x times the cost of the cycle, which is negative, thereby contradicting the assertion that the cost of the original flow was minimal. To prove the converse, suppose that we have a maxflow with no negativecost cycles whose cost is not minimal, and consider any mincost maxflow . By an argument identical to the flowdecomposition theorem (Property 22.2), we can find at most E directed cycles such that adding those cycles to the flow gives the flow . But, since has no negative cycles, this operation cannot lower the cost of , a contradiction. In other words, we should be able to convert to by augmenting along cycles, but we cannot do so because we have no negativecost cycles to use to lower the flow cost. This property leads immediately to a simple generic algorithm for solving the mincostflow problem, called the cyclecanceling algorithm:
This method brings together machinery that we have developed over this chapter and the previous one to provide effective algorithms for solving the wide class of problems that fit into the mincostflow model. Like several other generic methods that we have seen, it admits several different implementations, since the methods for finding the initial maxflow and for finding the negativecost cycles are not specified. Screenshot shows an example mincostmaxflow computation that uses cycle canceling. Screenshot Residual networks (cycle canceling)Each of the flows depicted here is a maxflow for the flow network depicted at the top, but only the one at the bottom is a mincost maxflow. To find it, we start with any maxflow and augment flow around negative cycles. The initial maxflow (second from top) has a cost of 22, which is not a mincost maxflow because the residual network (shown at right) has three negative cycles. In this example, we augment along 41024 to get a maxflow of cost 21 (third from top), which still has one negative cycle. Augmenting along that cycle gives a mincost flow (bottom). Note that augmenting along 32413 in the first step would have brought us to the mincost flow in one step. Since we have already developed algorithms for computing a maxflow and for finding negative cycles, we immediately have the implementation of the cyclecanceling algorithm given in Program 22.9. We use any maxflow implementation to find the initial maxflow and the Bellman–Ford algorithm to find negative cycles (see Exercise 22.108). To these two implementations, we need to add only a loop to augment flow along the cycles. We can eliminate the initial maxflow computation in the cyclecanceling algorithm by adding a dummy edge from source to sink and assigning to it a cost that is higher than the cost of any source–sink path in the network (for example, VC) and a flow that is higher than the maxflow (for example, higher than the source's outflow). With this initial setup, cycle canceling moves as much flow as possible out of the dummy edge, so the resulting flow is a maxflow. A mincostflow computation using this technique is illustrated in Screenshot. In the figure, we use an initial flow equal to the maxflow to make plain that the algorithm is simply computing another flow of the same value but lower cost (in general, we do not know the flow value, so there is some flow left in the dummy edge at the end, which we ignore). As is evident from the figure, some augmenting cycles include the dummy edge and increase flow in the network; others do not include the dummy edge and reduce cost. Eventually, we reach a maxflow; at that point, all the augmenting cycles reduce cost without changing the value of the flow, as when we started with a maxflow. Screenshot Cycle canceling without initial maxflowThis sequence illustrates the computation of a mincost maxflow from an initially empty flow with the cyclecanceling algorithm by using a dummy edge from sink to source in the residual network with infinite capacity and infinite negative cost. The dummy edge makes any augmenting path from 0 to 5 a negative cycle (but we ignore it when augmenting and computing the cost of the flow). Augmenting along such a path increases the flow, as in augmentingpath algorithms (top three rows). When there are no cycles involving the dummy edge, there are no paths from source to sink in the residual network, so we have a maxflow (third from top). At that point, augmenting along a negative cycle decreases the cost without changing the flow value (bottom). In this example, we compute a maxflow, then decrease its cost; but that need not be the case. For example, the algorithm might have augmented along the negative cycle 14531 instead of 01450 in the second step. Since every augmentation either increases the flow or reduces the cost, we always wind up with a mincost maxflow.
Technically, using a dummyflow initialization is neither more nor less generic than using a maxflow initialization for cycle canceling. The former does encompass all augmentingpath maxflow algorithms, but not all maxflows can be computed with an augmentingpath algorithm (see Exercise 22.40). On the one hand, by using this technique, we may be giving up the benefits of a sophisticated maxflow algorithm; on the other hand, we may be better off reducing costs during the process of building a maxflow. In practice, dummyflow initialization is widely used because it is so simple to implement. As for maxflows, the existence of this generic algorithm guarantees that every mincostflow problem (with capacities and costs that are integers) has a solution where flows are all integers; and the algorithm computes such a solution (see Exercise 22.107). Given this fact, it is easy to establish an upper bound on the amount of time that any cyclecanceling algorithm will require. Property 22.24 The number of augmenting cycles needed in the generic cyclecanceling algorithm is less than ECM. Proof: In the worst case, each edge in the initial maxflow has capacity M, cost C, and is filled. Each cycle reduces this cost by at least 1. Corollary The time required to solve the mincostflow problem in a sparse network is O(V^{3}CM). Proof: Immediate by multiplying the worstcase number of augmenting cycles by the worstcase cost of the Bellman–Ford algorithm for finding them (see Property 21.22). Like that of augmentingpath methods, this running time is extremely pessimistic, as it assumes not only that we have a worstcase situation where we need to use a huge number of cycles to minimize cost, but also that we have another worstcase situation where we have to examine a huge number of edges to find each cycle. In many practical situations, we use relatively few cycles that are relatively easy to find, and the cyclecanceling algorithm is effective. It is possible to develop a strategy that finds negativecost cycles and ensures that the number of negativecost cycles used is less than VE (see reference section). This result is significant because it establishes the fact that the mincostflow problem is tractable (as are all the problems that reduce to it). However, practitioners typically use implementations that admit a bad worst case (in theory) but use substantially fewer iterations on the problems that arise in practice than predicted by the worstcase bounds. The mincostflow problem represents the most general problemsolving model that we have yet examined, so it is perhaps surprising that we can solve it with such a simple implementation. Because of the importance of the model, numerous other implementations of the cyclecanceling method and numerous other different methods have been developed and studied in detail. Program 22.9 is a remarkably simple and effective starting point, but it suffers from two defects that can potentially lead to poor performance. First, each time that we seek a negative cycle, we start from scratch. Can we save intermediate information during the search for one negative cycle that can help us find the next? Second, Program 22.9 takes just the first negative cycle that the Bellman–Ford algorithm finds. Can we direct the search towards negative cycles with particular properties? In , we consider an improved implementation, still generic, that represents a response to both of these questions. Exercises

Previous Next 