EvoOptiGraph: Weakness-Driven Coevolution via Graph-Based Structural Generation for Hard Optimization Problems¶

会议: NeurIPS 2026
arXiv: 2606.26578
领域: 优化/理论
关键词: 运筹优化建模, 混合整数线性规划, 图结构演化, 弱点驱动协同演化, 强化学习验证反馈

一句话总结¶

针对大语言模型在运筹优化建模中训练数据结构单一及静态分布脱节的问题，EvoOptiGraph 将混合整数线性规划建模为属性二分图进行保持有效性的遗传结构演化，并通过 XGBoost 与 SHAP 提取模型弱点特征，构建自适应强化学习闭环，以 8B 参数在六大运筹基准上取得了 78.1% Pass@1 的领先表现。

研究背景与动机¶

自动化运筹优化建模旨在将自然语言描述的实际业务决策问题转化为求解器可执行的规范数学规划代码（如 Gurobi），在智能制造、现代物流、能源调度与金融投资等领域具有极其广泛的应用价值。然而，建立高保真数学模型历来极度依赖运筹专家的跨领域建模与编程经验，建模者必须准确辨识出决策变量集合、目标函数方向与权重、复杂约束逻辑以及现实业务边界条件。近期大语言模型（LLMs）在该领域展现出了巨大潜力，但现有研究主要依赖推理阶段的复杂提示工程、多智能体协同框架或针对静态数据集的监督微调（SFT），在面对复杂运筹场景时仍频频发生约束遗漏、维度不匹配与求解器代码不可执行等建模失败。

当前技术推进面临两大致命瓶颈。其一，现有训练语料的结构多样性严重匮乏。主流运筹建模基准涵盖的数学结构模式非常狭窄，现存的数据合成管线多局限于针对固定专家模板做数值系数扰动或文本同义改写，仅能增加词汇多样性或表层规模，无法探索底层拓扑多变的混合整数线性规划（MILP）有效解空间。其二，现有的数据生成与模型训练处于完全割裂的静态状态。训练数据集一旦构建完成便被冻结，模型无法在训练中感知自身在高维运筹特征空间的薄弱环节，数据生成管线也无法定向针对模型的失败模式持续供给高价值的针对性训练样本。

针对上述两难困境，本文提出跳出“基于文本提示或参数扰动的静态数据合成”框架，将运筹建模的数据合成与模型训练紧密耦合为一个动态协同演化闭环。核心 idea：将混合整数线性规划建模为属性二分图，在保有效性约束下直接执行图级拓扑交叉与变异以生成高结构多样性实例，并通过基于验证集错误模式的 SHAP 弱点特征分析定向引导新样本演化，在可验证奖励强化学习（RLVR）中实现数据生成与模型能力的闭环协同进化。

方法详解¶

整体框架¶

EvoOptiGraph 的整体架构围绕“数据-模型弱点驱动协同演化闭环”展开，全流程覆盖图结构演化生成、确定性编译与逆向文本翻译、模型预热微调、基于 SHAP 的结构弱点诊断，以及基于求解器反馈的分阶段强化学习优化。系统首先基于 53 个经典运筹问题族构建初始二分图群体并衍生跨族杂交实例，经求解器验证与可逆回译生成初始数据集 $\mathcal{D}_0$ 进行 SFT 预热。随后在每一轮协同演化中，模型在保留验证集上的报错案例被映射到图拓扑特征空间，通过 XGBoost 分类器与 SHAP 解释归因出弱点权重向量 $\mathbf{w}$；遗传演化算法在适应度函数中激活弱点对齐项，定向合成命中盲区的高质量优化问题 $\mathcal{D}_{\text{RL}}$；最终通过组相对策略优化（GRPO）结合求解器运行、可行性、目标值逼近度及精确匹配的分阶段可验证奖励进行策略迭代。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["种子问题族<br/>(53个经典MILP生成器)"] --> B["属性二分图建模与结构演化<br/>拓扑交叉/多层级变异/跨族杂交"]
    B --> C["求解器验证与逆向回译<br/>Gurobi编译检验 + 三阶段文本生成"]
    C --> D["监督微调预热<br/>获取初始建模基线策略"]
    D --> E["结构化弱点诊断<br/>103维图特征提取 + XGBoost分类 + SHAP重要度"]
    E -->|计算弱点向量 w| F["弱点引导图演化<br/>激活弱点对齐项生成定向样本集 D_RL"]
    F --> G["可验证奖励强化学习<br/>分阶段连续奖励 + GRPO策略迭代"]
    G -->|更新策略模型| E

