Introduction: We now describe a general approach to solving the integer linear programming problem. The problem is NP-complete; our algorithm uses a branch-and-bound approach that can take an exponential amount of time in the worst case. However, it is rare that the heuristics of Section 11.6.4 cannot resolve the problem, and even if we do need to apply the algorithm of this section, it seldom needs to perform the branch-and-bound step.

The approach is to first check for the existence of rational solutions to the inequalities. This problem is the classical linear-programming problem. If there is no rational solution to the inequalities, then the regions of data touched by the accesses in question do not overlap, and there surely is no data dependence. If there is a rational solution, we first try to prove that there is an integer solution, which is commonly the case. Failing that, we then split the polyhedron bounded by the inequalities into two smaller problems and recurse.

Example: Consider the following simple loop:

f o r (i = 1; i < 10; i )

Z [ i ] = Z[i 10J ;

The elements touched by access Z[i] are Z [ l ] , . . . ,Z[9], while the elements touched by Z[i 10] are Z [ l l ] , . . . , Z[19]. The ranges do not overlap and therefore there are no data dependences. More formally, we need to show that there are no two dynamic accesses i and i', with 1 < i < 9, 1 < i' < 9, and i = %' 10. If there were such integers i and i', then we could substitute i' 10 for i and get the four constraints on i': 1 < i' < 9 and 1 < i' 10 < 9. However, i' 10 < 9 implies i' < —1, which contradicts 1 < i'. Thus, no such integers I and %' exist.

Algorithm describes how to determine if an integer solution can be found for a set of linear inequalities based on the Fourier-Motzkin elimination algorithm.

Algorithm: Branch-and-bound solution to integer linear programming problems.

INPUT: A convex polyhedron Sn over variables vi,... ,vn.

OUTPUT: "yes" if Sn has an integer solution, "no" otherwise.

METHOD: The algorithm is shown in Fig. 11.22.

Lines (1) through (3) attempt to find a rational solution to the inequalities. If there no rational solution, there is no integer solution. If a rational solution is found, this means that the inequalities define a nonempty polyhedron. It is relatively rare for such a polyhedron not to include any integer solutions — for that to happen, the polyhedron must be relatively thin along some dimension and fit between integer points.

Thus, lines (4) through (9) try to check quickly if there is an integer solution. Each step of the Fourier-Motzkin elimination algorithm produces a polyhedron with one fewer dimension than the previous one. We consider the polyhedra in reverse order. We start with the polyhedron with one variable and assign to that variable an integer solution roughly in the middle of the range of possible values if possible. We then substitute the value for the variable in all other polyhedra, decreasing their unknown variables by one. We repeat the same process until we have processed all the polyhedra, in which case an integer solution is found, or we have found a variable for which there is no integer solution.

If we cannot find an integer value for even the first variable, there is no integer solution (line 10). Otherwise, all we know is that there is no integer solution including the combination of specific integers we have picked so far, and the result is inconclusive. Lines (11) through (13) represent the branch-and bound step. If variable Vi is found to have a rational but not integer solution, we split the polyhedron into two with the first requiring that Vi must be an integer smaller than the rational solution found, and the second requiring that Vi must be an integer greater than the rational solution found. If neither has a solution, then there is no dependence.

Previous Next