论文理解【LLM-OR】—— 【PaMOP】Guiding large language models in modeling optimization problems via question partitioning

首发链接：论文理解【LLM-OR】—— 【PaMOP】Guiding large language models in modeling optimization problems via question partitioning
文章链接：Guiding large language models in modeling optimization problems via question partitioning
发表：IJCAI 2025
领域：LLM OR
一句话总结：使用 LLM 对运筹优化问题（OR Problem）建模时，传统方法通常将整段自然语言描述一次性端到端生成完整优化模型/求解代码（或配合少量 CoT、反思与求解器报错自修正），但在大规模/长文本场景易因约束耦合复杂而出现漏约束、混淆变量参数与格式不稳定导致可执行性与正确率下降；本文提出 PaMOP，先将约束按变量关联与语义相似度划分成问题树并分块建模，再结合迭代纠错与验证（含求解器反馈与反向翻译一致性检查）合并为全局模型，从而在复杂实例上实现更高的可执行率与建模准确率

摘要：优化问题在资源调度、生产规划和销售管理等诸多领域普遍存在。传统上，这类问题通常需要人工建模；由于建模专家与领域专家之间沟通与协作困难，往往导致效率低下。大型语言模型（LLMs）的出现使自动化建模成为可能。然而，真实世界应用通常规模大、变量与约束数量众多，从而限制了现有方法的适用性。为了解决这一问题，我们提出 PaMOP —— 一种基于 LLM 的新型建模框架，仅给定自然语言描述即可自动对优化问题建模。具体而言，我们使用树结构对问题进行抽取与划分，引导 LLM 结合自增强提示对每一组约束进行建模，从而降低对 LLM 处理长上下文能力的要求。随后，通过我们的纠错流程对数学模型进行迭代修正与验证。实验表明，我们的方法在通用基准数据集 NLP4LP 上提升了性能：在 GPT-4 上测试时，准确率达到 62.3%，代码可执行率达到 86.8%。此外，我们还展示了 PaMOP 在处理大规模真实世界问题上的有效性

1. 背景：运筹问题建模

本文研究优化问题的自动建模与编程，以减轻对人类专家的严重依赖。具体而言，这类问题要求输入一段自然语言描述的问题（如配送货、生产规划等问题），要求模型或系统完成运筹学建模，并生成问题求解代码。近期研究常借助 LLM 丰富的领域知识和推理能力完成建模

具体地，一个优化问题通常由一个唯一的目标函数与若干约束刻画，目标是将初始问题描述数学建模为：
$\max _{x} f(x) \quad \text { s.t. } \quad \forall i \in 1 . . n, g_{i}(x) \leq 0$

问题 $q$ 的数学模型可表示为 $M=\left(m_{p}, m_{v}, m_{o}, m_{c}\right)$ ，其中 $m_p$ 表示问题约束中的常量或参数， $m_v$ 表示决策变量 $x$ ， $m_o$ 表示目标函数 $f(x)$ ，而 $m_c$ 表示问题的约束 $g(x)$ 。这种四元组表示方法和 AMPL（以及 GAMS/OPL 这类代数建模语言）的核心组成高度一致，因此可以对应生成 AMPL 文件，再调用 gurobi 等求解器完成求解
针对该任务，当前主要存在基于提示和基于微调的两类方法：
1. 基于微调的建模fine-tuned LLM modeling agents：通过构造大规模运筹学及建模知识对 LLM 进行微调，形成专用的建模语言模型，如 ORLM
2. 基于提示的建模prompt-based modeling：通过为 GPT-4o 等大规模预训练 LLM 精心设计建模 Prompt 来工作，可以引入多智能体协作流程或蒙特卡洛树搜索等技术
  当前该类方法基本流程如下：
  1. 在接收到优化问题的描述后，提取关键信息并以特定格式结构化；
  2. 使用提示词引导 LLMs 构建问题模型；
  3. 与 LLMs 进行迭代交互，识别并消除生成模型中的错误
  4. 完成建模后，将生成的模型与原问题数据文件一并输入求解器求解
  5. 当输出得到满足问题要求的最优解时，认为建模是正确的
