用代码生成法高效构建高质量混合整数规划实例
Code Retrieval for MILP Instance Generation
- 将生成问题转化为代码生成，提升灵活性与可解释性
- 新相似度度量能准确比较不同规模实例的相似性
- 适合需要大量训练数据的学习型求解器研究者
混合整数线性规划（MILP）广泛应用于调度、物流和规划等领域。提升学习型求解器性能需大量高质量数据，但现有生成方法需为每类问题单独训练模型，且生成效率低。本文将MILP实例生成任务重构为MILP代码生成任务，通过代码实现高效、灵活、可解释的实例生成。针对代码生成实例规模差异大的问题，提出MILP-EmbedSim相似度度量，可精准衡量同类别中不同规模实例的相似性。基于此，构建MILP-Retrieval管道，从代码库中检索生成代码以产出与目标实例高度相似的实例。实验表明，该方法在代码生成和实例生成任务上均优于基线，为学习型求解器提供了新范式。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) is widely used in fields such as scheduling, logistics, and planning. Enhancing the performance of MILP solvers, particularly learning-based solvers, requires substantial amounts of high-quality data. However, existing methods for MILP instance generation typically necessitate training a separate model for each problem class and are computationally intensive when generating new instances. To address these limitations, we reformulate the MILP Instance Generation task as MILP Code Generation task, enabling efficient, flexible, and interpretable instance generation through code. Since MILP instances generated from code can vary significantly in scale, we introduce MILP-EmbedSim, a new similarity metric that accurately measures the similarity between instances of varying sizes within the same problem class. Leveraging this metric, we propose MILP-Retrieval, a pipeline that retrieves generation code from library to produce MILP instances highly similar to target instance. MILP-Retrieval outperforms baselines in both MILP Code Generation and Instance Generation tasks, provides a novel perspective on MILP instance generation and opens new possibilities for learning-based solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。