Nov, 2024

学习混合整数线性规划的最优目标值

HTML
PDF
TL;DR本研究针对现代混合整数线性规划（MILP）求解器的一个空白，通过引入图神经网络（GNN）架构的预测方法，预测最优目标值或当前解是否最优。实验结果表明，该方法在预测任务中表现出高准确率，并超越了现有方法，为将机器学习驱动的预测集成到MILP求解器中提供了新的可能性。
发现论文，激发创造
  • 基于解预测加速混合整数规划原始解求解

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

    Jun, 2019

  • 学习分支的混合模型

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

    Jun, 2020

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

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

    Dec, 2020

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

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

    May, 2022

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

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

    Feb, 2023

  • 探索图神经网络求解线性优化问题的能力

    机器学习中的消息传递图神经网络（MPNNs）可以模拟线性优化问题和组合优化问题，提高解决难解优化问题的效率。

    Oct, 2023

  • 基于训练过的神经网络的优化：放松行走

    此研究提出了一种基于全局和局部线性松弛的可扩展启发式方法，用于对训练后的神经网络模型进行建模和求解，具有与最先进的整数线性规划（MILP）求解器和之前的启发式方法相竞争，并且在输入、深度和神经元数量增加时能够产生更好的解。

    Jan, 2024

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

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

    Feb, 2024

  • 重新考虑图神经网络在分支策略中的容量

    研究表明图神经网络能够有效地表示和学习基于混合整数线性规划的解决策略，其中包括强分支评分。另外，该研究还证明第二阶基因网络结构能够以高准确率和高概率近似强分支评分。

    Feb, 2024

  • RL-MILP求解器：一种基于强化学习的方法解决混合整数线性规划

    本研究解决了现有机器学习方法在混合整数线性规划（MILP）问题中可行性不足的挑战。提出一种新颖的基于强化学习的求解器，设计专门针对MILP的奖励函数，从而使智能体能够学习决策变量与约束之间的关系。实验结果表明，该方法能有效解决MILP问题，并在无需传统求解器的情况下找到近似最优解。

    Nov, 2024