Mincost Flows

It 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 unit-capacity 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 mincost-flow problem, which is the subject of this section. As with the maxflow problem, there are numerous equivalent ways to pose the mincost-flow problem. We consider one standard formulation in detail in this section, then consider various reductions in . Specifically, we use the mincost-maxflow 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 problem-solving 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 upper-bound 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 augmenting-path algorithm for the maxflow problem.

Screenshot Maxflows in flow networks with costs

These 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).

Java graphics 22fig40.gif


Numerous other problems reduce to or are equivalent to the mincost-maxflow problem. For example, the following formulation is of interest because it encompasses the merchandise-distribution 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–feasible-flow 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 merchandise-distribution 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.

Computing flow cost

This method, to be added to Program 22.1, returns the cost of a network's flow. It sums cost times flow for all positive-capacity edges, allowing for uncapacitated edges to be used as dummy edges.

static int cost(Network G)
{ int x = 0;
 for (int v = 0; v < G.V(); v++)
 {
 AdjList A = G.getAdjList(v);
 for (Edge e = A.beg(); !A.end(); e = A.nxt())
 if (e.from(v) && e.costRto(e.w()) < Edge.C)
 x += e.flow()*e.costRto(e.w());
 }
 return x;
}

Property 22.22 The mincost–feasible-flow problem and the mincost-maxflow problems are equivalent. Proof: Immediate, by the same correspondence as Property 22.18 (see also Exercise 22.76). Screenshot


Because of this equivalence and because the mincost–feasible-flow problem directly models merchandise-distribution 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 mincost-flow 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 u-v in the original, let f be the flow, c the capacity, and x the cost. If f is positive, include an edge v-u in the residual with capacity f and cost -x; if f is less than c, include an edge u-v in the residual with capacity c-f 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 negative-cost cycles. The concept of negative cycles, which seemed artificial when we first considered it in the context of shortest-paths algorithms, plays a critical role in mincost-flow 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 negative-cost (directed) cycle. Proof: Suppose that we have a mincost maxflow whose residual network has a negative-cost cycle. Let x be the capacity of a minimal-capacity edge in the cycle. Augment the flow by adding x to edges in the flow corresponding to positive-cost edges in the residual network (forward edges) and subtracting x from edges corresponding to negative-cost 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 Java graphics f.gif with no negative-cost cycles whose cost is not minimal, and consider any mincost maxflow Java graphics m.gif. By an argument identical to the flow-decomposition theorem (Property 22.2), we can find at most E directed cycles such that adding those cycles to the flow Java graphics f.gif gives the flow Java graphics m.gif. But, since Java graphics f.gif has no negative cycles, this operation cannot lower the cost of Java graphics f.gif, a contradiction. In other words, we should be able to convert Java graphics f.gif to Java graphics m.gif by augmenting along cycles, but we cannot do so because we have no negative-cost cycles to use to lower the flow cost. Screenshot


This property leads immediately to a simple generic algorithm for solving the mincost-flow problem, called the cycle-canceling algorithm:

Find a maxflow. Augment the flow along any negative-cost cycle in the residual network, continuing until none remain.

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 mincost-flow 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 negative-cost cycles are not specified. Screenshot shows an example mincost-maxflow 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 4-1-0-2-4 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 3-2-4-1-3 in the first step would have brought us to the mincost flow in one step.

Java graphics 22fig41.jpg


Since we have already developed algorithms for computing a maxflow and for finding negative cycles, we immediately have the implementation of the cycle-canceling 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 cycle-canceling 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 mincost-flow 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 maxflow

This sequence illustrates the computation of a mincost maxflow from an initially empty flow with the cycle-canceling 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 augmenting-path 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 1-4-5-3-1 instead of 0-1-4-5-0 in the second step. Since every augmentation either increases the flow or reduces the cost, we always wind up with a mincost maxflow.

Java graphics 22fig42.gif


