0 预求解算法简介
预求解(presolve)是在实际求解优化问题之前，对模型进行一系列的分析和转化，以便减少问题的规模、简化约束、去除冗余信息等，从而使问题更容易高效地求解。目前所有的整数规划求解器都配备了预求解技术。
预求解的主要目标是优化问题规模，以减少求解时间和内存需求。它通过以下方式实现：
变量与约束的删除： 首先，presolve 分析问题中的变量和约束，识别出那些在问题求解过程中不会起作用的项。这些项可以被直接删除，从而减少问题的规模。 约束的简化： 如果某些约束之间存在冗余或者线性相关性，presolve 可以将它们合并、简化，从而减少约束的数量，使问题更加紧凑。 变量范围的缩小： 通过分析变量的取值范围，presolve 可以缩小变量的可能取值范围，有时甚至能够将某些变量固定为特定的值，从而降低问题的复杂性。 问题转化： 在某些情况下，presolve 可以将原始问题转化为等价但更简单的形式，从而为求解器提供更好的起始点。
总之，预求解在运筹优化中是一个非常重要的技术，能够大幅度提高问题求解的效率和质量。通过在求解之前对问题进行预求解处理，可以减少计算成本，加快求解速度。
具体来说，目前主要的预求解算法有十几种，可以说在预求解算法中占据最核心地位的就是 Domain Propagation，目前中文互联网上几乎没有关于 Domain Propagation 的内容，因此大家对于 Domain Propagation 的了解比较少。本文就对 Domain Propagation 这一核心技术进行介绍。
1 从一个例子看 Domain Propagation 的基本思想
Domain Propagation 想要做的事情就是通过整数规划问题中约束和变量的边界信息来进一步压缩变量的边界。这么说对于初学者来说比较抽象，我们通过一个具体的例子来说明 Domain Propagation 这一基本思想。考虑在整数规划问题中有如下约束：
其中 都是整数变量， 和 变量的边界分别为：
观察式(1.1)和式(1.2)我们不难发现 的边界虽然是0到2之间，但是 是无法等于2的。这是因为如果 ，带入约束(1.1)左端就会得到 ，也就是说 一旦等于2就会造成约束(1.1)一定是无法满足的，这样我们就可以反推出 一定无法取到2，那么根据以上性质，我们就可以对变量的边界进行压缩：
这样变量 的边界实现了压缩，消除了我们模型中的冗余，缩减了模型的可行域，这样通过 Domain Propagation 处理后的模型显然是一个更好的模型。
2 Domain Propagation
前面是通过一个具体的实例来阐述 Domain Propagation 的基本思想，我们这一节是要给出一般的 Domain Propagation 的操作。考虑如下一般的约束形式：
其中 ，同时定义出每个变量的上下界分别为： ，根据变量的上下界我们可以得到约束(2.1)左端项 的上下界为：
进一步我们定义约束(2.1)左端项 除去任意一个变量 之后的上下界为：
有了以上定义接下来我们正式开始推导 Domain Propagation 是如何缩进变量边界的，首先我们根据约束(2.1)可以等价得到：
将上式中左端项替换可得：
这是因为 是对于左端项任意 的上界，自然对左端项的max也是成立的，因此我们用 替换掉 是成立的。
接下来我们对式(2.6)进行移项处理，若 ，从式(2.6)可以得到
反之，若 ，从式(2.6)可以得到
式(2.7)和式(2.8)我们就得到变量 的一个新的界，如果这个新的界比之前的界 更紧的话，那么我们的目标就达到了。
前面的推导过程我们并没有用到任何关于 是整数的信息，因此上面的结论对整数变量和连续变量都是成立的。进一步，如果 是整数变量的话我们改写式(2.7)和式(2.8):
由于考虑了整数变量的信息，上面得到的界会更加紧一点。
以上推导过程看起来内容偏多，但是实际上就是对第一节中那个具体例子的一般化，如果没有看懂的话，请大家回到第一节中的那个小例子对应起来去体会一下。
3 Domain Propagation 实例
我们还是回到最开始那个例子：
在这一节中我们会用第二节推导出的方法来计算变量的边界，而不是像第一节中用肉眼观察的方法来压缩变量的边界。这么做的目的就是 加深大家对于 第二节中推导过程的理解。
套用式(2.4)和式(2.5)，我们计算出约束(3.1) 左端项去除变量 的上下界为：
由于变量 的系数是大于0的，我们带入到式(2.7)可得：
至此我们就得到了 的一个新的上界为1，我们发现原来 的上界是2，也就是说新的这个上界确实是起到了作用。至此我们就用第二节中推导出的一般的方法得到了一开始我们在第一节得到的直观的结果。
接下来我们用同样的方法对变量 也进行处理，套用式(2.4)和式(2.5)，我们计算出约束(3.1) 左端项去除变量 的上下界为：
由于变量 的系数是大于0的，我们带入到式(2.7)可得：
至此我们就得到了 的一个新的上界为2，我们发现原来 的上界是1，也就是说新的这个上界确实没有起到任何作用。
4 总结
至此我们了解了 Domain Propagation 这项实用技术，Domain Propagation 的价值不单单在于其算法本身，同时也可以促使我们在对整数规划建模的时候就考虑建立变量边界更紧的模型。所以个人感觉掌握 Domain Propagation 的思想更为重要。关于 Domain Propagation 还有以下几点作为本文的补充：
Domain Propagation 每次可以更新一个变量的边界，这个过程是一个迭代过程，往往需要做很多轮的 Domain Propagation，直至满足最大迭代次数或者边界不再变化为止 Domain Propagation 的计算复杂度并不高，在实际的数值实验中计算速度也比较快。 Domain Propagation 具体的实现需要考虑 Numerical Issue 的问题，否则容易导致问题的不可行。
本文只是对 Domain Propagation 有了一个基本思想的介绍，更进一步的内容可以查阅参考文献【1】Chapter 7 Domain Propagation 部分，在公众号后台回复 “domain” 即可获得参考文献 【1】资料。
参考文献
【1】Achterberg T. Constraint integer programming[J]. 2007.
【2】Berthold T, Hendel G. Shift-and-propagate[J]. Journal of Heuristics, 2015, 21: 73-106.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：王源
责任编辑：Road Rash
微信编辑：疑疑
文章转载自『科研式学习』公众号，原文链接：整数规划预求解算法的核心技术：Domain Propagation
关注我们
FOLLOW US
