利用LP2Graph进行LP挖掘：铁路重新调度的一个用例

# 基于LP2Graph的线性规划挖掘：铁路列车调整的应用案例  
来源：https://arxiv.org/html/2607.11980  

\[ orcid=0009-0005-6050-7596 \]\\cormark\[1\]\\creditConceptualization, Methodology, Software, Data curation, Investigation, Visualization, Writing – original draft\\creditConceptualization, Supervision, Writing – review & editing\\creditSupervision, Writing – review & editing  
1\]organization=德累斯顿工业大学, addressline=铁路运营教席，“弗里德里希·李斯特”交通与运输科学学院, city=德累斯顿, postcode=01069, country=德国  
2\]organization=德累斯顿工业大学, addressline=ScaDS.AI 德累斯顿/莱比锡，可扩展数据分析软件架构教席, city=德累斯顿, postcode=01069, country=德国  
\\cortext\[cor1\]通讯作者  

###### 摘要  
与许多优化驱动的领域一样，铁路列车调整依赖混合整数线性规划（MILP），但该领域的建模知识分散在数百篇论文中，符号不兼容，而叙述性综述则主观地组织这些知识：它们按词汇而非结构对模型进行分类，且既不重现这些模型也不重现其分类。我们提出*基于LP2Graph的线性规划挖掘*，该方法将已发表的LP和MILP公式的结构挖掘为可复现的数据集和由此导出的分类体系。其核心*LP2Graph*将其规范语法接受的每个公式表示为从单一规范模型导出的类型化的变量-方程图；一旦将源文献提取到该模型中，下游所有步骤都是确定性的。每个源文献都被解析为该模型，进行同源化处理，并自底向上聚类（先变量，然后约束和目标，最后整体模型结构），同时按应用领域和求解方法分别聚类；产生的类别由规则种子、自更新分类器进行标注。我们验证而非假设该表示的有效性：每个聚类代表案例作为独立的LaTeX重新生成，并在CBC、HiGHS和Gurobi上重新求解，与源文献中报告的最优值进行比较。结果是变量、约束和模型类型的客观、可重复的分类体系：这是我们*raiLPminer*自动化铁路列车调整模型开发系列工作的原则基础。  

###### 关键词：混合整数线性规划\\sep铁路列车调整\\sep优化模型挖掘\\sep图表示\\sep分类体系\\sep可复现的文献分析\\sepraiLPminer  

\{highlights\}  
一个确定性的、基于图的方法，用于从文献中挖掘LP和MILP公式的结构  
LP2Graph类型化的变量-方程图可实现无求解器的结构比较和特征提取  
自底向上的多层聚类和两阶段标注产生变量、约束和模型类型的可复现分类体系  
通过往返翻译和跨求解器复现已发表最优值来验证表示保真度  

## 1 引言  

许多领域，如生产调度、车辆路径规划、服务网络设计和能源调度，将其最困难的计划和控制决策表述为混合整数线性规划（MILP）（nemhauser1988），并且每个领域都已将数十年的运筹学（OR）建模知识沉淀在已发表的公式中。本文旨在使这些知识变为机器可读；铁路列车调整是我们展示该方法的应用领域，它也是一个具有挑战性的领域。当中断使预定时刻表失效时，操作员必须在严格的安全、容量和衔接约束下重新规划路线、重新排序和重新调整列车时间，而运筹学研究已经为此产生了丰富的恢复模型和算法库（cacchiani2014;ReschReview2023;besinovic2020;railrev2022）。然而，这个库几乎完全以散文和数学公式的形式散落在数百篇论文中，每篇都使用自己的符号体系。真正重要的建模知识（哪些变量承载哪些决策，哪些约束族反复出现，整体公式如何构建）是分散的，并且以其当前形式，既不可搜索，也无法跨来源进行比较。  

整合这类工作的传统方式是叙述性文献综述或评述。这些综述主观地总结该领域：它们既不可复现也无法量化，并且它们根据领域词汇而非公式本身的结构对公式进行分类（ReschReview2023;railrev2022）。两个具有相同底层结构但使用不同词汇的公式被分置不同类别；两个共享词汇但结构不同的公式却被归为一类。其后果是具体的：一位实践者需要通过中断瓶颈重新排序和重新调整列车时间，他会找到一个铁路列车调整公式（veelenturf2016rescheduling）和一个作业车间调度公式（ku2016jobshop），它们被归入不同的文献。然而，从结构上看，两者都是析取的“谁先走”排序模型，对于微观层面的瓶颈调度，作业车间模型实际上更贴合问题——列车调度本身就是带阻塞的作业车间调度（dariano2008reordering）。标题页命名了领域；只有结构才能揭示模型是否适合问题，而基于词汇的分类综述无法揭示这一点。  