Cycle canceling

This class solves the mincost-maxflow problem by canceling negative-cost cycles. It uses a NetworkMaxFlow object to find a maxflow and a private member method negcyc (see Exercise 22.108) to find negative cycles. While a negative cycle exists, this code finds one, computes the maximum amount of flow to push through it, and does so. The augment method is the same as in Program 22.3, which was coded (with some foresight!) to work properly when the path is a cycle.

class NetworkMinCost
{ private Network G; private int s, t;
 private Edge[] st;
 private int ST(int v) { return st[v].other(v); }
 private void augment(int s, int t)
 // See Program 22.3
 private int negcyc()
 // See Exercise 22.108
 NetworkMinCost(Network G, int s, int t)
 { this.G = G; this.s = s; this.t = t;
 st = new Edge[G.V()];
 NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
 for (int x = negcyc(); x != -1; x = negcyc())
 { augment(x, x); }
 }
}

Technically, using a dummy-flow initialization is neither more nor less generic than using a maxflow initialization for cycle canceling. The former does encompass all augmenting-path maxflow algorithms, but not all maxflows can be computed with an augmenting-path 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, dummy-flow initialization is widely used because it is so simple to implement. As for maxflows, the existence of this generic algorithm guarantees that every mincost-flow 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 cycle-canceling algorithm will require. Property 22.24 The number of augmenting cycles needed in the generic cycle-canceling 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. Screenshot


Corollary The time required to solve the mincost-flow problem in a sparse network is O(V3CM). Proof: Immediate by multiplying the worst-case number of augmenting cycles by the worst-case cost of the Bellman–Ford algorithm for finding them (see Property 21.22). Screenshot


Like that of augmenting-path methods, this running time is extremely pessimistic, as it assumes not only that we have a worst-case situation where we need to use a huge number of cycles to minimize cost, but also that we have another worst-case 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 cycle-canceling algorithm is effective. It is possible to develop a strategy that finds negative-cost cycles and ensures that the number of negative-cost cycles used is less than VE (see reference section). This result is significant because it establishes the fact that the mincost-flow 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 worst-case bounds. The mincost-flow problem represents the most general problem-solving 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 cycle-canceling 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

Expand your class for feasible flows from Exercise 22.74 to include costs. Use a NetworkMinCost object to solve the mincost–feasible-flow problem.

Java graphics ltr.gif 22.106 Given a flow network whose edges are not all maximal capacity and cost, give an upper bound better than ECM on the cost of a maxflow.

Prove that, if all capacities and costs are integers, then the mincost-flow problem has a solution where all flow values are integers.

Implement the negcyc() method for Program 22.9, using the Bellman–Ford algorithm (see Exercise 21.134).

Java graphics ltr.gif 22.109 Modify Program 22.9 to initialize with flow in a dummy edge instead of computing a flow.

Screenshot 22.110 Give all possible sequences of augmenting cycles that might have been depicted in Screenshot.

Screenshot 22.111 Give all possible sequences of augmenting cycles that might have been depicted in Screenshot.

Show, in the style of Screenshot, the flow and residual networks after each augmentation when you use the cycle-canceling implementation of Program 22.9 to find a mincost flow in the flow network shown in Screenshot, with cost 2 assigned to 0-2 and 0-3; cost 3 assigned to 2-5 and 3-5; cost 4 assigned to 1-4; and cost 1 assigned to all of the other edges. Assume that the maxflow is computed with the shortest-augmenting-path algorithm.

Answer Exercise 22.112, but assume that the program is modified to start with a maxflow in a dummy edge from source to sink, as in Screenshot.

Extend your solutions to Exercises 22.6 and 22.7 to handle costs in flow networks.

Extend your solutions to Exercises 22.9 through 22.11 to include costs in the networks. Take each edge's cost to be roughly proportional to the Euclidean distance between the vertices that the edge connects.



   
Comments