本文聚焦于基于提示的方法，作者认为现有方法未能充分利用 LLMs 的建模能力，通过提示词引导 LLMs 进行优化问题建模仍面临若干挑战
1. 如何获得满足要求的输出：LLM 生成的模型常无法满足期望的格式或内容标准，例如只生成对问题的文本分析或 markdown 形式的数学模型，而非规范的代码格式
2. 如何处理大规模问题：问题规模会限制 LLM 生成准确模型的能力，从而出现遗漏约束或混淆变量与参数等问题，特别是在需要长文本推理的情况下
3. 如何提高建模输出的准确性：现有纠错方法多聚焦于提升模型在求解器上的执行成功率，但并未解决模型中的逻辑错误，而逻辑错误会直接影响模型的准确性与质量

2. 本文方法

为了充分发挥 LLM 的建模推理能力，本文提出基于 LLMs 的自动化优化问题建模框架 PaMOP

如图所示，PaMOP 首先利用 LLM 提取问题信息，随后通过树结构，从数学和语义两个层面将约束条件分解为更简单的子问题。借助该划分树，使用自增强提示（self-augmented prompts）引导 LLMs 为每一组约束建模，这些节点随后自底向上合并为完整模型。最终，数学模型通过语法检查、代码执行和逆向翻译进行迭代校正，直至无错误

2.1 问题划分树

本文使用 “分而治之” 思想降低 LLM 的工作负担，即把一个复杂问题拆分成若干较简单的子问题，分别解决再合并，尽量让 LLM 在任何一次关键生成时都不要背负整段长文本，从而允许 LLM 解决整体难度超出其能力上限的复杂问题
- 传统方法在 “生成模型” 这一步必须同时完成长文本理解和数学建模生成，复杂问题上下文长度可能很长，且约束相互耦合，容易导致 LLM 出现遗漏/混淆/格式漂移等问题：
- PaMOP 通过树结构对原始长文本问题描述进行拆分，将其压缩成多个更短、更结构化的输入，从而使 LLM 上下文长度和耦合度显著降低。：
  1. 从原文抽出目标描述 $t_o$ ，按条列出的约束文本 $t_c$ 、变量/参数信息 $t_v$ 和全局摘要 $g$
  2. 使用树结构对所有约束文本 $t_c$ 做分块，让后续每次生成只面对一小组约束 $t_{c,i}$ ，但仍带着 $g$ 和 $t_v$ 作为全局上下文
PaMOP 使用 约束集合constraint set 从原始描述中得到相对独立的子问题，划分过程从包含全部问题信息的根节点开始，每层划分把节点拆分成若干子节点，每个子节点内部的约束高度相关，不同子节点之间的约束相关性较弱，划分得到的叶节点代表需要建模的子问题。具体而言，划分树的构建过程如下：
1. 抽取结构化表示：使用 LLM 从原始问题描述中抽取结构化要素 $\{t_o, t_c, t_v, g\}$ 存入根节点，其中 $g$ 是问题的全局摘要， $t_o$ 是目标函数函数文本描述， $t_v$ 是变量与参数信息， $t_c = \{(c_1, v_1), (c_2, v_2), \dots\}$ 是约束集合的文本描述，且每条约束描述 $c$ 对应一个 LLM 生成的模糊度分数 $v$
  
  注意这里仍然需要 LLM 对完整问题描述进行长上下文理解，这一点是难以回避的，因为因为信息分散在全文。PaMOP 的思想是承认全篇理解不可避免，但尽量不要让 “高精度建模/代码生成” 也同时承受全篇长度，它降低的是“建模/生成阶段”的长上下文负担，但并没有消除“理解原始长文本”的需求。这也是本文方法的一个缺点，如果第一步的提取就错了，后面分解也会是错误的
