Feb, 2024

机器学习增强的混合整数线性规划的支配分枝

PDF
TL;DR混合整数线性规划 (MILP) 是数学优化领域的重要组成部分，其提供了一个强大的建模语言，适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展，探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。
mixed integer linear programmingalgorithmic developmentmachine learning algorithmsbranch-and-bound algorithmmathematical optimization
发现论文，激发创造
  • 整数规划切割平面的机器学习：一项调查

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

    Feb, 2023

  • 通过机器学习解决混合整数规划问题的调查

    本文调查了利用机器学习解决混合整数规划（MIP）问题的趋势，介绍了 MIP 及其传统算法，提倡学习和 MIP 的不同集成，并引入了与学习相关的方法。最后，我们展望了基于学习的 MIP 求解器的前景。

    Mar, 2022

  • 基于启发式增强分支定界算法的 MILP 求解器的设计与实现

    在 MIP 2022 竞赛的限时 10 分钟内，我们的混合整数规划求解器，利用分支定界算法和多线程的原始启发式方法，表现出优异的表现，特别是在使用 Diving heuristic 的情况下，成功地解决了 10 个数据集实例，这使得我们的竞赛作品获得了 “优秀学生投稿” 荣誉提名。

    Jun, 2022

  • 混合整数规划作为一层

    该研究介绍了一种新的决策集中学习方法，可以优化预测模型，支持将问题编码为混合整数线性规划，并使用割平面算法求解。实验结果表明，该方法在多个实际领域中的性能优于现有方法。

    Jul, 2019

  • 学习剪枝的改进强化学习算法

    本文提出了基于深度强化学习的分支定界算法，该算法利用离线模仿学习与自主生成数据相结合的优化方法，并且引入了一种优先存储机制来控制二者之间的混合比例，以此提高算法的性能表现。文章在三个公共研究基准上对所提出的算法进行了评估，并与三种经典的启发式方法以及一种先进的模仿学习算法进行了比较。研究结果表明，所提出的算法在性能上表现最佳，并具有不断提高分支定界算法性能的潜力。

    Jan, 2022

  • 利用神经网络解决混合整数规划问题

    本文介绍了一种将机器学习与混合整数规划相结合的方法，通过构建两个神经网络组件 Neural Diving 和 Neural Branching 来生成高质量的联合变量分配和绑定目标值差异，在实验中，该方法比传统方法得到了更好的结果。

    Dec, 2020

  • CAMBranch：使用增强型 MILP 进行区分学习的分支

    通过引入机器学习框架加强了解决混合整数线性规划（MILP）的分支策略，特别是通过模仿学习强分支方法，提出了一种新的框架 CAMBranch，借助变量转移生成增强 MILPs（AMILPs），并利用对比学习提高模型的能力从而改善分支决策质量。

    Feb, 2024

  • 分枝的抽象模型及其在混合整数规划中的应用

    本文提出了一种基于理论模型的枝界算法，其用于选择分支变量的方法是对 MIP 问题进行简化后，对选择不同变量可以得到对偶理论的提升（LP gains）的解析式进行计算，并提出了该方法在实验中的有效性。

    Nov, 2015

  • 离线排名策略学习在高效混合整数规划中的分支排序

    本文提出了一种离线强化学习方法，将分支定界问题的分支决策作为全局决策问题来解决，并通过排名奖励方案将分支方法的长期优势与短期视野进行区分，建立一个离线 MIP 数据集。作者称该方法比现有的基于启发式方法和现有的深度学习方法在优化算法性能方面更有效。

    Jul, 2022

  • 利用回溯轨迹的强化学习在分支定界优化中的应用

    本文提出一种名为 retro branching 的强化学习方法，用于解决混合整数线性规划问题中的 branch-and-bound 算法中的变量选择问题，与之前的方法相比，本方法不需要专家指导或预训练，且在四种组合问题上表现优异。

    May, 2022