AAAIMay, 2022

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

PDF
TL;DR提出了一种称作 MIP-GNN 的混合整数规划改进方法，利用图神经网络模型预测混合整数线性规划的变量偏差，并将其集成到一个先进的 MIP 求解器中，针对二进制 MILP 的节点选择和启发式方面展示了与默认设置相比的显著改进。
mixed-integer programmingmip-gnncombinatorial optimizationgraph neural networkbinary milps
发现论文，激发创造
  • 基于解预测加速混合整数规划原始解求解

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

    Jun, 2019

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

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

    Dec, 2020

  • 有限数据可用情况下深度实例生成框架在 MILP 求解器中的应用

    提出了 G2MILP 方法，它作为第一个深度生成 MILP 实例的框架，通过将 MILP 实例表示为二分图，并应用掩码变分自编码器来生成新的实例，既不依赖于专家设计的公式，同时又能保持真实世界数据集的结构和计算难度，从而为增强 MILP 求解器提供有限数据的下游任务提供帮助。

    Oct, 2023

  • 混合整数规划作为一层

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

    Jul, 2019

  • 深度学习增强的整数混合优化：学习降低模型维度

    通过深度学习来解决混合整数规划（MIP）模型中固有的计算复杂性，并比较前馈神经网络（ANN）和卷积神经网络（CNN）在逼近 MIP 问题中的活动维度的效果，利用多标签分类来纳入多个活动维度，通过贝叶斯优化进行超参数调优以提升模型性能，并应用于基于流量的设施位置分配混合整数线性规划（MILP）问题，描述个性化医疗供应链中的长期投资规划和中期战略规划。

    Jan, 2024

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

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

    Mar, 2022

  • 训练神经网络的强混合整数规划公式

    本文提出了一个强大的混合整数编程（MIP）框架，可以用于处理高维分段线性函数，从而建立与训练好的神经网络相匹配的数学模型，并通过这些数学模型来解决图像分类的鲁棒性验证和机器学习模型的决策问题。我们的方法比文献中其他方法更加有效，并且在图像分类网络的验证任务中取得了优异的结果。

    Nov, 2018

  • 学习分支的混合模型

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

    Jun, 2020

  • 基于物理信息图学习解决大规模机组组合问题

    提出了一种基于物理信息的分层图卷积网络（PI-GCN）用于神经潜伏，通过学习电力系统各组成部分的底层特征来寻找高质量的变量分配；采用基于 MIP 模型的图卷积网络（MB-GCN）用于神经分支，在 B＆B 树的每个节点上选择最优变量进行分支；将神经潜伏和神经分支集成到现代 MIP 求解器中构建一个创新的神经 MIP 求解器，用于处理大规模的 UC 问题。数值研究表明，相较于基线 MB-GCN，PI-GCN 在神经潜伏方面具有更好的性能和可扩展性；此外，将神经 MIP 求解器与我们提出的神经潜伏模型和基线神经分支模型相结合，可以获得最低的运营成本，并在所有测试日中优于现代 MIP 求解器。

    Nov, 2023

  • 网络封锁的神经方法

    通过将网络干扰问题表示为混合整数线性规划（MILP）实例，然后应用具有充分表征能力的多部分 GNN 来学习这些公式，我们的方法在两个不同任务中表现出优于理论基准模型和传统精确解算器的性能优势。

    May, 2024