本论文调查了机器学习在选择混合整数线性规划中剪切平面的技术上的应用,通过使用数据来确定有希望的剪辑以加速 MILP 实例的解决方案,并分析文献中的实证结果以量化已经取得的进展,并建议未来的研究方向。
Feb, 2023
本文提出了一种名为 NeuralCut 的新型神经网络进行割平面选择,该方法基于对专家的模仿学习而设计,能够在 MILPs 的切割选择中实现性能优异的表现,且在验证神经网络时表现出很大潜力。
Jun, 2022
本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking,用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数,该方法被证明比传统的启发式算法更为有效,可适用于具有不同特性的多种问题,且在实验和在线 A / B 测试中效果显著。
May, 2021
通过强化学习,提出了一种新的层次序列模型(HEM),可以同时解决切割选择中的三个主要问题:(P1)哪些切割应该优先选择,(P2)应选择多少切割和(P3)优选选择的切割顺序对于求解混合整数线性规划问题的效率有显著影响。
我们提出了一种新的层次序列 / 集合模型(HEM),可以同时解决切割选择的三个挑战:学习要选择哪些切割、学习选择多少切割、以及学习选择顺序。实验证明,HEM 显著提高了求解 MILP 问题的效率。
Apr, 2024
混合整数线性规划 (MILP) 是数学优化领域的重要组成部分,其提供了一个强大的建模语言,适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展,探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。
Feb, 2024
本文提出一组新的切割评分措施、切割过滤技术和停止准则,并将其扩展到现有的算法状态,并获得了 4%的性能提升,用于 SCIP 覆盖 MIPLIB 2017 基准集。
Jul, 2023
本文研究了一种基于参数调整的混合整数线性规划问题的解法。通过设计一种基于图卷积神经网络和强化学习的自适应割集选择算法,我们证明此算法在实验中取得了优秀性能。
Feb, 2022
在基于切割平面方法的整数线性规划中,我们尝试使用可学习的参数化准则 - 切割删除策略,以在不影响整数最优解的情况下,对先前迭代中引入的切割进行删除,结果表明这种策略在基础组合优化问题中能够显著提升,即使使用简单模型实现,也能超越基于人类或机器学习的切割添加策略。
Jun, 2024
通过使用混合整数线性规划中的割平面,我们设计了一个基于增强学习的混合图表示模型 (HYGRO),来解决割平面生成停止问题,并与现代求解器集成,实验证明 HYGRO 相对于竞争基准有显著的解决效率提升,达到了高达 31% 的改进。
Jan, 2024