0 简介
其实判断一个变量是否冗余的方法非常多，之前也已经介绍过 Dual Fixing 算法本质就是固定变量的一种技巧。本文再介绍两种可以固定变量的方法：平行变量法和支配变量法。
1 平行变量
我们先来通过一个例子展示，有如下的优化问题：
我们观察上述优化问题，发现变量 和变量 对应的约束矩阵列向量刚好呈现2倍的关系：即
同时 和 两个变量在目标函数中对应的系数也是两倍关系。那么满足以上两个条件我们就可以说变量 和 是平行变量。我们可以采用一个变量 来替换掉这两个平行变量，如下表达式：
采用上述 替换掉原来优化问题 （1-3）中的 和 即可得到新的优化问题：
在新的优化问题中变量的数量变少了，因为我们把平行变量合并成了一个变量，要注意的是合并后的变量 的上下界需要根据式 （5）和原始的平行变量 和 的上下界来确定。
上面仅仅是举一个例子来说明平行变量，接下来我们把这一过程严谨化，进一步推导出一般的平行变量的情况。考虑如下一般的优化问题：
我们采用 来表示约束矩阵第 列元素构成的向量，那么对于两个变量 和 而言，若满足如下条件
则称变量 和 变量 是平行变量。
那么进一步我们可以得到一个新的变量来替换如上平行变量：
进一步可以得到 的边界（这里为了简便我们假设 ）：
自然也可以得到 的目标函数系数：
2 支配变量
我们先来通过一个例子展示支配变量，有如下的优化问题：
我们观察上述优化问题，发现在所有的约束中变量 的系数均小于等于变量 的系数，同时变量 在目标函数中的系数也小于等于变量 在目标函数中的系数。这个时候我们就称 支配了变量 ，接下来我们进一步来解释这个支配变量的含义：
这里我们设上述优化问题 （6-8）有一个可行解：
我们发现
也肯定是一个可行解 ()。
这是因为优化问题 （6-9）中所有的约束中变量 的系数均小于等于变量 的系数，往变量 上增加 同时使得变量 上减少 ，只会让所有约束的左端值不变或者变小，因此对于小于等于的约束而言都不会增加违反约束的程度。这自然表明 肯定也是一个可行解。
又因为 的目标函数比 更小，所以说进一步得到：
那么这就表明 和 都是可行解，但我们总可以根据式 (10) 通过对原来的可行解 做一个平移的滑动 构造出一个更优的可行解 ，那么这个 滑动的值越大自然得到的 的目标函数值就更优。这就说支配变量的基本含义。
观察1：但 一般来说不大可能往无限大了取，因为 的值最终还是要会受到 和 两个变量的上下界的限制。也就是说 会让可行解滑动，直到触碰到 的上界 或者触碰到 的下界 。（这是一个很重要的结论，也是理解支配变量的核心，后边还会用到这个结论）。具体来说 的最优取值如下所示：
接下来我们给出严谨的支配变量的含义，考虑如下优化问题
那么对于两个变量 和 而言，若满足如下条件
则称变量 支配变量 。
若变量 支配变量 ， 进一步可以得到
若 ，则变量 ,
若 ，则变量
以上推论实际上可以根据观察1中给出的结论很容易得到证明，这里我们就不给出具体的证明过程了。如果想看具体的证明过程请参考文献【1】。那么通过支配变量的判定准则我们就可以固定一些变量，从而缩减问题规模，达到加速计算的目标。
3 总结
本文介绍了平行变量法和支配变量法这两种算法来消除混合整数线性规划中的变量数量，实际上这两种算法是非常实用的两种算法，这两种算法也已经被广泛集成到求解器中来加速求解器的性能。
参考文献
【1】 Gamrath G, Koch T, Martin A, Miltenberger M, Weninger D (2015) Progress in presolving for mixed integer programming. Math. Programming Comput. 7(4):367–398
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：王源
责任编辑：Road Rash
微信编辑：疑疑
文章转载自『科研式学习』公众号，原文链接：【Presolve (五)】如何判断一个变量是否是冗余的？
关注我们
FOLLOW US
