对数据依赖关系的分析要求找出是否存在一些整数满足由等式和不等式组成的约束系统。其中的等式是从数组访问的矩阵向量表示中得到的;不等式是从循环界限中得到的。等式可以用不等式表示:等式* 可以用两个不等式*和表示。
因此,数据依赖关系问题可以被表示为寻找满足一组线性不等式的整数解,这个问题就是众所周知的整数线性规划(integer linearprogramming)。
整数线性规划是一个完全问题。虽然没 有已知的多项式复杂性的算法,但人们研发了多种启发式解法来解决涉及很多变量的线性规划问题。这些解法在很多情况下运行得是相当快的。