1 什么是 Presolve
一个混合整数线性规划问题包含如下两个约束：
那我马上可以发现约束 是冗余的，因此可以直接删除这个约束而并不会影响可行域的大小。
再举一个例子，对于一个混合整数线性规划问题包含这样一个约束：
那我马上可以把这个约束做一个替换
由于上式左端变量都是整数，因此左端只可能取整数的值。对于整数规划问题而言，小于等于10.8和小于等于10是完全等价的（可行域相同）。但对于其线性规划松弛而言，小于等于10.8比小于等于10的约束要更差一些。因此做了如上等价变换后会让整数规划的bound更加紧，有利于求解器的求解。
对于一个混合整数线性规划问题而言，如果有这样一个约束：
那我马上可以把这个约束做一个替换
以上两个约束是完全等价的（可行域是一样大的），但后者的约束系数绝对值更小，一般来说后者更加利于求解器的求解。
以上我们通过三个非常简单的例子直观感受一下 Presolve 的作用，那么从这三个例子可以大致总结出来 Presolve 做的事情：
消除冗余约束或者冗余变量，使得通过Presolve处理之后的问题规模减小，这有利于求解器的加速 让整数规划的bound变得更紧，使得通过Presolve处理之后的问题的线性规划松弛的界更好，这有利于求解器的加速 缩减问题中的系数的大小，使得通过Presolve处理之后的问题的系数绝对值更小，这有利于求解器的加速
以上就是大致总结了 Presolve 的意义和作用，其实还不能算是很全面的总结。Presolve 在混合整数线性规划求解器中发挥着举足轻重的作用，常见的商业求解器如 Gurobi, CPLEX等都集成了非常多的 Presolve 技巧。很多时候我们可以观察到通过 Presolve 可以把问题规模缩减几倍，十几倍都是很常见的事情。
2 Simple Probing
Simple Probing 是一种 Presolve 技巧，接下来我们详细介绍这个技巧，我们首先来看一个例子，我们考虑在整数规划问题中有这样一个约束：
其中 ,
观察这个约束我们发现只有 是一个 binary variable，其他的变量是连续变量，每个变量都在0到1之间的界限内。
如果 的话我们马上可以得到：
如果 的话我们马上可以得到：
这其实就启发我们，得到一个非常关键的结论： 的取值一旦确定了，那约束（1）中其他变量 () 的取值就一定可以被确定。进一步把这个结论表述出来就是：
不难验证约束（2）和约束（1）是等价的。这样我们就可以用约束（2）来替换掉原始的约束（1）。
这么做的好处就是 首先约束（2）比约束（1）的线性松弛的界要更加紧一些，另外就是约束（1）的系数的绝对值比较大，这不利于求解器的求解，而约束 (2)系数都是-1和1，系数绝对值比较小，这对于求解器来说是比较有益的。
那么以上只是从一个简单的例子出发，让大家对 Simple Probing 有一个初步的感性认识，接下来我们需要把这一个过程严谨化，考虑到一般的情况如何来做 Simple Probing 。对于一个一般的约束：
该约束中存在一个变量 ，我们假设在上述约束的系数 ，实际上这个假设并不失一般性，因为如果某一个系数 我们总可以通过做如下变量代换 ，使得系数变换为大于0的情况。
接下来如果说 这个系数 （即Binary变量 对应的系数）还满足如下条件：
那么我们就可以做 Simple Probing 了。接下来我们来推导这个过程。显然观察式 (5)中 max 这一项我们发现，因为其中 的系数是大于0的，所以求 max 自然是取到 。类似的，由于是求 max，同时所有的系数都是大于0的，自然都是取到每个变量的上界。基于此得到如下表达式：
进一步整理可得
显然观察式 (6)中 min 这一项我们发现，因为其中 的系数是大于0的，所以求 min 自然是取到 。类似的，由于是求 min，同时所有的系数都是大于0的，自然都是取到每个变量的下界。基于此得到如下表达式：
至此我们得到关键的两个表达式 (7) 和 (8)。观察式(7)我们发现，若 的时候，要想保证原约束(3)被满足，必须使得所有的 。观察式(8)我们发现，若 的时候，要想保证原约束(3)被满足，必须使得所有的
3 总结
对于约束 (3), (4) ，若其中 binary 变量 对应的系数 满足式(5)和式(6)两个条件，则表明：
若 ，则必须有 ；若 ，则必须有
基于此可以把约束(3)替换为：
根据如上的结论，回到我们给出的例子：
其中 ,
在这个例子中 , , , ，容易验证
至此发现约束(1)确实是满足我们Simple Probing的条件的，因此把约束(1)替换为：
是成立的。
至此，我们完成了所有关于 Simple Probing的推导过程，并且将其应用到一个例子中进行了详细的说明。
