技术摘要：Forge：基于图嵌入的基础优化表示

1. 问题陈述

组合优化（CO）问题，特别是混合整数规划（MIP），是科学与工程领域的基础，但其求解计算成本极高。虽然机器学习（ML）提供了极具前景的替代方案，但目前的学习型方法面临着显著的可扩展性和泛化性限制：

• 数据依赖性： 训练通常需要求解大量困难实例以生成标注数据，这产生了高昂的计算成本，并且依赖于研究人员试图加速的求解器本身。
• 缺乏泛化能力： 现有方法通常为特定的问题分布、下游任务或问题规模训练专用模型。它们无法在不同的问题领域（例如集合覆盖与组合拍卖）或任务类型（例如割平面生成与搜索引导）之间进行泛化。
• 结构性局限： 大多数组合优化方法依赖于图神经网络（GNN），虽然 GNN 能有效捕捉局部变量-约束信息，但由于固有的局部性偏差，难以编码具有意义的全局实例结构。

本文认为有必要开发一种基础优化表示：一种预训练的、通用的模型，能够生成可跨任务、问题和规模进行泛化的 MIP 嵌入，且通过无监督方式进行训练，无需最优解。

2. 方法论：Forge 框架

Forge（Foundational Optimization Representations from Graph Embeddings，基于图嵌入的基础优化表示）是一个框架，它在一个多样化的 MIP 实例集合上预训练了一个矢量量化图自编码器。其设计灵感源自自然语言处理（NLP）和计算机视觉（CV）中的基础模型。

核心架构

该框架通过以下阶段运行（图 1）：

1. MIP-to-BP（二分图表示）： MIP 实例被表示为变量和约束构成的二分图。
   • 节点特征： 与以往依赖求解器生成的特征（如来自分支定界树的特征）不同，Forge 仅使用基础输入属性：约束的方向（>, <, =）以及约束的右侧值（RHS）；变量的类型、边界和目标系数。这确保了模型不依赖于求解实例的过程。
2. BP-to-GNN： 一个基于 GraphSAGE 的 GNN（两层）处理二分图，以生成每个节点的连续嵌入。
3. 矢量量化码本（“词汇表”）： 为了解决 GNN 无法捕捉全局结构的问题，连续嵌入被传递到一个矢量量化器。该量化器将每个节点映射到来自大小为 $k$ 的可学习码本的离散代码（充当词汇表）。
   • 这一步骤通过在整个图中创建离散代码的分布来保留全局结构信息，类似于语言模型中的标记（token）分布。
4. 重构（自编码器）： 离散代码被映射回码字，并通过解码器重构原始节点特征和边权重。
5. 损失函数： 模型通过无监督方式进行训练，以最小化以下各项：
   • 重构损失（节点特征和边）。
   • 码本损失（将码字向嵌入移动）。
   • 承诺损失（将嵌入向码字移动）。

表示形式

训练完成后，Forge 生成两个层级的表示：

• 局部： 针对单个变量和约束的离散码字。
• 全局： 通过整个图中分配的编码的频率分布导出的实例级嵌入。嵌入的维度等于词汇表大小（$|codebook|$）。

3. 主要贡献

本文概述了五项主要贡献：

1. 基础模型步骤： 引入了 Forge，这是一个能够在无需监督的情况下，生成 MIP 实例级及细粒度（变量/约束）级嵌入的单一预训练模型。
2. 无监督泛化： 证明了 Forge 嵌入可以在不同问题领域和难度水平下，以高精度对未见过的实例进行聚类，其表现优于静态特征和标准 GNN 读取（readout）。
3. 监督适应性： 证明了同一个预训练模型可以通过极少量的、廉价标注的数据，在截然不同的下游任务（完整性间隙预测和搜索引导）以及变化的规模上进行微调。
4. 求解器集成： 成功将 Forge 的预测集成到商业求解器 Gurobi 中，证明了在多种问题类型上都能一致地改善原始间隙（primal gaps）。
5. ML 增强： 通过拼接 Forge 嵌入，增强了最先进的（SOTA）学习型方法（特别是 Li et al., 2025 和 PS-Gurobi），从而在未见过的实例上获得了显著的性能提升。

4. 实验结果

无监督聚类

• 设置： 在 1,800 个 MIPLIB 实例上训练；在涵盖 21 个领域-难度对的 1,000 个未见实例（来自 D-MIPLIB 和 strIPlib）上测试。
• 指标： 用于衡量聚类准确性的归一化互信息（NMI）。
• 表现： Forge 实现了 0.953 的 NMI，显著优于平均读取法（0.726）和标签传播法（0.790）。PaCMAP 可视化显示，尽管模型在训练期间从未见过这些特定实例，但仍能呈现出各问题类型的清晰簇，并展现出从易到难的清晰梯度。

任务 I：完整性间隙预测（伪割平面生成）

• 目标： 预测完整性间隙以生成根节点的伪割平面，从而收紧 LP 松弛界限。
• 训练： 在 450 个实例（CA, SC, GIS）上进行微调，标签由 Gurobi（120秒超时）生成，避免了寻求完全最优解。
• 结果：
  • 在“极难”测试实例（包括未在微调中出现的 MVC）上，Forge 在不同问题类型上的平均绝对偏差为 12–19%。
  • 求解器影响： 将 Forge 伪割平面集成到 Gurobi 中，与仅使用 Gurobi 相比，原始间隙最高可降低 85%（例如，在广义独立集问题上获得了 84.52% 的增益）。
  • 对比： 在 17,500 个未见实例上，其表现优于 Li et al. (2025) 的 SOTA 方法（18.63% 偏差 vs 20.14% 偏差）。

任务 II：搜索引导

• 目标： 预测哪些变量极有可能出现在最优解中，以引导分支定界搜索。
• 训练： 使用结合了二元交叉熵（BCE）和三元组损失（Triplet Loss）的 700 个实例进行微调。标签源自 5 分钟内找到的可行解（无需达到最优）。
• 结果：
  • 求解器影响： 使用 Forge 搜索引导的 Gurobi 在中等规模实例上实现了高达 48.75% 的原始间隙改善，以及高达 35% 的收敛时间加速。
  • ML 增强： 当用于增强 PS-Gurobi（一种 SOTA 学习型搜索引导方法）时，Forge 嵌入使原始间隙降低了超过 40%（组合拍卖）和 50%（广义独立集）。

5. 意义与主张

本文声称 Forge 代表了迈向优化领域基础模型的重要一步。其意义在于：

• 打破求解器依赖： 它在预训练过程中学习结构化表示，无需访问最优解或求解器的内部状态，解决了“先有鸡还是先有蛋”的问题（即需要用求解器来训练求解器）。
• 通用表示： 它证明了单一模型可以跨越迥异的问题类型（如集合覆盖、组合拍卖、顶点覆盖）和任务类型（间隙预测、搜索引导）进行泛化，而此前该能力受限于特定问题或任务的模型。
• 实际效用： 该框架不仅具有理论意义；它能直接集成到商业求解器中，并提升现有机器学习流水线的性能，提供即时且可衡量的效率增益。
• 开放科学： 作者发布了训练代码、预训练权重和嵌入，以促进表示学习领域的研究。

作者对其局限性保持了谦逊的态度，指出目前的规模（3.25M 参数）与其它基础模型相比较小，所学“词汇表”的语义尚待探索，且目前的集成是“单次”而非在分支定界树中迭代进行的。他们建议未来的工作可以将这些原则扩展到约束满足问题（CSP）和 SAT。