用对比学习优化约束顺序，让大规模整数规划求解快30%。
CLCR: Contrastive Learning-based Constraint Reordering for Efficient MILP Solving
- 基于结构聚类和指针网络的对比学习排序方法
- 平均提速30%，单纯迭代减少25%，精度不变
- 适合需要高效求解大规模优化问题的研究者
约束顺序对混合整数线性规划（MILP）求解器的效率至关重要，尤其在大规模问题中，不当的顺序会引发更多单纯形法迭代和次优搜索路径。本文提出CLCR（基于对比学习的约束重排序）框架，通过分析约束的结构模式进行聚类，并利用指针网络结合对比学习优化其顺序，在保持问题等价性的同时提升求解效率。在多个基准测试上，CLCR平均将求解时间缩短30%，单纯形法迭代次数减少25%，且不牺牲解的准确性。该工作展示了数据驱动的约束排序在优化模型中的潜力，为数学规划与机器学习的融合提供了新范式。
原文摘要 · Abstract (English)
Constraint ordering plays a critical role in the efficiency of Mixed-Integer Linear Programming (MILP) solvers, particularly for large-scale problems where poorly ordered constraints trigger increased LP iterations and suboptimal search trajectories. This paper introduces CLCR (Contrastive Learning-based Constraint Reordering), a novel framework that systematically optimizes constraint ordering to accelerate MILP solving. CLCR first clusters constraints based on their structural patterns and then employs contrastive learning with a pointer network to optimize their sequence, preserving problem equivalence while improving solver efficiency. Experiments on benchmarks show CLCR reduces solving time by 30% and LP iterations by 25% on average, without sacrificing solution accuracy. This work demonstrates the potential of data-driven constraint ordering to enhance optimization models, offering a new paradigm for bridging mathematical programming with machine learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。