关键设计¶

1. 属性二分图表征与结构保真遗传演化：跳出参数微扰的拓扑级多样性合成 针对现有方法仅能通过参数微扰产生同构模板实例的局限，本文将通用 MILP 问题抽象为属性二分图 $\mathcal{G}=(V_{\text{con}}\cup V_{\text{var}}, E, \mathcal{A})$。约束节点集 $V_{\text{con}}$ 包含 $m$ 个业务约束节点与 1 个专属目标节点，变量节点集 $V_{\text{var}}$ 包含 $n$ 个决策变量节点。边集 $E$ 显式编码非零约束系数与目标系数，节点与边的属性集 $\mathcal{A}$ 则严格保存变量界限（下界、上界、变量类型）及约束方向与右端项。基于此可计算数学拓扑，算法实施保有效性的遗传操作： - 子图交叉算子：在兼容性评分超过阈值（考量变量类型分布、矩阵稀疏度、规模比例和优化方向一致性）的实例间交换连续约束行子块，同时按列独立继承变量并修复边界以杜绝孤立节点或不可行解，甚至支持创建混合耦合约束。 - 三层级变异算子：包含数值参数变异（扰动系数与右端项）、拓扑结构变异（增删或替换约束与变量边结构）以及规模变异（如扩增供需节点数量）。 - 复合适应度选择：候选个体的生存竞争受综合适应度函数调控： $$f(\mathcal{G}) = \beta \tilde{f}_{\text{diff}} + \gamma \tilde{f}_{\text{div}} + \delta \tilde{f}_{\text{weak}}$$ 其中难度项 $\tilde{f}_{\text{diff}}$ 取决于 Gurobi 求解用时与分支定界节点数，多样性项 $\tilde{f}_{\text{div}}$ 基于二分匹配逼近的图编辑距离（GED）惩罚结构塌缩，弱点对齐项 $\tilde{f}_{\text{weak}}$ 则在模型获得诊断证据后激活。

2. 基于可解释机器学习的结构化弱点诊断：从离散错误到连续弱点特征投影 以往训练机制无法精确定位大模型究竟在何种数学结构特征下容易发生建模崩溃。EvoOptiGraph 引入了一个从运筹数学结构直接提取特征并诊断薄弱环节的分析流水线。在每个协同演化轮次中，模型在保留验证集 $\mathcal{V}_{\text{val}}$ 上求解，收集其产生错误的代码与模型预测。对每一个验证实例抽取涵盖 103 个维度的图拓扑结构特征向量 $\phi(\mathcal{G})$，覆盖问题维度尺度、连续/整数/0-1变量比例、约束稀疏度与非零分布、系数均值及变异系数、目标与约束的余弦几何相似度、图谱与度分布偏度，以及 Big-M 模式与变量耦合度等。随后，训练一个深度限制为 4、经过互信息筛选保留前 20 个强关联特征的 XGBoost 二分类器，拟合“模型是否建模正确”的二元标签。对于所有预测失败的错误样本子集 $\mathcal{E}$，计算各个特征属性的 SHAP 归因绝对值： $$w_k = \frac{1}{|\mathcal{E}|} \sum_{i \in \mathcal{E}} \text{SHAP}_{i,k}$$ 所得的归一化权重向量 $\mathbf{w}=[w_1, \dots, w_d]$ 直观刻画了当前模型发生建模失误最核心的拓扑敏感特征组合。演化生成器通过计算候选图特征与弱点向量的余弦相似度 $\tilde{f}_{\text{weak}} = \text{cosine\_similarity}(\phi(\mathcal{G}), \mathbf{w})$，强力牵引群体向模型当前盲区演进。

