通过约束压缩提升求解效率,让大规模整数规划更快更准。
Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
- 从约束入手压缩模型,而非传统变量压缩
- 提升解质量超50%,求解时间减少17.47%
- 适合需要高效求解大规模整数规划的研究者
模型简化旨在学习原混合整数线性规划(MILP)的更简模型,可显著加速大规模MILP问题求解。现有方法多基于变量压缩,预测部分变量取值。本文从对偶视角提出一种新型基于约束的模型简化方法:将部分不等式约束转化为等式以降低复杂度。该方法面临两大挑战:一是如何识别关键约束,使其压缩后仍保持可行性;二是如何高效预测这些关键约束。为此,我们首先将最优解处的紧约束标记为潜在关键约束,并设计启发式规则筛选关键紧约束。为进一步学习关键紧约束,提出一种融合实例级与抽象级信息的多模态表示技术。实验表明,相比当前最佳方法,本方法解质量提升超50%,计算时间减少17.47%。
原文摘要 · Abstract (English)
Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for the MILP. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we first label these tight-constraints at the optimal solution as potential critical constraints and design a heuristic rule to select a subset of critical tight-constraints. To learn the critical tight-constraints, we propose a multi-modal representation technique that leverages information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art methods, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。