一种面向混合整数规划的上下文感知割平面选择算法
本文研究了一种基于参数调整的混合整数线性规划问题的解法。通过设计一种基于图卷积神经网络和强化学习的自适应割集选择算法,我们证明此算法在实验中取得了优秀性能。
Feb, 2022
本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking,用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数,该方法被证明比传统的启发式算法更为有效,可适用于具有不同特性的多种问题,且在实验和在线 A / B 测试中效果显著。
May, 2021
对比不同种类的切割平面以及它们间的相对强度,讨论在分支定界树中选取一个投资组合的切割平面的问题,提出一些新的方法。在研究中,试图为切割平面选择设计出一种更为系统的方法。同时我们为与切割平面选择有关的一些问题提供了初步的理论基础。
May, 2018
本论文调查了机器学习在选择混合整数线性规划中剪切平面的技术上的应用,通过使用数据来确定有希望的剪辑以加速 MILP 实例的解决方案,并分析文献中的实证结果以量化已经取得的进展,并建议未来的研究方向。
Feb, 2023
本文提出了一种名为 NeuralCut 的新型神经网络进行割平面选择,该方法基于对专家的模仿学习而设计,能够在 MILPs 的切割选择中实现性能优异的表现,且在验证神经网络时表现出很大潜力。
Jun, 2022
在基于切割平面方法的整数线性规划中,我们尝试使用可学习的参数化准则 - 切割删除策略,以在不影响整数最优解的情况下,对先前迭代中引入的切割进行删除,结果表明这种策略在基础组合优化问题中能够显著提升,即使使用简单模型实现,也能超越基于人类或机器学习的切割添加策略。
Jun, 2024
使用分支切割算法解决大规模整数规划问题时,关键步骤之一是选择有效的约束条件(切割平面)来减少最优解搜索空间。该论文扩展了数据驱动选择最佳切割平面生成函数的概念,并探索了使用神经网络进行依赖于实例的切割平面生成函数选择的样本复杂性。
May, 2024
通过使用混合整数线性规划中的割平面,我们设计了一个基于增强学习的混合图表示模型 (HYGRO),来解决割平面生成停止问题,并与现代求解器集成,实验证明 HYGRO 相对于竞争基准有显著的解决效率提升,达到了高达 31% 的改进。
Jan, 2024
本文提出了基于整数规划的方法来构建用于算法选择问题的决策树,并使用 COIN-OR Branch & Cut solver 实现的线性规划算法进行了实验。实验结果表明,该方法具有很好的泛化性能且未过度拟合。
Jul, 2019