目前，关于铁路列车调整模型实际上是如何构建的，还没有客观、可复现、结构化的描述，而评审者越来越期望选择过程本身遵循有记录的系统综述协议，如PRISMA（page2021prisma），这类叙述性综述无法提供这一点。这一缺陷并不仅限于铁路领域，而本文方法所利用的正是这种结构上的亲缘关系，而非声称要填补某个独立的空白。列车时刻表恢复公式与更广泛的交通文献具有密切的结构亲缘关系，并且更松散地与生产调度以及一般的路径与调度模型（如车辆路径规划、作业车间调度和服务网络设计（toth2014vrp;pinedo2016scheduling;crainic2000snd））相关联，它们共享变量模式（分配、排序、流）和约束族（优先关系、容量、时间窗口）。正是这种亲缘关系使得语料库不仅限于铁路列车调整，而是按其与铁路调整的结构接近程度排序：首先是铁路，然后是更广泛的交通领域，最后是生产领域作为类比的外壳，仅在邻近领域稀疏时才引入，跨越了反应式调整任务以及更广泛的计划与控制操作（第3.1节（https://arxiv.org/html/2607.11980#S3.SS1））。铁路列车调整是演示目标；该方法导出的可比较结构使得这种扩展原则化而非机会主义。  

第三个缺口涉及提取和可复现性。在该领域，发布公式背后的求解器代码仍然不常见，这对可复现研究来说是不良实践：绑定到已发布模型的论文可以被克隆并确定性地重新运行，精确挖掘并在几秒钟内验证，而纯PDF的公式必须从其文本中恢复。从自由文本或LaTeX中读取模型的结构（检查公式而非重新实现）没有完全确定的路径，这使得文献中大部分的建模知识锁定在无法大规模处理的形式中。  

我们通过*基于LP2Graph的线性规划挖掘*来解决这些缺口，并将其作为铁路列车调整的系统的、PRISMA风格文献综述的用例。其核心*LP2Graph*是一个确定性程序，它将定义的LP和MILP公式类别（即那些可用其规范语法表达的公式，第3.2节（https://arxiv.org/html/2607.11980#S3.SS2））表示为从单一规范模型导出的类型化的变量-方程图。因此，本文*并非*对基于LLM的优化建模的贡献：没有语言模型参与表示、挖掘或验证。最近的工作从自然语言描述中合成新模型，而我们做相反的事情：我们将*已发表*的文献挖掘为结构化、可比较、经过验证的语料库；与自动化模型合成的关系留待展望部分讨论（第3.7节（https://arxiv.org/html/2607.11980#S3.SS7））。  

围绕该表示，我们构建了一个挖掘流水线：获取按优先级排序的已发表公式语料库，提取每个公式并同源化到该表示中，导出词汇和结构特征向量，在没有先验名称的情况下自底向上对公式进行聚类，并利用现有分类词汇表自上而下标注产生的组。然后将诱导出的聚类与现有专家评审论文中的分类进行合理性检查，量化和解释机器诱导结构与专家分类之间的差异，这些专家分类作为解释锚点而非真实基准。主要产出是一个*数据集*：已发表的模型被转换为一种通用形式，进行标注和分组，实现了之前不存在的跨公式的*结构可比性*。我们有意使*结构*可比，而非结果：不同的目标和数据使得对公式排名毫无意义，因此我们规范化基础而非结果。  

本文有四项贡献：（i）*LP2Graph*，LP/MILP公式的确定性类型化变量-方程图表示，包含视图、结构度量以及图与具体模型源之间的双向编解码器：LaTeX↔\\leftrightarrow图（当前主要通道）以及代码↔\\leftrightarrow图（从求解器代码导入公式并导出可执行模型）。（ii）一个端到端的*挖掘流水线*（语料库构建、提取/同源化、特征构建、多层聚类和两阶段标注），作用于已发表的文献。（iii）挖掘得到的*数据集*，这是主要贡献，它建立了原本不兼容的公式之间的结构可比性。（iv）一个关于变量角色、约束族和模型类型的诱导*分类体系*，以专家分类为锚点并进行对比。每个聚类重新求解一个代表公式仅用于验证LaTeX→\\tograph→\\totranslate→\\tosolve的往返过程，而非对论文排名。  

