Feb, 2024

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

PDF
TL;DR通过引入机器学习框架加强了解决混合整数线性规划（MILP）的分支策略，特别是通过模仿学习强分支方法，提出了一种新的框架 CAMBranch，借助变量转移生成增强 MILPs（AMILPs），并利用对比学习提高模型的能力从而改善分支决策质量。
machine learningbranch and boundmixed integer linear programmingimitation learningcontrastive learning
发现论文，激发创造
  • 机器学习增强的混合整数线性规划的支配分枝

    混合整数线性规划 (MILP) 是数学优化领域的重要组成部分，其提供了一个强大的建模语言，适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展，探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。

    Feb, 2024

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

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

    Jan, 2022

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

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

    May, 2022

  • 使用 Tree MDPs 进行分支学习

    本文通过强化学习的方法，提出了树马尔科夫决策过程的概念，从头学习分支规则，并通过计算实验证明了树马尔科夫决策过程对于 MILP 中学习分支问题具有更好的收敛性能。

    May, 2022

  • 利用对比学习学习混合整数规划问题的后门

    利用蒙特卡洛树搜索方法收集训练数据，通过对比学习框架训练图注意力网络模型来预测 Mixed Integer Programs 中的 MIP backdoors，相比 Gurobi 和之前的模型，在四个常见的 MIP 问题领域中展现了性能的提升。

    Jan, 2024

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

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

    Jul, 2022

  • 参数化分支定界搜索树以学习分支策略

    采用参数化状态来帮助泛化 “学习分支” 方法，该方法可以有效地处理各种 MILP 问题，通过模拟学习框架实现新的输入特征和架构以表示分支决策，从而在准确性和 B&B 树的大小等方面具有显著的优势。

    Feb, 2020

  • 通过敌对实例增强促进精确求解器的泛化能力

    通过对混合整数线性规划问题应用机器学习，我们提出了一种新方法 AdaSolver，通过实例增强来改善分支定界求解器的泛化效果，从而显著提高效率。

    Oct, 2023

  • 学习如何分支：加速无线网络资源分配

    使用机器学习中的模仿学习方法，加速分支定界算法并在深度神经网络中使用创新的损失函数来实现更好的动态控制，以同时实现更好的最优性和更少的计算复杂性。

    Mar, 2019

  • 学习分支的混合模型

    本文提出了一种基于 GNN 和 MLP 的混合模型，可在没有高端 GPU 的情况下有效地优化 Mixed Integer Linear Programming 问题求解器的性能。

    Jun, 2020