14.10 Omega 一种对线性规划问题的求解

数据相关性分析包含多个求解器，从不太复杂的到比较复杂的。为了确保这些求解器的结果的一致性，实现了一个基于不同求解器的数据相关性检查过程。已经被集成到GCC中的第二种方法是基于Omega相关求解器，由William Pugh和David Wonnacott在1990年编写。数据相关性测试能够通过使用Presburger算法的子集来公式化，从而可以转化为线性约束系统。然后这些线性约束系统能够使用Omega求解器求解。

Omega求解器使用Fourier-Motzkin算法进行变量消除：一个包含n个变量的线性约束系统被消减为包含n-1个变量的线性约束系统。Omega求解器还能够用来解决其它能被表示为线性等式和不等式系统形式的问题。Omega求解器有一个公认的指数最坏情况，即文献上称之的“omega 恶梦”，不过实际上，众所周知omega测试对于公用数据相关性测试是有效的。

Omega求解器所使用的描述线性规划问题接口在omega.h中，求解器为omega_solve_problem。