提出首个联合建模整数与连续变量的生成框架,显著提升混合整数规划求解质量。
FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming
- 构建整数与连续变量联合分布的生成模型,突破传统方法仅关注整数变量的局限。
- 在8个标准测试集上平均降低41.34%原始目标差距,逼近最优解。
- 可适配任意神经网络和下游求解器,适合实际复杂决策场景。
混合整数线性规划(MILP)是复杂决策问题的核心工具,但其NP-hard特性带来巨大计算挑战,促使基于机器学习的启发式方法加速求解器运行。尽管近期生成模型在学习高效启发式方面展现出潜力,但其主要局限在于仅建模整数变量分布,未能捕捉整数与连续变量间的复杂耦合关系,造成信息瓶颈,最终导致次优解。为此,我们提出面向混合整数线性规划的联合连续-整数流框架(FMIP),这是首个对MILP解中整数与连续变量联合分布进行建模的生成框架。基于该联合建模范式,设计了整体引导机制,在推理过程中主动引导生成轨迹,持续优化解的可行性和最优性。在8个标准MILP基准上的大量实验表明,FMIP相比现有基线平均降低41.34%的原始目标差距。此外,我们证明了FMIP可兼容任意主干网络和多种下游求解器,适用于广泛的现实世界MILP应用场景。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) is a foundational tool for complex decision-making problems. However, the NP-hard nature of MILP presents a significant computational challenge, motivating the development of machine learning-based heuristic solutions to accelerate downstream solvers. While recent generative models have shown promise in learning powerful heuristics, they suffer from a critical limitation. That is, they model the distribution of only the integer variables and fail to capture the intricate coupling between integer and continuous variables, creating an information bottleneck and ultimately leading to suboptimal solutions. To this end, we propose Joint Continuous-Integer Flow for Mixed-Integer Linear Programming (FMIP), which is the first generative framework that models the joint distribution of both integer and continuous variables for MILP solutions. Built upon the joint modeling paradigm, a holistic guidance mechanism is designed to steer the generative trajectory, actively refining solutions toward optimality and feasibility during the inference process. Extensive experiments on eight standard MILP benchmarks demonstrate the superior performance of FMIP against existing baselines, reducing the primal gap by 41.34% on average. Moreover, we show that FMIP is fully compatible with arbitrary backbone networks and various downstream solvers, making it well-suited for a broad range of real-world MILP applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。