2. 独立集合分离：划分的第一步是基于变量分离相互独立的子问题：构建一个二部图，其中一类节点是约束，另一类节点是变量，若约束文本与变量/参数描述在关键词层面呈现高置信匹配，则在二部图中连边。若该二部图可以分解为多个互不相交的连通子图，则对应的约束集合可以被拆分为相互独立的子问题。我们对根节点应用这一分离策略，以获得第一层子节点，它们对应 “变量层面独立” 的子问题
3. 约束集合聚类：仅靠独立集合分解难以有效降低问题难度，因为很多真实问题的约束会通过少量全局变量连起来，导致断不开或断得不细。因此，对于每个需要继续分解的节点，我们将其约束聚成若干集合，从而生成新的子节点，每层划分目标是让子节点内约束更相关、子节点间相关性更弱（论文未强调约束集合严格不重叠，且聚类噪声点会被保留）。重复进行 “聚类—生成子节点” 的过程，直到节点已足够简单或无法继续有效划分，由此得到的叶节点将作为后续建模的子单元
  
  为进行聚类，约束之间距离定义为两条约束相似度 $s_{i, j}$ 的反函数
  $d_{i, j}=\frac{1}{s_{i, j}+\varepsilon}-\frac{1}{1+\varepsilon}$
  
  其中 $\varepsilon$ 是一个固定小值，如下图所示，这种距离方式可以使 $s_{i, j} \to 0$ 时约束间距离迅速增大
  具体地，约束间相似度由三部分加权求和得到，且在树的不同层使用不同权重，以适配从“粗”到“细”的逐层划分：在更高层更强调结构与相邻关系，在更低层更强调语义内容的相似度
  1. 邻接/上下文关系：约束通常按顺序抽取，相邻更可能相似，因此 “优先给相邻约束更高相似度”
  2. 关键词相似度：取两条约束各自 TF-IDF 的 top-k 关键词，共同关键词数决定相似度
  3. 向量相似度：GloVe（Wikipedia 2014）embedding 的余弦相似度
一个示例如下，原始问题由问题描述和数据文件组成（AMPL格式特点，建模可以和数据分离），仅靠 LLM CoT 推理常遗漏约束，而 PaMOP 可以正确完成建模

下图是问题划分树的示例

图中约束 4 同时出现在两个叶节点（Node1/Node2）。论文正文未明确说明划分是否强制约束集合互斥；结合作者‘noise points 保留’的设定，可能存在跨子问题的耦合/边界约束被重复保留用于后续纠错与合并（此处以原图为准）

2.2 求解器模型的生成与改进

2.2.1 构建求解器模型

通过 2.1 节方法完成建模树构建后，PaMOP 使用提示工程引导 LLM 对所有叶节点进行建模，这些模型会被合并为一个完整的 AMPL 数学模型，在补充数据文件后即可直接运行求解
对第 $i$ $i$ 个叶节点对应的局部模型 $m_i$ $m_{i}$ 进行建模时，需要该节点的约束描述 $t_{c}$ $t_{c}$ 、变量信息 $t_v$ $t_{v}$ 和全局摘要 $g$ $g$ ，以确保 LLM 在建模时保持对整体问题的认识，表示为
$m_{c, i}=G_{\bmod }\left(g, t_{v}, \bigcup_{j \in \operatorname{cons}_{i}} t_{c, j}\right)$
其中 $\operatorname{cons}_{i}$ $c o n s_{i}$ 表示节点 $i$ $i$ 所包含的约束列表， $t_{c,j}$ $t_{c, j}$ 表示 $t_c$ $t_{c}$ 中第 $j$ $j$ 条约束（包含文本和模糊度分数）
- 受 CoT 方法启发，作者在 prompt 中引入了用于 “指定优化问题” 的完整流程，并提出了一组用于优化建模任务的原则，以提升 LLM 输出的稳定性
- 对于“模糊约束”的建模，不同约束的模糊程度可能不同，导致逻辑一致性难以保证；借助树结构分解原问题后，在对包含模糊约束的节点建模时，可以引入其父节点与兄弟节点的信息来辅助建模
  
  在叶节点建模时引入全局摘要 $g$ 、父节点与兄弟节点信息有助于保持对整体问题语境的理解，但也可能将不属于该叶节点的信息带入局部约束生成；PaMOP 通过后续基于求解器/反向翻译的纠错验证来缓解该风险
