最大割问题⚓︎
约 2355 个字 8 行代码 预计阅读时间 8 分钟 总阅读量 次
1. Max-Cut 问题是什么？模型如何表示？⚓︎
问题定义：
给定一个无向图 \(G=(V, E)\)，其中 \(V=\{1, ..., n\}\) 是顶点集，\(E\) 是边集，每条边 \((i, j)\) 有权重 \(w_{ij}\)。 MAX-CUT 问题的目标是找到一个顶点子集 \(S \subset V\)，将顶点划分为两个集合 \((S, \bar{S})\)（其中 \(\bar{S} = V \setminus S\)），使得连接这两个集合的所有边的权重之和最大化。
这个问题可以被建模成一个： 整数二次规划（Integer Quadratic Programming） formulation：
- 目标函数： $$ \max \frac{1}{2} \sum_{1 \le i < j \le n} w_{ij}(1 - y_i y_j) $$
- 约束条件： $$ y_i \in {-1, 1}, \quad \forall i \in V $$
变量含义：
- \(y_i = 1\) 表示顶点 \(i\) 属于集合 \(S\)。
- \(y_i = -1\) 表示顶点 \(i\) 属于集合 \(\bar{S}\)。
- 如果 \(y_i \neq y_j\)（即一个为 1，一个为 -1），则边 \((i, j)\) 跨越了割，\((1 - y_i y_j)\) 为 2，贡献权重 \(w_{ij}\)；否则贡献为 0。
背景： NP-hard。应用领域包括 VLSI 设计（超大规模集成电路）和统计物理学（如自旋玻璃模型）。
2. 随机启发式算法⚓︎
基于论文 RANDOMIZED HEURISTICS FOR THE MAX-CUT PROBLEM
6 种随机启发式算法。这些算法基于三种主要的元启发式策略及其混合：GRASP、VNS 和 Path-Relinking (PR)。
核心策略： 1. GRASP (Greedy Randomized Adaptive Search Procedure)： * 构造阶段： 使用自适应贪婪函数。对于每个未分配的顶点 \(v\)，计算将其放入 \(S\) 或 \(\bar{S}\) 能增加的权重。根据贪婪值构建“受限候选列表 (RCL)"，从中随机选择一个顶点加入解中。 * 局部搜索阶段： 尝试移动单个顶点到另一个集合，如果能使割权重增加（\(\delta(v) > 0\)），则移动，直到无法改进。 2. VNS (Variable Neighborhood Search)： * 通过动态改变邻域结构来跳出局部最优。 * 定义 \(k\) 阶邻域：同时移动 \(k\) 个顶点到另一个集合。如果在当前邻域找不到改进解，则增加 \(k\) 值（扩大搜索范围）。 3. Path-Relinking (PR)： * 一种强化策略。在找到一个局部最优解后，将其与一个“精英解池 (Elite Set)"中的解进行路径连接。 * 通过逐步翻转变量，使当前解向精英解靠拢，并在路径上寻找更好的解。
提出的 6 种具体算法：
- g (Pure GRASP)： 纯 GRASP 算法。
- gpr (GRASP + PR)： GRASP 加上路径重连强化。
- vns (Pure VNS)： 纯 VNS 算法。
- vnspr (VNS + PR)： VNS 加上路径重连强化。
- gvns (GRASP + VNS)： 使用 VNS 代替 GRASP 中的局部搜索阶段。
- gvnspr (GRASP + VNS + PR)： 上述混合再加上路径重连。
在实现和实验过程中，有几个关键的技术细节决定了算法的性能：
- 贪婪函数与 RCL 参数 \(\alpha\)：
- 在 GRASP 构造阶段，定义截断值 \(\mu = w_{min} + \alpha \cdot (w_{max} - w_{min})\)。
- 只有贪婪函数值 \(\ge \mu\) 的顶点才能进入候选列表。
- 细节： 在实验中，\(\alpha\) 不是固定的，而是在每次 GRASP 迭代中从 \([0, 1]\) 均匀分布中随机选择。这增加了构造解的多样性。
- 精英解池 (Elite Set) 管理：
- 用于 Path-Relinking。最大容量设为 30。
- 替换策略： 如果新解比池中最差解好但不如最好解，它必须与池中所有解的特征向量差异超过 1%，才能替换掉最差解。这保证了精英解的多样性，防止早熟收敛。
- VNS 的邻域参数 \(k_{max}\)：
- 纯 VNS 中，\(k_{max} = 100\)（搜索更彻底，但慢）。
- 在 GRASP+VNS 混合中，为了加速，\(k_{max}\) 减小为 15。
- 对比基准的选择：
- 作者没有主要对比经典的 Goemans-Williamson (GW) 随机算法（近似比 0.87856）。
- 原因： Burer, Monteiro, and Zhang 提出的
circut算法（基于 rank-2 松弛启发式）在实践中比 GW 算法产生更高质量的解且速度更快。因此，作者主要将自己的启发式算法与circut进行对比。
- 时间 - 目标值分布 (Time-to-Target)：
- 作者不仅看最终结果，还分析了“找到特定质量解所需时间”的概率分布。发现 GRASP+PR (
gpr) 在寻找次优解时收敛最快，适合并行化。
- 作者不仅看最终结果，还分析了“找到特定质量解所需时间”的概率分布。发现 GRASP+PR (
2.1 近似算法⚓︎
Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs，2002.
作者：Samuel Burer, Renato D.C. Monteiro, Yin Zhang
核心贡献：提出一种基于秩二松弛（rank-two relaxation） 的连续优化启发式算法，用于高效求解Max-Cut等二元二次规划问题。
目前在解决同类问题效果很好。
3. 系统的数值试验与梳理⚓︎
针对最大割问题，What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO 参考这篇论文的报告。这里的 QUBO 指的是 Quadratic Unconstrained Binary Optimization，存在简单的变换可以将 QUBO 实例转化为 Max-Cut 实例，QUBO 目标是在二元变量（0 或 1）上优化（最大化或最小化）一个二次函数，且没有显式的约束条件（除了变量本身的二元性）。
\[ \max_{x \in \{0,1\}^n} x^T Q x \]
其中：
- \(x\) 是一个包含 \(n\) 个变量的向量，每个变量 \(x_i \in \{0, 1\}\)。
- \(Q\) 是一个 \(n \times n\) 的实数矩阵（通常是对称矩阵或上三角矩阵），包含了线性项和二次项的系数。
- 目标函数展开后包含形如 \(q_{ii}x_i\) 的线性项和形如 \(q_{ij}x_i x_j\) 的二次交互项。
主要特点
- 二元性：变量只能取 0 或 1，这使得解空间是离散的（大小为 \(2^n\)）。
- 无约束：问题本身没有额外的线性或非线性约束（如 \(Ax=b\)）。如果有约束，通常通过惩罚项（Penalty Method）加入到目标函数矩阵 \(Q\) 中转化为无约束形式。
- 计算复杂度：QUBO 是 NP-hard 问题。论文中提到它与 Max-Cut 问题可以通过简单的变换相互归约（reduce to each other），而 Max-Cut 是 Karp 的 21 个 NP 完全问题之一。
| 项目 | 内容 |
|---|---|
| 标题 | What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO |
| 作者 | Iain Dunning, Swati Gupta, John Silberholz |
| 机构 | MIT Operations Research Center |
| 关键词 | 计算测试、可重复研究、启发式算法、二元二次优化、Max-Cut、超启发式、测试床、可解释机器学习 |
现有启发式算法评估的三大缺陷
- 可重复性差
- 仅 4% 的 Max-Cut/QUBO 启发式论文公开源代码
-
20% 未报告处理器信息，87% 未报告编译器标志
-
比较不公平、范围窄
- 86% 的比较使用不同的终止条件，难以判断性能差异来源
-
中位数仅比较 3 种先前算法，无人比较超过 10 种
-
测试实例同质化
- 标准库仅含 231 个随机生成实例，缺乏真实场景代表性
- Max-Cut 库仅含稀疏图，QUBO 库仅含稠密矩阵
研究目标⚓︎
构建可复现、公平、大规模的启发式算法评估框架，回答"什么算法在什么情况下最有效"这一实践者核心问题。
┌─────────────────────────────────────┐
│ 1. 扩展实例库 (Section 2) │
│ • 3,296 个实例（2,153 真实 + 1,143 随机）│
│ • 覆盖多种图结构、密度、权重分布 │
└─────────────────────────────────────┘
↓
┌─────────────────────────────────────┐
│ 2. 开源启发式实现 (Section 3) │
│ • 系统综述筛选 95 篇论文 │
│ • 实现 37 种启发式算法（10 Max-Cut + 27 QUBO）│
│ • 统一 C++ 代码框架，共享数据结构 │
└─────────────────────────────────────┘
↓
┌─────────────────────────────────────┐
│ 3. 云端大规模评估 (Section 4) │
│ • 60 台 AWS EC2 实例并行计算 │
│ • 统一终止条件：生成 1500 个随机解 + 局部搜索 │
│ • 每种算法×每种实例×5 次随机种子 │
└─────────────────────────────────────┘
↓
┌─────────────────────────────────────┐
│ 4. 可解释性分析 (Section 5) │
│ • CART 回归树识别算法性能与实例特征关系 │
│ • 分析启发式思想（如进化算法、禁忌搜索）适用场景│
└─────────────────────────────────────┘
↓
┌─────────────────────────────────────┐
│ 5. 算法组合构建 (Section 6) │
│ • 随机森林预测最优启发式 │
│ • 构建超启发式（hyper-heuristic）选择器 │
└─────────────────────────────────────┘
📊 数值试验设计⚓︎
- 数据库
| 类型 | 数量 | 来源 |
|---|---|---|
| 标准库实例 | 231 | G-set, Spin Glass, Biq Mac, OR-Lib 等 |
| 真实世界实例 | ~2,000 | VLSI 设计、电信网络、生物网络分析等 |
| 随机生成实例 | 1,143 | Erdős-Rényi, Barabási-Albert, Watts-Strogatz 等 |
| 总计 | 3,296 | 公开于 GitHub: MQLib/MQLib |
- 评估指标（7 项）
# 核心指标定义（以启发式 h 在实例集 I 上为例）
- WD(h): 最差解平均偏差（5 次运行中最差）
- MD(h): 平均解平均偏差
- BD(h): 最优解平均偏差
- FE(h): "并列第一"实例百分比
- FS(h): "严格第一"实例百分比
- BA(h): 至少一次达到最优的实例百分比
- AR(h): 平均排名（1=最佳，37=最差）
- 总计算量：2.0 CPU-年（每算法 20.1 CPU-天）
- 墙钟时间：12.4 天（60 台机器并行）
- 云成本：$1,196（每算法 $32.3）
🎯 结论⚓︎
| 排名 | 算法 | 类型 | FE(%) | FS(%) | MD(%) | AR |
|---|---|---|---|---|---|---|
| 1 | BUR02 | Max-Cut 非线性优化+局部搜索 | 22.9 | 16.2 | 0.3 | 10.7 |
| 2 | FES02GP | GRASP+路径重连 | 21.3 | 4.1 | 0.5 | 10.1 |
| 3 | GVP | GRASP+VNS+路径重连 | 19.4 | 2.3 | 0.6 | 7.5 |
| 4 | PAL04T3 | 禁忌搜索+GRASP | 19.3 | 5.5 | 0.7 | 14.2 |
| 5 | FES02GV | GRASP+VNS 局部搜索 | 18.0 | 1.5 | 0.7 | 11.2 |
🔑 关键发现：无单一算法在所有实例上最优，30/37 算法在至少一个实例上表现最佳。
标准库评估结果 → 扩展库评估结果
• 23 种算法在标准库上"严格第一"率为 0，但在扩展库上 >0
• 其中 3 种算法在扩展库上"严格第一"率 >5%
• 例：MER99LS（遗传算法）在扩展库上排名从 23/37 升至 3/37
| 启发式类别 | 适用实例特征 | 不适用实例特征 |
|---|---|---|
| 进化算法 | 稀疏/稠密中等规模图 | 超大规模实例 |
| 禁忌搜索 | 稠密图 | 稀疏图 |
- 方法论贡献
- 首次实现 Max-Cut/QUBO 启发式的大规模公平比较
- 开源代码库
MQLib促进可重复研究 -
统一终止条件 + 云计算确保结果可比性
-
实践指导价值
- 无"万能算法"，需根据实例特征选择启发式
- 算法组合（portfolio）显著优于单一算法
-
可解释模型帮助理解"何时用什么算法"
-
领域启示
- 标准测试库的同质化严重限制结论泛化性
- 真实世界实例对评估启发式鲁棒性至关重要
- 机器学习方法可有效辅助算法选择
4 关于二次规划⚓︎
二次优化就是目标函数为二次型、约束通常为线性的优化问题，形式可写成 \(\min \frac12x^TPx+q^Tx\)，约束一般线性。
判断难度关键看矩阵 \(P\)：若 \(P\) 半正定，问题是凸二次规划，属于凸优化，只有全局最优，可用内点法、有效集法等在多项式时间精确求解；若 \(P\) 不定或负定，就是非凸二次优化，存在大量局部最优，属于NP-hard，无法高效求精确解。
最大割 Max Cut 就可以写成非凸二次 0‑1 规划，也是 NP‑hard。实际求解里，凸 QP 直接用求解器快速算出最优解，非凸 QP 一般用 SDP 松弛、启发式算法求近似解，很难得到全局最优。