优化 | 如何判断一个约束是否是冗余的？

0 什么是冗余约束

考虑如下线性整数规划问题 ：

我们定义上述整数规划问题的可行域：

删除掉其中一条约束 ，得到一个新的线性整数规划问题 ，由此也可以定义出 问题的可行域为 ，若删除前和删除后的两个整数规划问题的可行域是相等的，即满足

成立，则我们可以判断出约束 是冗余的。这个对于冗余约束的定义是非常自然的，直接来说就是一个约束有它没它完全不影响原来整数规划问题的可行域，那么自然这个约束就是冗余的。

不难看出对于上述线性整数规划问题而言，想要检测一个给定约束是否是冗余约束，这个问题本身就是一个 NPC 问题。值得注意的一点是 如果我们可以检测出冗余约束，那是否就是要全部删除掉这些冗余约束呢？

答案是 否定的。

为什么呢？试想一下，我们上述定义冗余约束的方式是 通过约束是否会影响整数规划问题可行解来定义的，那么大多数的割平面实际上都不会影响整数规划问题的可行解，这些割平面本质上也就是一种冗余约束。那么如果要删除所有的冗余约束，显然就代表着要删除很多割平面。我们都知道割平面对于求解整数规划问题是非常有帮助的，那么基于此我们会有两个思考：

1. 删除所有冗余约束并不是一个明智的行为
2. 如果有一个冗余约束，它可以切割掉整数规划对应的线性松弛的可行解，那么这个约束其实也是有价值的，实际上我们更应该考虑的是线性松弛的冗余约束

1 线性规划冗余约束判断

前面我们根据是否影响整数规划可行域来定义冗余约束，但我们发现实际上我们可能更需要关心的是那些对于线性松弛问题而言的冗余约束。基于此我们需要重新定义面向线性规划问题的冗余约束，我们称之为松弛问题冗余约束，考虑如下线性规划问题：

我们说判断一个约束

是不是冗余的。可以通过判断如下线性规划问题（这个线性规划就是删除掉了约束 ）最优解的方式来实现：

当且仅当   时 约束 (4) 是对于线性规划问题 (1-3) 是冗余的。

我们观察线性规划问题（5）实际上和原始的线性规划问题(1-3) 只差是少了一个约束 ，然后把这个约束 放到了目标函数上。

那么我们可以发现确实可以通过求解线性规划的方式来判断一个约束是否是松弛问题冗余约束，但求解线性规划也是比较耗时的一件事情，那么接下来介绍一些启发式的方法可以非常快速的去判断松弛问题冗余约束。这些算法已经被广泛的应用于商业求解器中。

注意为了方便起见，从这里开始我们提到的冗余约束 都指的是对于 整数规划问题线性松弛问题的冗余约束，而不是一开始在 chapter 0 里边定义的冗余约束。

2 根据变量上下界来判断冗余约束

我们可以根据变量的上下界来辅助判断冗余约束，举一个简单的例子就是：

如果我们知道变量 的上下界为

因为变量有上下界限制，所以约束（6）是被自动满足的。这样利用单个约束的变量上下界信息就可以非常简单的判断出约束（6）是一个冗余约束。

3 根据支配约束判断冗余约束

我们可以根据支配约束来辅助判断冗余约束，举一个简单的例子来说明支配约束：

其中 ，我们发现只要约束（9）被满足，那么约束（8）是一定被满足的。这种情况我们称之为约束（9）支配约束（8）。约束（8）就是一个冗余约束，那么只需要保留约束（9），删除掉约束（8）即可。

4 根据平行约束判断冗余约束

我们可以根据平行约束来辅助判断冗余约束，举一个简单的例子来说明平行约束：

我们很容易观察到 约束（10）左端项乘以0.2就等于约束（11）左端项，满足这样条件的就说 约束（10）和约束（11）是平行约束。接下来我们采用比较严谨的符号来定义平行约束。

对于线性规划问题（1-3）而言，若两个约束 ，这两个约束称之为平行约束，那么其对应的系数：

其中 , 分别为约束 和约束  的约束系数向量。

那么对于平行约束会有如下三种情况：

情况1：两个平行约束都是等式约束

若 则表明上述两个约束是等价的，可以删除掉任意一个。若 则表明该问题是不可行的。

情况2：平行约束中一个是等式一个是不等式约束：

我们方便期间只讨论 的情况， 的情况其实是相似的。

若 ，我们发现满足约束 则一定会使得约束 被满足，所以约束 是冗余的，可以被删除掉。

若 ，我们发现满足约束 和约束 是矛盾的，所以该问题是不可行的。

情况3： 平行约束中两个都是不等式约束：

我们方便期间只讨论 的情况， 的情况其实是相似的。

若 ，我们发现满足约束 则一定会使得约束 被满足，所以约束 是冗余的，可以被删除掉。

若 ，我们发现满足约束 则一定会使得约束 被满足，所以约束 是冗余的，可以被删除掉。

至此我们讨论了平行约束出现的三种情况，每种情况其实都不难处理。实际上在具体的算法实现中如何检测出两个约束是平行约束并不困难，但是想要实现非常高效的算法还需要一些技巧。例如利用 hash function 来加速平行约束的判断就是一个非常实用的技巧。

5 根据近似平行约束判断冗余约束

平行约束是要求两个约束包含的变量一定是一样的，而且系数刚好呈现一个倍数的关系。这样的要求相对来说是比较严格的，那么我们尝试放松一点要求。比如说两个约束只有一个变量不一样的情况，那么这种情况就是近似平行约束。举一个例子来说：

约束（12）和约束（13）就是近似平行约束，这两个约束中只有一个变量不一样就是 ，其他变量都是一样的，并且约束（12）中其他的变量系数是约束（13）中其他变量系数的10倍。

那么进一步严谨的定义近似平行约束：

其中 , 若  则表明约束 （14）和约束（15）是近似平行约束。其中 就是近似平行约束中两个约束公共拥有的变量， 是约束（14）独有的变量， 是约束（15）独有的变量。

将约束（14）两边同乘以 ，再两边同时减去约束 （15）可得：

进一步整理可得：

其中 和

我们将式（16）反带入约束（15）中可得：

这样我们就可以将近似平行约束（14）和约束（15）等价转化为平行约束（14）和约束（17），那么接下来只需要采用上一节所述处理平行约束的方法来处理即可。

这里我们只考虑近似平行约束都是等式的情况，类似于平行约束存在三种情况，本文就不详细介绍一个等式约束一个不等式 和 两个不等式约束的情况了。详情可以见参考文献【1】。

6 总结

至此，我们先介绍了 冗余约束的概念，分别在整数规划和线性规划上来定义冗余约束的概念。并且说明了我们主要还是考虑在线性规划问题上（或者说是整数规划线性松弛问题上）来做冗余约束检测和删除的操作。

然后，我们介绍了五种判定冗余约束的方法：

1. 线性规划判断法
2. 变量上下界判断法
3. 支配约束判断法
4. 平行约束判断法
5. 近似平行约束判断法

以上五种算法是最为常见的判断冗余约束的方法，其均已经被集成到商业求解器中。这些方法虽然看起来并不复杂但对我们加速整数规划起到了很重要的作用。

参考文献：

【1】Achterberg T, Bixby R E, Gu Z, et al. Presolve reductions in mixed integer programming[J]. INFORMS Journal on Computing, 2020, 32(2): 473-506.

【2】Gleixner A, Gottwald L, Hoen A. Papilo: A parallel presolving library for integer and linear optimization with multiprecision support[J]. INFORMS Journal on Computing, 2023, 35(6): 1329-1341.