最大切割问题
最大切割问题确定图的顶点 的一个子集
,从
到其补集
的边的权重
的和被最大化。
这个例子演示了如何使用 SemidefiniteOptimization 来设置一个函数,能有效求解 NP 完备的最大切割问题的松弛问题。
假定 有
个顶点,可以用索引描述
描述。设
为一个向量,其分量为
,
;
,
,只有当
且
时
非零 (=2)。因此可通过最大化
找到最大切割,其中
。可将目标函数改写为:
... 其中 是图的拉普拉斯矩阵,
是加权邻接矩阵。
对于简单的问题,可以精确求解最大割问题,但对于较大的图是不切实际的,因为通常问题具有 NP 完备复杂性。
该问题要最小化 ,其中
是对称 1 阶半制定矩阵,对于每个
,
,等价于
,其中
是第
个对角元素为 1、其他位置上的元素为 0 的矩阵。
为了得到实用解,求解 1 阶条件被排除掉的松弛问题,只要求 。
对偶形式的半定问题如下所示:
用 SemidefiniteOptimization[c, {a0, a1, …, ak}, {"DualMaximizer" }] 求解。
对于松弛问题的解 ,通过随机舍入构建切割:分解
,令
为具有单位范数的均匀分布的随机向量,令
。为了演示,我们定义了一个函数来显示松弛条件下的值、舍入值和图,用红色显示
中的顶点。
用以上所示步骤求近似切割,并与精确结果相比较。
求网格图的最大切割。
求随机图的最大切割。
比较 Peterson 图的松弛算法和精确算法的用时。