LP Mining with LP2Graph: A Use Case for Railway Rescheduling

LP Mining 与 LP2Graph：铁路重调度的一个用例

Abstract: Like many optimization-driven domains, railway rescheduling relies on Mixed-Integer Linear Programming (MILP), yet the field’s modeling knowledge is scattered across hundreds of papers in incompatible notations, and narrative surveys organize it subjectively: they classify models by vocabulary rather than by structure, and reproduce neither.

摘要： 与许多以优化为驱动的领域一样，铁路重调度依赖于混合整数线性规划（MILP）。然而，该领域的建模知识分散在数百篇论文中，且符号系统互不兼容；现有的叙述性综述往往带有主观性：它们根据词汇而非结构对模型进行分类，且无法复现这些模型。

We present LP Mining with LP2Graph, a method that mines the structure of published LP and MILP formulations into a reproducible dataset and an induced taxonomy. Its core, LP2Graph, represents each formulation admitted by its canonical grammar as a typed variable—equation graph derived from a single canonical model; once a source is extracted into that model, everything downstream is deterministic.

我们提出了 LP Mining 与 LP2Graph，这是一种将已发表的 LP 和 MILP 公式结构挖掘为可复现数据集及归纳分类法的方法。其核心 LP2Graph 将符合其规范语法的每个公式表示为从单一规范模型派生的类型化变量-方程图；一旦源文件被提取到该模型中，后续的所有处理过程都是确定性的。

Each source is parsed into this model, homologized, and clustered bottom-up (over variables, then constraints and the objective, then whole-model structure) and, separately, by application domain and solution approach; the resulting groups are labeled by a rule-seeded, self-updating classifier.

每个源文件都被解析到该模型中，进行同源化处理，并采用自下而上的方式进行聚类（先处理变量，再处理约束和目标函数，最后处理整体模型结构），同时按应用领域和求解方法分别进行聚类；最终形成的组别由一个基于规则引导的自更新分类器进行标注。

We validate the representation rather than assume it: per-cluster representatives are regenerated as independent LaTeX and re-solved across CBC, HiGHS and Gurobi against the optimum reported in the source paper. The outcome is an objective, repeatable taxonomy of variables, constraints and model types: the principled foundation on which our raiLPminer line of automated railway-rescheduling model development builds.

我们对这种表示方法进行了验证，而非直接假设其有效性：我们将每个聚类的代表性模型重新生成为独立的 LaTeX 代码，并使用 CBC、HiGHS 和 Gurobi 求解器进行重新求解，并与原论文中报告的最优解进行对比。最终成果是一个客观、可重复的变量、约束和模型类型分类法：这正是我们 raiLPminer 自动化铁路重调度模型开发系列所构建的原则性基础。