ICMLJun, 2019

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

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

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

    Jun, 2024

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

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

    Feb, 2023

  • 通过预测选择切平面：基于模仿学习的切割技能培养

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

    Jun, 2022

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

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

    Feb, 2022

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

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

    May, 2021

  • 通过强化学习引导的整数规划实现鲁棒调度

    本文提出了一种结合深度强化学习和整数规划的技术 ——NICE，用于解决飞行员航班表调度中的鲁棒性问题，实验结果表明，相较于基线方案和鲁棒整数规划，NICE 能够更有效地减少调度中不良因素所带来的影响。

    Sep, 2021

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

    通过使用混合整数线性规划中的割平面，我们设计了一个基于增强学习的混合图表示模型 (HYGRO)，来解决割平面生成停止问题，并与现代求解器集成，实验证明 HYGRO 相对于竞争基准有显著的解决效率提升，达到了高达 31% 的改进。

    Jan, 2024

  • 基于整数规划的贝叶斯网络学习的进展

    本研究通过整数规划方案和贪心算法等方法，从离散数据中学习 Bayesian 网络，在实验结果中取得了和之前相比有着巨大的改进。

    Sep, 2013

  • 使用割平面算法学习贝叶斯网络

    提出了一个将贝叶斯网络结构学习问题转化为优化问题，使用整数规划方法进行求解的方法，具体来说，在整数规划算法中添加了割平面的约束，用子整数规划搜索这些割平面来提高该方法性能，以求得最大化对数边际似然（BDe 分数）的贝叶斯网络结构，该方法能够高效地进行准确的贝叶斯网络结构学习。

    Feb, 2012

  • 割平面选择中的理论挑战

    对比不同种类的切割平面以及它们间的相对强度，讨论在分支定界树中选取一个投资组合的切割平面的问题，提出一些新的方法。在研究中，试图为切割平面选择设计出一种更为系统的方法。同时我们为与切割平面选择有关的一些问题提供了初步的理论基础。

    May, 2018