Linear programming

In the general linear-programming problem, we are given an m × n matrix A, an m-vector b, and an n-vector c. We wish to find a vector x of n elements that maximizes the objective function subject to the m constraints given by Ax ≤ b.

Although the simplex algorithm, which is the focus of Chapter 29, does not always run in time polynomial in the size of its input, there are other linear-programming algorithms that do run in polynomial time. There are several reasons that it is important to understand the setup of linear-programming problems. First, knowing that a given problem can be cast as a polynomial-sized linear-programming problem immediately means that there is a polynomial-time algorithm for the problem. Second, there are many special cases of linear programming for which faster algorithms exist. For example, as shown in this section, the single-source shortest-paths problem is a special case of linear programming. Other problems that can be cast as linear programming include the single-pair shortest-path problem (Exercise 24.4-4) and the maximum-flow problem (Exercise 26.1-8).

Sometimes we don't really care about the objective function; we just wish to find any feasible solution, that is, any vector x that satisfies Ax ≤ b, or to determine that no feasible solution exists. We shall focus on one such feasibility problem.

Systems of difference constraints

In a system of difference constraints, each row of the linear-programming matrix A contains one 1 and one -1, and all other entries of A are 0. Thus, the constraints given by Ax ≤ b are a set of m difference constraints involving n unknowns, in which each constraint is a simple linear inequality of the form

x_j - x_i ≤ b_k,

where 1 ≤ i, j ≤ n and 1 ≤ k ≤ m.

For example, consider the problem of finding the 5-vector x = (x_i) that satisfies

This problem is equivalent to finding the unknowns x_i , for i = 1, 2, ..., 5, such that the following 8 difference constraints are satisfied:

One solution to this problem is x = (-5, -3, 0, -1, -4), as can be verified directly by checking each inequality. In fact, there is more than one solution to this problem. Another is x' = (0, 2, 5, 4, 1). These two solutions are related: each component of x' is 5 larger than the corresponding component of x. This fact is not mere coincidence.

Systems of difference constraints occur in many different applications. For example, the unknowns x_i may be times at which events are to occur. Each constraint can be viewed as stating that there must be at least a certain amount of time, or at most a certain amount of time, between two events. Perhaps the events are jobs to be performed during the assembly of a product. If we apply an adhesive that takes 2 hours to set at time x₁ and we have to wait until it sets to install a part at time x₂, then we have the constraint that x₂ ≥ x₁ + 2 or, equivalently, that x₁ - x₂ ≤ -2. Alternatively, we might require that the part be installed after the adhesive has been applied but no later than the time that the adhesive has set halfway. In this case, we get the pair of constraints x₂ ≥ x₁ and x₂ ≤ x₁ + 1 or, equivalently, x₁ - x₂ ≤ 0 and x₂ - x₁ ≤ 1.

Constraint graphs

It is beneficial to interpret systems of difference constraints from a graph-theoretic point of view. The idea is that in a system Ax ≤ b of difference constraints, the m × n linear-programming matrix A can be viewed as the transpose of an incidence matrix (see Exercise 22.1-7) for a graph with n vertices and m edges. Each vertex v_i in the graph, for i = 1, 2,..., n, corresponds to one of the n unknown variables x_i . Each directed edge in the graph corresponds to one of the m inequalities involving two unknowns.

More formally, given a system Ax ≤ b of difference constraints, the corresponding constraint graph is a weighted, directed graph G = (V, E), where

V = {v₀, v₁,..., v_n}

and

E = {(v_i, v_j) : x_j - x_i ≤ b_k is a constraint} ∪{(v₀, v₁), (v₀, v₂), (v₀, v₃),..., (v₀, v_n)} .

The additional vertex v₀ is incorporated, as we shall see shortly, to guarantee that every other vertex is reachable from it. Thus, the vertex set V consists of a vertex v_i for each unknown x_i , plus an additional vertex v₀. The edge set E contains an edge for each difference constraint, plus an edge (v₀, v_i) for each unknown x_i . If x_j - x_i ≤ b_k is a difference constraint, then the weight of edge (v_i , v_j) is w(v_i, v_j) = b_k. The weight of each edge leaving v₀ is 0. Figure 24.8 shows the constraint graph for the system (24.3)-(24.10) of difference constraints.

The following theorem shows that we can find a solution to a system of difference constraints by finding shortest-path weights in the corresponding constraint graph.

Solving systems of difference constraints

Theorem 24.9 tells us that we can use the Bellman-Ford algorithm to solve a system of difference constraints. Because there are edges from the source vertex v₀ to all other vertices in the constraint graph, any negative-weight cycle in the constraint graph is reachable from v₀. If the Bellman-Ford algorithm returns TRUE, then the shortest-path weights give a feasible solution to the system. In Figure 24.8, for example, the shortest-path weights provide the feasible solution x = (-5, -3, 0, -1, -4), and by Lemma 24.8, x = (d - 5, d - 3, d, d - 1, d - 4) is also a feasible solution for any constant d. If the Bellman-Ford algorithm returns FALSE, there is no feasible solution to the system of difference constraints.

A system of difference constraints with m constraints on n unknowns produces a graph with n+1 vertices and n+m edges. Thus, using the Bellman-Ford algorithm, we can solve the system in O((n + 1)(n + m)) = O(n² + nm) time. Exercise 24.4-5 asks you to modify the algorithm to run in O(nm) time, even if m is much less than n.