当每个叶子节点分别完成建模后，自底向上逐层合并为完整模型。由于常量与变量** $t_v$ 已预先描述，不同节点生成的公式之间冲突较少，因此可以直接合并这些公式，并在根节点完成目标函数建模。最终完整模型 $M=\left(m_{p}, m_{v}, m_{o}, m_{c}\right)$ 是给定全局摘要 $g$ 、变量信息 $t_v$ 、目标描述 $t_o$ 的条件下，将合并得到的约束内容 $m_c$ 组装进来生成的。对于 LLM 来说，自然语言、数学公式、程序代码都是某种 “语言”，因此PaMOP 输出的是 AMPL 建模文件（代数建模语言）而非数学公式**

2.2.2 错误纠正

模型构建完成得到 AMPL 代码 $M$ $M$ 后，作者使用了多步错误纠正方法
1. 基础检查：通过正则表达式检查 AMPL 语法、检查 AMPL 文件和对应的输入数据文件是否对应
2. 使用 Self-Edit 方法进行多步径迭代修正：基本思想是用 AMPL 调用 gurobi 求解 $M$ ，如果出现失败/异常报错，就把执行结果/错误信息整理成一个辅助注释 $e$ 加入 prompt，修正得到新模型 $M$ ，如此反复进行多步修正。这步主要是为了确保代码可执行，形式化表示为 $\begin{aligned} \operatorname{solution}(a n s, e) & =\operatorname{Solve}(M, \text { data }) \\ M & =\mathcal{G}_{\text {exe }}(M, e) \end{aligned}$
3. 通过 逆向翻译 reverse translation 处理逻辑不一致：若问题仍然存在，针对 $M$ $M$ 中每一条约束单独进行逆向语义翻译和语义对比。这里略微滥用符号，设 $m_c$ $m_{c}$ 是某条被检查的约束，它是由 AMPL 代码 $m_c'$ $m_{c}^{'}$ 和意图注释 $t_c$ $t_{c}$ 共同组成的，整个逆向翻译修正流程形式化表示如下
  $\begin{aligned} t_{c}^{\prime} & =\mathcal{G}_{\mathrm{rev}}\left(m_{p}, m_{v}, m_{c}^{\prime}\right) \\ \mu & =\mathcal{G}_{\mathrm{comp}}\left(t_{c}, t_{c}^{\prime}\right), \mu \in\{0,1\} \\ M & =\mathcal{G}_{\mathrm{remod}}\left(T, m_{c}, \mu\right) \end{aligned}$
  1. 准备约束对应的 “注释信息”：PaMOP 建模过程中，会为每条约束 $m_c$ 附带一些注释/意图描述 $t_c$ ，可以理解为 “这条约束在建模树里对应哪句原文、想表达什么”
    
    文章指出注释信息是从对划分树和生成过程的分析中提取的，但没有清晰说明这些注释信息如何存储，但从工程角度说要么是注释在 AMPL 代码中，要么在构建划分树生成 $M$ 时即生成并存储，因此此处大概不需要回溯划分树
  2. 隐去约束对应的 ‘’注释信息“ $t_c$ ，只留下约束代码 $m_c'$
  3. 逆向翻译约束，将优化目标、优化变量和去掉注释的约束代码 $m_c'$ 输入 LLM，令其重新用自然语言解释 $m_c'$ 的意图，得到 $t_c'$
  4. 使用 LLM 对比 $t_c,t_c'$ 的语义，输出语义是否一致的二值判定
  5. 对所有约束完成以上1-4步后，认为所有反向翻译的约束语义 $t_c'$ 和真实语义 $t_c$ 不同的约束建模有误，把这些 “有问题的约束” 连同原问题文本/模型上下文交给 LLM，让它重新解释并重生成这些约束，并更新模型 $M$