本文其余部分组织如下：第2节（https://arxiv.org/html/2607.11980#S2）回顾相关文献并精确陈述缺口。第3节（https://arxiv.org/html/2607.11980#S3）详细介绍挖掘方法和LP2Graph表示。第4节（https://arxiv.org/html/2607.11980#S4）和第5节（https://arxiv.org/html/2607.11980#S5）描述语料库并呈现结果数据集和分类体系。第6节（https://arxiv.org/html/2607.11980#S6）总结。  

## 2 相关工作  

### 2.1 铁路列车调整及更广泛的路径-调度家族  

铁路时刻表恢复有着深厚的MILP文献：在容量、间隔和衔接约束下，重新规划路线、重新排序和重新调整时间，通过精确方法或专用启发式算法求解（cacchiani2014;ReschReview2023;besinovic2020;railrev2022）。从结构上看，这些公式是更广泛的路径和调度模型（如车辆路径规划、作业车间调度和服务网络设计（toth2014vrp;pinedo2016scheduling;crainic2000snd））的近亲，它们与时刻表恢复共享变量模式（分配、排序、流）和约束族（优先关系、容量、时间窗口）。本文将铁路列车调整作为演示领域，同时认识到其针对的建模结构在该家族中反复出现；这种邻近性后来允许策略性地扩展语料库（第3节（https://arxiv.org/html/2607.11980#S3））。  

### 2.2 综述、分类体系和系统综述方法论  

组织该文献的标准方式是叙述性综述，它根据领域词汇对模型进行分类并主观地总结它们（ReschReview2023;railrev2022）。现有的优化模型分类体系确实捕捉了重复出现的变量、约束和模型类型，但它们由专家编写，不可复现，且依赖于命名而非公式的结构。评审者现在越来越期望综述类的论文遵循有记录的系统综述协议PRISMA（page2021prisma），该协议规定了如何搜索、筛选和报告语料库。我们将本文定位为这种系统综述的*用例*：符合PRISMA的语料库协议为机械诱导分类体系的方法提供输入，而现有的专家分类作为锚点，用于对诱导出的聚类进行合理性检查，而非作为真实基准。  

### 2.3 从论文和代码中提取形式化模型  

越来越多的工作从自然语言描述中提取形式化优化模型并将其转换为求解器代码，其中许多现在由LLM驱动（Optimus2024;ORLM2025;OptGen2022;SurveyORLM2024;ahmaditeshnizi2024;wasserkrug2024;Formalization2025;li2023optiguide），同时伴随有专用的自然语言优化建模基准，如NL4Opt（ramamonjison2023nl4opt）、NLP4LP（ahmaditeshnizi2024）和MAMO（huang2024mamo）。在此方向上，对生成模型的验证日益被视为首要关注：TriVAL（fang2026trival）在每个建模阶段（语义规范、数学公式、代码）插入显式的“构建-验证-修订”步骤，这一验证需求与本工作中挖掘的结构化底层数据直接互补。这些努力绝大多数面向*合成*，即从自然语言提示生成一个新模型，并根据精心策划的问题描述对求解准确性进行评估。本文既非合成系统也非为其设计的基准：它从*已发表*的文献中挖掘出结构化、可比较的语料库，其流水线中不使用语言模型，因此无法与这些系统在同一标准下进行比较。  

现有模型最可靠的来源是其发布的代码：绑定到公共仓库的论文可以被确定性地挖掘并快速验证，而纯PDF的公式必须从文本中恢复。从其LaTeX或散文中读取模型的结构（检查公式而非重新实现）是本文核心的数据提取问题，对于非结构化源来说没有完全确定的解决方案。  

### 2.4 优化模型的图表示  

MILP具有自然的二分图结构，变量与它们出现的方程相连，这种表示已被确立为组合问题的结构分析和机器学习的基础（gasse2019exact;bengio2021mlco）。图结构化视图还支持确定性结构度量（例如规模、约束与变量之比以及图直径），这些度量独立于措辞概括了一个公式（cf.diameterMetro;diameterStreet）。此类图的先前用途是针对学习求解或分支；在此，相同的二分结构被重新用作挖掘和聚类已发表模型的规范、可比较的*表示*，使得结构相似的公式无论作者选择何种词汇都能聚集在一起。  

### 2.5 跨领域结构迁移与外壳优先级语料库  

将异构的形式化模型置于共同基础上并非交通领域独有：结构比较和实例合成的工作在整个更广泛的优化文献中反复出现（smithmiles2012instance;gleixner2021miplib）。这使得结构上扩展的语料库变得可行。当铁路列