论文

并非所有问题都最适合建模为MILP:以DSL为中心的灵活精准优化建模框架OptiDSL

Not All Problems Are Best Modeled as MILP: A DSL-Centric Framework for Flexible and Accurate Optimization Modeling

模型推理推理策略与问题分解

摘要

求解组合优化问题(COP)不仅需要高效的算法,还需要精心设计的建模表述。尽管近期工作已利用大语言模型(LLM)实现优化建模自动化,但现有框架主要依赖僵化的混合整数线性规划(MILP)范式。本文论证并非所有问题都最适合建模为MILP,因为将复杂领域强行塞入线性约束会带来难以承受的建模复杂度,并严重限制求解器的灵活性。为此,我们提出OptiDSL,一个将焦点从僵化MILP表述转向领域专用语言(DSL)表示的框架。OptiDSL利用LLM将自然语言映射到标准化、领域公认的结构上,从而将问题表述与执行解耦。这一范式使其能够与多样化的专用求解器库无缝集成,涵盖从传统启发式到现代基于学习的方法。在涵盖44类COP的综合基准上的实验结果显示,OptiDSL显著超越基于MILP的流水线:建模准确率提升51.66%,建模时间减少91.71%。值得注意的是,它在现有基准上也优于基于MILP的流水线,建模准确率高出23.09%。代码见 https://anonymous.4open.science/r/OptiDSL。

并非所有问题都最适合建模为MILP:以DSL为中心的灵活精准优化建模框架OptiDSL:论文配图
图 1:CVRP 案例建模范例的说明性示例。 DSL 公式比 MILP 公式更适合表示 CVRP 实例。