May, 2021

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

PDF
TL;DR本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking，用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数，该方法被证明比传统的启发式算法更为有效，可适用于具有不同特性的多种问题，且在实验和在线 A / B 测试中效果显著。
cutting plane methodsmixed-integer programmingdata-driven approachcut selectioninstance-specific cut features
发现论文，激发创造
  • 混合整数线性规划中的自适应削减选择

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

    Feb, 2022

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

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

    Jun, 2022

  • 一种面向混合整数规划的上下文感知割平面选择算法

    本文提出一组新的切割评分措施、切割过滤技术和停止准则，并将其扩展到现有的算法状态，并获得了 4％的性能提升，用于 SCIP 覆盖 MIPLIB 2017 基准集。

    Jul, 2023

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

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

    Feb, 2023

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

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

    Apr, 2024

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

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

    Feb, 2023

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

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

    Jun, 2024

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

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

    Jan, 2024

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

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

    May, 2018

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

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

    Jun, 2019