预处理概述

 问题背景

线性规划问题的规模越来越大，含有成千上万个约束和变量的问题非常常见，面临着数据的储存和处理效率问题，大规模问题一般都是由模型支持工具自动生成的，往往存在大量冗余的约束和变量，在算法求解之前进行数据预处理是必要的。

 主要目的

1.  化约冗余约束，减少约束矩阵非零元素，提高稀疏度，减少问题规模，节省内存；
2.  改善模型的数值特征，提高问题的数值稳定性；
3. 在不求解问题的情况下判定问题无可行解或无界。

 主要挑战

1. 提升复杂预处理方法的性能；
2. 确定不同预处理方法的作用次序和作用次数；
3.  确定预处理何时停止；
4.  设计预处理并行框架。

预处理方法

不可行性

空行和空列

固定变量

强制行

比例行

平行行

对偶规定

两行非零元消去