0 什么是 Clique
可能有的同学对 Clique 不太熟悉，这里做一个简单介绍。Clique 是一个图论的概念，中文翻译是团。如下图所示：
图中 这三个节点就是一个 clique，因为这三个节点中任意两个节点之间都存在一条边。那么换句话说 图中的 clique 就是 图中的全连接子图的节点集合。
一个图中可以有多个 clique，比如说任意一条边就可以看作是 有两个节点的 clique，而 就是有三个节点的 clique, 在整数规划中有一类经典的问题就是找一个图中最大的 clique，也就是找到节点数最多的 clique，在图中的例子显然就是 就是最大的 clique，这类问题也被称之为 max clique 问题。
1 Clique Merge
介绍完了 Clique 是什么，貌似乍一看它和整数规划预处理也扯不上什么联系。那就让我们转化一个视角来看 Clique 的问题。
你把图中的节点看作是一个整数规划问题中的 binary 变量，把图中的边看作是两个变量相加之和小于等于1的约束。例如对于上图而言变量是
那么边对应的约束为
当然除了上面三个约束，还有两个约束比较多这里就不全写出来了。由于变量 都是 binary 变量，那么以上三条约束都是有含义的。
约束（1）表示 和 至多有一个可以取到1 约束（2）表示 和 至多有一个可以取到1 约束（3）表示 和 至多有一个可以取到1
那么把这三条合并起来看就可以得到一个结论： 和 这三个 binary 变量至多只有一个可以取1，那么把这个结论翻译为约束就是：
也就是说我可以把约束（1-3）等价替换为 约束（4）。以上这个操作就是 Clique Merge，可以看出它是把属于 Clique 的多个约束合并成为一个约束的操作，所以叫做 Clique Merge 。
做这个 Clique Mege 的好处在于 首先约束的数量变少了，上面的例子中由三个约束变成了一个约束，而且显然对于线性松弛问题而言约束（4）的 bound肯定是会更紧一些的，这也有助于提升线性松弛的问题的质量。
那么接下来我们就把上面这个例子严谨化表示出来，首先我们需要构建一个 ，这个图称之为 Conflict Graph，这个图的节点就是整数规划问题中所有的 Binary 变量，若两个 binary 变量至多只有一个可以取1的话，则在两个节点之间有一条边。通过这样的方式就可以把 Conflict Graph 构建出来。
那么对于中任意一个 Clique ，我们可以得到：
得到约束（5）之后就可以把被约束（5）支配的那些约束替换掉。
显而易见，我们希望找到越大的 Clique 集合来做 Clique Merge 的话，可以合并掉的约束就越多，而且线性松弛的bound就会越紧。但寻找一个图的最大的 Clique 本身就说一个NP-hard 的问题，在求解器中一般会采用一些启发式的算法去寻找尽量大的 Clique 来做 Clique Merge 这个操作。
2 Clique Extension
求解 Max Clique 实际上用的比较多的是 Bron-Kerbosch 算法，这是一种递归算法，复杂度是指数级别的。之后有时间可以单开一期讲一讲 Max Clique 的求解方法。
这里我们侧重的是 用快速的启发式算法获取比较大的 Clique 即可，无需百分之百去追求精确获取 Max Clique。实际上更多的场景是我已经知道了一些 Clique，我想在这些 Clique 的基础上做扩展，看是否可以基于现有的 Clique 可以扩展出一个更大的 Clique 出来。我们通过一个例子来展示 Clique Extension 的动机：
图中我们已经知道一个 Clique 是 ，我想扩展这个 Clique 使之变成一个更大的 Clique，那一个自然而然的想法就是，从不在 Clique 的点从挨个去试一下，有没有说是一个点它和当前 Clique 内的所有的点都是连接在一起的。如果有那自然可以把这个点也加入到当前的 Clique 中，这就完成了 Clique Extension 的操作，我们也就获得了更大的一个 Clique 了。
对于上图而言，比方说我可以试一下节点5，我发现节点5和节点1，3没有连接，因此不能扩展 Clique
我再尝试节点3，我发现节点3和Clique 中的所有节点都是连接的，那就可以把节点3也加入到 Clique 中，构成了一个更大的 Clique 即：，就这样不停的重复去尝试扩展 Clique 直到无法扩展为止。
详细算法伪代码如下：
Input: Conflict Graph G=(V,E) and clique C
Output: Extend Clique C1
选择 clique C中度最小的节点 d
L:=节点d的邻居节点集合
while L非空
l:= L集合中度最大的节点
将l从L集合中移除
if 节点l和当前Clique C中所有节点都连接 then
将l添加到Clique C中，构成新的clique
算法伪代码实际上就说对我们前面所述的内容的具体实现版本。需要注意的是在算法中采用了节点的度来做启发式的节点选择顺序准则。
3 总结
至此我们就介绍完了 Clique Merge 算法，以及如何启发式的扩展 Clique 的大小，即 Clique Extension 算法。实际上在整数规划问题中 Clique 这样的结构是非常非常常见的一种结构。高效的处理 Clique 相关的操作是商业求解器必备的基础模块。
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：王源
责任编辑：Road Rash
微信编辑：疑疑
文章转载自『科研式学习』公众号，原文链接：【Presolve (四)】整数规划预处理 Clique Merge 算法
关注我们
FOLLOW US
