Shortest paths

The single-source shortest-paths problem, described in Chapter 24, can be formulated as a linear program. In this section, we shall focus on the formulation of the single-pair shortest-path problem, leaving the extension to the more general single-source shortest-paths problem as Exercise 29.2-3.

In the single-pair shortest-path problem, we are given a weighted, directed graph G = (V, E), with weight function w : E → R mapping edges to real-valued weights, a source vertex s, and a destination vertex t. We wish to compute the value d[t], which is the weight of a shortest path from s to t. To express this problem as a linear program, we need to determine a set of variables and constraints that define when we have a shortest path from s to t. Fortunately, the Bellman-Ford algorithm does exactly this. When the Bellman-Ford algorithm terminates, it has computed, for each vertex v, a value d[v] such that for each edge (u, v) ∈ E, we have d[v] ≤ d[u] + w(u, v). The source vertex initially receives a value d[s] = 0, which is never changed. Thus we obtain the following linear program to compute the shortest-path weight from s to t:

subject to

In this linear program, there are |V | variables d[v], one for each vertex v ∈ V . There are |E| + 1 constraints, one for each edge plus the additional constraint that the source vertex always has the value 0.

Maximum flow

The maximum-flow problem can also be expressed as a linear program. Recall that we are given a directed graph G = (V, E) in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0, and two distinguished vertices, a sink s and a source t. As defined in Section 26.1, a flow is a real-valued function f : V × V → R that satisfies three properties: capacity constraints, skew symmetry, and flow conservation. A maximum flow is a flow that satisfies these constraints and maximizes the flow value, which is the total flow coming out of the source. A flow, therefore, satisfies linear constraints, and the value of a flow is a linear function. Recalling also that we assume that c(u, v) = 0 if (u, v) ∉ E, we can express the maximum-flow problem as a linear program:

subject to

This linear program has |V|² variables, corresponding to the flow between each pair of vertices, and it has 2|V|² + |V| - 2 constraints.

It is usually more efficient to solve a smaller-sized linear program. The linear program in (29.47)-(29.50) has, for ease of notation, a flow and capacity of 0 for each pair of vertices u, v with (u, v) ∉ E. It would be more efficient to rewrite the linear program so that it has O(V + E) constraints. Exercise 29.2-5 asks you to do so.

Minimum-cost flow

In this section, we have used linear programming to solve problems for which we already knew efficient algorithms. In fact, an efficient algorithm designed specifically for a problem, such as Dijkstra's algorithm for the single-source shortest-paths problem, or the push-relabel method for maximum flow, will often be more efficient than linear programming, both in theory and in practice.

The real power of linear programming comes from the ability to solve new problems. Recall the problem faced by the politician in the beginning of this chapter. The problem of obtaining a sufficient number of votes, while not spending too much money, is not solved by any of the algorithms that we have studied in this book, yet it is solved by linear programming. Books abound with such real-world problems that linear programming can solve. Linear programming is also particularly useful for solving variants of problems for which we may not already know of an efficient algorithm.

Consider, for example, the following generalization of the maximum-flow problem. Suppose that each edge (u, v) has, in addition to a capacity c(u, v), a real-valued cost a(u, v). If we send f (u, v) units of flow over edge (u, v), we incur a cost of a(u, v) f (u, v). We are also given a flow target d. We wish to send d units of flow from s to t in such a way that the total cost incurred by the flow, Σ_{(u, v)∈E} a(u, v)f(u v), is minimized. This problem is known as the minimum-cost-flow problem.

Figure 29.3(a) shows an example of the minimum-cost-flow problem. We wish to send 4 units of flow from s to t, while incurring the minimum total cost. Any particular legal flow, that is, a function f satisfying constraints (29.48)-(29.50), incurs a total cost of Σ_{(u, v)∈E} a(u, v) f (u, v). We wish to find the particular 4-unit flow that minimizes this cost. An optimal solution is given in Figure 29.3(b), and it has total cost Σ_{(u, v)∈E} a(u, v) f (u, v) = (2·2)+(5·2)+(3·1)+(7·1)+(1·3) = 27.

There are polynomial-time algorithms specifically designed for the minimum-cost-flow problem, but they are beyond the scope of this book. We can, however, express the minimum-cost-flow problem as a linear program. The linear program looks similar to the one for the maximum-flow problem with the additional constraint that the value of the flow be exactly d units, and with the new objective function of minimizing the cost:

subject to

Multicommodity flow

As a final example, we consider another flow problem. Suppose that the Lucky Puck company from Section 26.1 decides to diversify its product line and ship not only hockey pucks, but also hockey sticks and hockey helmets. Each piece of equipment is manufactured in its own factory, has its own warehouse, and must be shipped, each day, from factory to warehouse. The sticks are manufactured in Vancouver and must be shipped to Saskatoon, and the helmets are manufactured in Edmonton and must be shipped to Regina. The capacity of the shipping network does not change, however, and the different items, or commodities, must share the same network.

This example is an instance of a multicommodity-flow problem. In this problem, we are again given a directed graph G = (V, E) in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0. As in the maximum-flow problem, we implicitly assume that c(u, v) = 0 for (u, v) ∉ E. In addition, we are given k different commodities, K₁, K₂, ..., K_k, where commodity i is specified by the triple K_i = (s_i, t_i, d_i). Here, s_i is the source of commodity i, t_i is the sink of commodity i, and d_i is the demand, which is the desired flow value for commodity i from s_i to t_i. We define a flow for commodity i, denoted by f_i, (so that f_i(u, v) is the flow of commodity i from vertex u to vertex v) to be a real-valued function that satisfies the flow-conservation, skew-symmetry, and capacity constraints. We now define f (u, v), the aggregate flow, to be sum of the various commodity flows, so that . The aggregate flow on edge (u, v) must be no more than the capacity of edge (u, v). This constraint subsumes the capacity constraints for the individual commodities. The way this problem is described, there is nothing to minimize; we need only determine whether it is possible to find such a flow. Thus, we write a linear program with a "null" objective function:

The only known polynomial-time algorithm for this problem is to express it as a linear program and then solve with a polynomial-time linear-programming algorithm.