Apr, 2023

在线学习用于调度 MIP 启发式算法

PDF
TL;DR本文提出了一种在线学习方法，用于优化 Mixed Integer Programming (MIP) 中的启发式算法，以适应于不同的实例，并将大邻域搜索和 Diving 两类复杂启发式方法同时控制，实现 MIPLIB 2017 基准测试的节点数减少和速度提升。
mixed integer programmingonline learning approachheuristicslarge neighborhood searchdiving
发现论文，激发创造
  • 通过机器学习解决混合整数规划问题的调查

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

    Mar, 2022

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

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

    Dec, 2020

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

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

    Jun, 2022

  • 混合整数规划的大邻域搜索算法学习

    该论文提出了一种基于学习的大邻域搜索 (LNS) 方法来解决混合整数规划 (MIP)，该方法使用神经潜水模型来表示变量分配的可能性分布，并使用非自用 MIP 求解器生成初始分配，并使用诱导学习来训练神经网络选择在每个步骤中寻找下一个分配的邻域。

    Jul, 2021

  • 基于数据驱动的框架用于指导组合优化求解器 (MIP-GNN)

    提出了一种称作 MIP-GNN 的混合整数规划改进方法，利用图神经网络模型预测混合整数线性规划的变量偏差，并将其集成到一个先进的 MIP 求解器中，针对二进制 MILP 的节点选择和启发式方面展示了与默认设置相比的显著改进。

    May, 2022

  • 混合整数规划作为一层

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

    Jul, 2019

  • 在线硬约束多任务学习

    本文探讨了多任务在线学习，当决策者需要同时处理 M 个任务时。M 个任务是相关的，我们给出了此类问题的一个一般可行解，并提供了计算上有效的方法来选择行动，本质上是将其化简为在线最短路径问题。我们还讨论了问题的 “跟踪” 和 “劫掠” 版本，并扩展了模型，包括非可加全局损失和无穷集合的任务。

    Feb, 2009

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

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

    Feb, 2024

  • 基于解预测加速混合整数规划原始解求解

    本文提出了基于三分图的方法表示 MIP 问题，该问题可以通过图卷积网络结合机器学习方法来预测二进制变量的解，以生成一种局部分支类型切割，从而提高求解 MIP 问题的性能。

    Jun, 2019

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

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

    Jan, 2024