Jan, 2024

学习停止剪切生成以提高混合整数线性规划的效率

PDF
TL;DR通过使用混合整数线性规划中的割平面，我们设计了一个基于增强学习的混合图表示模型 (HYGRO)，来解决割平面生成停止问题，并与现代求解器集成，实验证明 HYGRO 相对于竞争基准有显著的解决效率提升，达到了高达 31% 的改进。
cutting planesmixed-integer linear programscuts generation stoppingreinforcement learninghygro
发现论文，激发创造
  • 通过预测选择切平面：基于模仿学习的切割技能培养

    本文提出了一种名为 NeuralCut 的新型神经网络进行割平面选择，该方法基于对专家的模仿学习而设计，能够在 MILPs 的切割选择中实现性能优异的表现，且在验证神经网络时表现出很大潜力。

    Jun, 2022

  • 通过层次序列模型学习混合整数线性规划的切割选择

    通过强化学习，提出了一种新的层次序列模型（HEM），可以同时解决切割选择中的三个主要问题：（P1）哪些切割应该优先选择，（P2）应选择多少切割和（P3）优选选择的切割顺序对于求解混合整数线性规划问题的效率有显著影响。

    Feb, 2023

  • 通过分层序列 / 集合模型学习剪裁以实现高效混合整数规划

    我们提出了一种新的层次序列 / 集合模型（HEM），可以同时解决切割选择的三个挑战：学习要选择哪些切割、学习选择多少切割、以及学习选择顺序。实验证明，HEM 显著提高了求解 MILP 问题的效率。

    Apr, 2024

  • 学习去除整数线性规划中的剪枝

    在基于切割平面方法的整数线性规划中，我们尝试使用可学习的参数化准则 - 切割删除策略，以在不影响整数最优解的情况下，对先前迭代中引入的切割进行删除，结果表明这种策略在基础组合优化问题中能够显著提升，即使使用简单模型实现，也能超越基于人类或机器学习的切割添加策略。

    Jun, 2024

  • 整数规划切割平面的机器学习：一项调查

    本论文调查了机器学习在选择混合整数线性规划中剪切平面的技术上的应用，通过使用数据来确定有希望的剪辑以加速 MILP 实例的解决方案，并分析文献中的实证结果以量化已经取得的进展，并建议未来的研究方向。

    Feb, 2023

  • 学习选择剪枝以提高混合整数规划效率

    本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking，用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数，该方法被证明比传统的启发式算法更为有效，可适用于具有不同特性的多种问题，且在实验和在线 A / B 测试中效果显著。

    May, 2021

  • 混合整数线性规划中的自适应削减选择

    本文研究了一种基于参数调整的混合整数线性规划问题的解法。通过设计一种基于图卷积神经网络和强化学习的自适应割集选择算法，我们证明此算法在实验中取得了优秀性能。

    Feb, 2022

  • 强化学习用于整数规划：学习剪切

    应用深度强化学习技术提升整数规划问题求解算法中割平面方法 (Cutting Plane Method) 的性能表现。通过对算法的智能自适应选择，和其在分支定界算法 (Branch-and-Cut algorithm) 中的应用，表现出在各种不同规模的样例和不同的整数规划问题中，训练出来的深度 RL 代理能显著的超过人类设计的启发式方法。

    Jun, 2019

  • 学习整数规划的切割函数生成

    使用分支切割算法解决大规模整数规划问题时，关键步骤之一是选择有效的约束条件（切割平面）来减少最优解搜索空间。该论文扩展了数据驱动选择最佳切割平面生成函数的概念，并探索了使用神经网络进行依赖于实例的切割平面生成函数选择的样本复杂性。

    May, 2024

  • 学习在分支定界算法中配置分隔器

    本研究通过机器学习，在混合整数线性规划问题中选择切平面，以加速求解过程并提高求解时间。

    Nov, 2023