3. 实验

3.1 实验设定

LLM 设定：使用 GPT-4 对 PaMOP 框架进行测试，温度设置为 0.2，失败迭代最大次数为 5。默认情况下，输入问题，输出 AMPL 语言的建模文件，调用 Gurobi 求解该模型并获得目标值
评估指标：
1. 成功率 accuracy
2. 可执行的模型文件比例 execution rate
3. 生成程序中无法编译的比例 compile error rate, CE rate，这可能由建模过程中缺失参数等原因导致
4. 执行过程中发生错误的比例 runtime error rate, RE rate，这些错误多源于模型内部的逻辑错误（例如不可行模型或非线性约束）
数据集：使用 NLP4LP 数据集进行主实验，使用一组大规模真实世界问题进行扩展实验
- NLP4LP 包含线性规划（LP） 与 混合整数线性规划（MILP） 的自然语言建模任务。问题类型主要源自教材与讲义，PaMOP 使用的版本包含 54 个 LP 问题与 13 个 MILP 问题
- 自定义优化问题数据集包含与存储、调度、选址/布局、采矿和人力资源分配相关的问题，问题规模较大，旨在评估我们方法在实际环境中的适用性。例如，“Storage” 这一实例涉及 3,795 个参数、124 个决策变量以及 162 条约束
基线方法：
1. 不使用任何推理增强的默认 GPT 模型，记为 default，这时仅向模型提供需要完成的任务要求，而不添加任何额外的推理提示或增强策略
2. 四种基于 LLM 增强推理（LLM-enhanced reasoning）的基线方案，包括 CoT、Progressive Hint、ToT 与 Reflexion；
3. 利用 LLM 进行优化问题建模的方法 Optimus。该方法的核心是维护一个 “约束/变量相关性” 二部图，这样每次生成/修复某条约束时，只检索并喂给 LLM 与其相关的最小上下文，从而让 prompt 保持短、输出更稳定，并支持规模化处理长文本与大数据文件。Optimus 使用多 agent 架构，引入 Formulator、Programmer、Evaluator 分别负责数学建模、求解器代码编程和生成结果评估，这些 agent 在一个 manager agent 的规划下交替行动
  Optimus 维护的二部图和 PaMOP 划分第一层子问题时的二部图相同，但用法不同
  - Optimus 持续维护二部图，贯穿“公式化→写代码→调试修复”的多代理循环，保证变量/参数名一致，并实现相关短上下文提取
  - PaMOP 的二部图用作一次性的结构分解工具，后续主要靠约束相似度聚类来分解，从而缩短上下文

3.2 实验结果

NLP4LP 和真实世界问题上的性能如下
1. CoT 等简单方法对该任务带来的提升有限，Reflexion 和 Optimus 等引入预处理步骤与自我反思机制获得了更高的准确率
2. NLP4LP 任务上，PaMOP 比 Optimus（SOTA）正确率高 5%，真实世界问题上也更优

3.3 消融实验

使用 GPT4 模型，从简单的纯 prompt baseline 开始，逐步加入 PaMOP 组件
1. PromptOnly. 使用特定提示引导 LLM 按给定格式输出解，并使用 few-shot 学习以获得更好的任务理解
2. Partition + Prompt. 划分模块将问题拆分为更小的部分，分别建模后再进行组合
3. Partition + Prompt + Correction. 增加错误纠正模块以处理不可行模型，并执行检查与逆向翻译（reverse translation）
消融实验说明 PaMOP 的性能增益可归因于对问题的细粒度分解以及基于多角度反馈的模型优化，这一多层次的优化过程确保模型在面对复杂优化问题时能够以更高的精度与效率进行推理，去掉任意关键组件都导致性能显著下降

