Difference Constraints And Shortest Paths

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 Linear Programming, 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 and the maximum-flow problem.

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.