arXiv:2410.08288cs.LG2024-10ICLR被引 34

用大模型生成多样化混合整数规划问题,训练可泛化的求解基础模型。

Towards Foundation Models for Mixed Integer Linear Programming

  • 基于大模型演化生成海量多样化的混合整数规划实例
  • 在未见过的问题上显著提升求解性能,包括经典基准测试集
  • 适合对优化算法、AI for OR 感兴趣的研究者

混合整数线性规划(MILP)是建模复杂决策问题的关键工具,但面临计算困难和需专家建模的挑战。现有深度学习方法局限于特定问题类别,难以泛化。为此,本文提出一种基础模型训练范式:在多样化MILP问题上训练单一深度学习模型以实现跨类泛化。由于现有MILP数据集多样性与规模不足,我们引入MILP-Evolve——一种基于大语言模型的演化框架,可无限生成多样化的MILP类及其实例。我们在三个核心学习任务上验证方法:(1) 整数间隙预测,(2) 学习分支策略,(3) 将MILP实例与自然语言描述对齐。实证结果表明,基于MILP-Evolve生成数据训练的模型,在未见问题(包括MIPLIB基准)上表现显著提升。本工作展示了向通用MILP基础模型迈进的潜力。代码与数据公开于 https://github.com/microsoft/OptiGuide。

原文摘要 · Abstract (English)

Mixed Integer Linear Programming (MILP) is essential for modeling complex decision-making problems but faces challenges in computational tractability and requires expert formulation. Current deep learning approaches for MILP focus on specific problem classes and do not generalize to unseen classes. To address this shortcoming, we take a foundation model training approach, where we train a single deep learning model on a diverse set of MILP problems to generalize across problem classes. As existing datasets for MILP lack diversity and volume, we introduce MILP-Evolve, a novel LLM-based evolutionary framework that is capable of generating a large set of diverse MILP classes with an unlimited amount of instances. We study our methodology on three key learning tasks that capture diverse aspects of MILP: (1) integrality gap prediction, (2) learning to branch, and (3) a new task of aligning MILP instances with natural language descriptions. Our empirical results show that models trained on the data generated by MILP-Evolve achieve significant improvements on unseen problems, including MIPLIB benchmarks. Our work highlights the potential of moving towards a foundation model approach for MILP that can generalize to a broad range of MILP applications. Our code and data are publicly available at https://github.com/microsoft/OptiGuide.

优化基础模型MILPAI for OR

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。