Nov, 2024

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

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

    使用有限时间约束生成算法，将基于神经网络的观察到学习和规划过程中的潜在奖励函数上界计算建立为二层规划问题，并通过提前计算奖励潜力来强化混合整数线性规划模型的线性松弛度，以在长期视野下有效计算奖励潜力。

    Apr, 2019

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

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

    Jun, 2019

  • 分支定界算法中的变量选择强化学习

    文章提出了一种名为FMSTS的新型增强学习方法，采用一种全新的分支策略来优化整数线性规划问题，具有一致性和泛化能力，并在计算实验中验证了其有效性。

    May, 2020

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

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

    Dec, 2020

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

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

    May, 2022

  • 通过层次序列模型学习混合整数线性规划的切割选择

    通过强化学习，提出了一种新的层次序列模型（HEM），可以同时解决切割选择中的三个主要问题：（P1）哪些切割应该优先选择，（P2）应选择多少切割和（P3）优选选择的切割顺序对于求解混合整数线性规划问题的效率有显著影响。

    Feb, 2023

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

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

    Jan, 2024

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

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

    Feb, 2024

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

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

    Nov, 2024

  • 用于混合整数线性规划的多任务表征学习

    本研究解决了现有机器学习指导的混合整数线性规划（MILP）方法在数据收集和训练过程中的独立性问题，从而限制了其可扩展性和适应性。我们提出了一种新的多任务学习框架，能够横向指导多种求解器的MILP求解，并在多个任务中提供MILP嵌入。实验证明，该模型在多样性和任务泛化能力上显著优于传统专用模型。

    Dec, 2024