3. 求解器分阶段可验证奖励与组相对策略优化：克服稀疏奖励的模型策略迭代 运筹建模代码的正确性必须经过实际求解器执行与极值验证，直接使用二值化（成功/失败）奖励会导致强化学习梯度稀疏且训练极不稳定。为此，EvoOptiGraph 提出了分阶段连续可验证奖励机制（RLVR）。对于模型生成的代码 $c$，总奖励定义为四个渐进阶段的总和： $$R(c) = R_{\text{process}}(c) + R_{\text{solvable}}(c) + R_{\text{proximity}}(c) + R_{\text{correctness}}(c)$$ - 代码可执行奖励：若 Python 脚本可无语法错误正常编译运行，赋予基底奖励 $R_{\text{process}}=0.2$。 - 解可行性奖励：若求解器成功求出可行解（非不可行且非无界），赋予 $R_{\text{solvable}}=0.1$。 - 数值逼近奖励：计算求解器求得的目标值 $f_{\text{model}}$ 与真实标注全局极值 $f_{\text{opt}}$ 之间的相对误差 $\text{relerr} = \frac{|f_{\text{model}} - f_{\text{opt}}|}{|f_{\text{opt}}| + 10^{-8}}$。若相对误差处于 $10\%$ 以内，线性退火赋予数值接近奖励 $R_{\text{proximity}} = 0.2 \cdot \max(0, 1 - \text{relerr} / 0.1)$，有效引导仅发生微小系数推导偏差的候选策略。 - 严格精确匹配奖励：当求解器状态为最优且 $\text{relerr} \leq 10^{-4}$ 时，额外注入 $R_{\text{correctness}}=0.5$ 的大额正确性奖励，使得总奖励被严格约束在 $[0, 1]$ 之间。优化阶段采用组相对策略优化（GRPO），针对每个自然语言问题采样 $N=4$ 条候选代码，组内标准化计算优势值 $\hat{A}_i$，结合相对于 SFT 策略的 KL 散度正则项执行 LoRA 参数优化，防止策略在强化学习探索中退化。

损失函数 / 训练策略¶

训练过程严格分为预热与协同演化两个阶段： 1. SFT 阶段：基于初始生成的 5,000 个高质量验证图-代码对，在 Qwen3-8B 基座模型上采用 LlamaFactory 框架，使用 LoRA（rank=32, alpha=64, dropout=0.05）以 $1\times 10^{-4}$ 学习率微调 3-5 个 epoch，优化标准代码自回归交叉熵损失 $\mathcal{L}_{\text{SFT}}$。 2. RLVR 协同演化阶段：在 TRL 框架下运行 GRPOTrainer，对 LoRA 适配器进行持续更新。采样温度为 0.7，学习率为 $5\times 10^{-6}$，进行 3 轮协同演化迭代。每轮迭代重新从验证集抽取 2,000 个实例刷新弱点权重 $\mathbf{w}_t$，并定向演化合成 1,000 个极具挑战性的针对性实例供当前策略强化学习微调。

实验关键数据¶

主实验¶

评估在六个经过清洗的标准运筹基准上进行，包括 NL4Opt、MAMO (EasyLP 与 ComplexLP)、NLP4LP、ComplexOR 以及 IndustryOR，采用一次通过率（Pass@1 准确率，%）作为核心指标，要求代码求解的目标值与真值完全匹配。

数据集 / 基准	指标	EvoOptiGraph (8B)	GPT-4o (Closed)	DeepSeek-V3 (671B)	Qwen2.5-72B-Inst	OptiMUS-v0.3	之前开源微调最优 (ORLM 8B)
NL4OPT	Pass@1 (%)	96.7	73.4	79.9	79.9	79.8	73.8
MAMO (EasyLP)	Pass@1 (%)	98.0	95.2	96.7	95.8	92.4	90.4
MAMO (ComplexLP)	Pass@1 (%)	69.4	46.0	55.0	33.3	52.1	59.5
NLP4LP	Pass@1 (%)	97.2	87.6	94.9	89.9	89.8	76.4
ComplexOR	Pass@1 (%)	50.0	38.9	44.4	38.9	52.2	50.0
IndustryOR	Pass@1 (%)	57.1	66.7	69.1	61.9	54.3	42.9
宏平均 (Macro-Avg)	Pass@1 (%)	78.1	68.0	73.3	66.6	70.1	65.5

(注：基线数据中 ComplexOR 最优为 OptiMUS 的 52.2%，EvoOptiGraph 取得 50.0%；在宏平均指标上，EvoOptiGraph 以 78.1% 大幅领先 671B 参数的 DeepSeek-V3 的 73.3% 与 OptiMUS-v0.3 的 70.1%)

消融实验¶

为验证两阶段协同训练机制的不可替代性，作者设计了剔除强化学习协同演化的全量监督学习（All-SFT）与剔除监督预热的全量强化学习（All-RL）对比实验。