3.4 不同基座模型

对比了使用 GPT-3.5-turbo、GPT-4 与 Llama-3.3-70b 作为基座模型的效果

观察到 PaMOP 均超越了对比基线

4. 总结

4.1 文章总结

优化问题的自动建模与编程任务存在输出格式要求严格、大规模复杂任务建模困难、仅靠求解器反馈难以纠正建模逻辑错误等挑战。PaMOP 使用以下方式应对挑战
1. 引入划分树，将 “复杂问题描述上下文 -> 严格式要求代码” 的端到端生成过程拆分为 “问题描述理解 -> 子问题建模 -> 总体建模代码生成 -> 建模纠正” 等多个环节，降低每个环节复杂度
2. 利用 LLM 的代码理解能力进行反向翻译，识别建模中的逻辑错误
本文写作比较粗糙，很多细节没有写清楚，比如超参数设定、约束聚类使用的算法等等，实验范围也比较小，很多地方使用了较强的启发式手工设计，比如约束聚类时的加权比例等，观感不佳

4.2 相似方法对比

PaMOP、Optimus、OptiTree 这几个方法很相似，它们都在用某种 “结构化分解（图/树）+ 迭代纠错” 来对抗长上下文、严格格式与逻辑错误。但它们分解的对象不同、树/图的角色不同、纠错信号不同，所以适用场景也不一样
分解对象不同：PaMOP 是 “约束分块”；OptiMUS 是 “约束条款级流水线”；OptiTree 是 “子问题谱系/建模套路检索”
1. PaMOP：围绕“约束集合”建一棵 partition tree
  - 根节点用 二部图（变量/常量–约束） 做“独立子图分离”，后续层用约束相似度聚类继续细分，直到叶子约束数少或相似度高
  - 叶节点分别建模，再自底向上合并成完整 AMPL 模型
2. OptiTree：围绕“OR 问题的子问题分解”建 modeling tree（带检索/树搜索）
  - 把问题分解为一系列语义包含关系的子问题，并在树节点中存储“建模思路（modeling thoughts）”，让新问题通过树搜索匹配并组合这些思路来建模
  - 强调“在树上识别最大子问题→整合思路→生成模型”
3. OptiMUS/Optimus：围绕“clause（条款）”逐条公式化+写代码+调试
  - 明确维护一个 connection graph（条款↔变量/参数的二部结构），用于每次只检索该条款相关的最小上下文，从而可扩展到长描述与复杂数据
图/树在系统里的 “生命周期” 不同
1. PaMOP 的二部图是一次性的“根节点切分工具”，随后主力是 “约束相似度→距离→聚类→继续分解”；问题划分树是针对每个新问题在线构建的，相比 OptiTree 在线推理成本高
2. OptiMUS 的关联图是持续维护的“工作记忆/索引”，贯穿公式化、写代码与调试，用来控制 prompt 长度并保持一致性
3. OptiTree 的树更像一套“可复用知识库”：节点里存的是从真实建模过程“蒸馏”出来的高层建模思路，在线时通过树搜索组合这些思路，离线还会更新树以增强可扩展性与可靠性。

机器学习 > 论文理解

#LLM #LLM-OR

论文理解【LLM-OR】—— 【PaMOP】Guiding large language models in modeling optimization problems via question partitioning

https://wxc971231.github.io/MyBlog/2026/01/25/论文理解LLM_OR_PaMOPGuidinglargelanguagemodelsinmodelingoptimizationproblemsviaquestionpartitioning/

作者

云端fff

发布于

2026年1月25日

许可协议

论文理解【LLM-OR】——【Step-Opt】Training LLMs for Optimization Modeling via Iterative Data Synthesis and 上一篇

论文理解【LLM-OR】——【ORLM】Training Large Language Models for Optimization Modeling 下一篇