训练配置	NL4OPT	MAMO-Easy	MAMO-Complex	NLP4LP	ComplexOR	IndustryOR	宏平均 Pass@1	相对完整模型变化
EvoOptiGraph (Full)	96.7	98.0	69.4	97.2	50.0	57.1	78.1	-
All-SFT (仅SFT)	85.5	96.0	55.9	91.6	38.9	42.9	68.5	↓ 9.6%
All-RL (仅RLVR)	72.0	96.3	33.3	87.6	38.9	52.4	63.4	↓ 14.7%

此外，在数据生成多样性评估方面，基于 GenBench-MILP 的结构相似度评估显示： - OptMATH 合成数据结构相似度：$93.04\%$（表明主要局限于种子模板的参数微调，结构分布严重趋同）。 - EvoOptiGraph 合成数据结构相似度：$66.93\%$（相似度显著降低，证明图遗传演化和跨族杂交带来了更宽广的拓扑覆盖度）。

关键发现¶

两阶段范式的必要性显著：全监督微调（All-SFT）在第一轮快速收敛，但由于缺乏求解器真实结果的闭环奖惩，后续多轮微调迅速过拟合于合成语料的文本表达，最终均分仅 68.5%（落后 9.6%）；全强化学习（All-RL）由于缺失初始语法与数学建模基础先验，冷启动阶段探索效率极低，在复杂的 MAMO-Complex 上暴跌至 33.3%，均分仅 63.4%（落后 14.7%）。
跨族结构杂交大幅突破数据多样性瓶颈：通过在 53 类基准问题间引入 30 种跨族复合约束（如生产调度与背包问题的资源杂交），使生成数据在结构相似度指标上从 93.04% 骤降至 66.93%，有效消除了大模型在长尾复杂结构上的泛化盲区。
协同演化轨迹呈现自修正特性：在协同演化进程分析中，模型在第二轮强化学习（RL2）阶段可能出现对特定弱点样本的局部过拟合（如 MAMO-Complex 暂时波动），但在随后的第三轮演化中，新一轮 SHAP 弱点检测能够迅速动态重置演化重心，使模型最终重拾并超越峰值性能。

亮点与洞察¶

拓扑级运筹实例演化：巧妙规避了传统 NLP 文本同义替换或纯系数微调的浅层合成方式，将数学规划建模为属性二分图，在图拓扑级别操作子图拼接与变量耦合，彻底解决了合成数据“同质化”难题。
SHAP 弱点引导的数据协同进化：打破了静态固定数据训练的陈旧范式，把机器学习可解释性工具（SHAP）逆向用作生成器的适应度先验，形成“模型出错 $\rightarrow$ 归因拓扑弱点 $\rightarrow$ 定向演化补短板 $\rightarrow$ RL 更新”的高效正向循环。
可复用的分阶段连续可验证奖励：针对代码执行与数学建模任务中稀疏奖励阻碍探索的痛点，设计了涵盖语法执行、可行性、十进制相对误差线性逼近到精确匹配的渐进奖励梯度，极大提升了强化学习策略在严苛符号任务中的收敛稳定性。

局限与展望¶

问题形式覆盖局限：当前框架仅针对混合整数线性规划（MILP），尚无法直接支持非线性规划（NLP）、半正定规划（SDP）或二阶锥规划等更广泛的运筹问题族。
验证效率受求解器规模制约：随着生成的图节点规模和约束复杂性急剧提升，调用 Gurobi 进行可行性验证和分支定界指标提取的计算开销显著拉长。
弱点相关性不等于严格因果关系：基于树模型 SHAP 提取出的高权重拓扑特征本质上是统计相关性表征，未必构成大模型理解失误的本质因果机制，未来可结合因果推断进一步提纯弱点信号。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出运筹建模领域的属性二分图结构演化与基于可解释 SHAP 弱点引导的闭环数据-模型协同演化架构。
实验充分度: ⭐⭐⭐⭐⭐ 在六大公认权威基准上与大体量闭源模型、开源巨型模型、Agent框架和微调模型做了详尽对比，消融与演化轨迹分析极其完备。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰严谨，形式化定义精炼完备，图论拓扑表示、遗传算法与强化学习公式推导自洽且表达自然。
价值: ⭐⭐⭐⭐⭐ 为运筹优化、符号数学推理乃至广义代码智能领域解决高质量训练语料匮乏与定向能力对齐提供了极具价值的方法学范式。