Dec, 2022

整数线性规划的局部分支松弛启发式算法

PDF
TL;DR本文探讨了在整数线性规划（ILP）的大邻域搜索（LNS）中设计有效和高效的启发式。 创新性地提出了 LB-RELAX 及其变体，利用线性规划松弛代替 Local Branching 来选择邻居。实验证明相对于 LB，LB-RELAX 及其变体计算出的邻域相同，但是速度更快。在多个 ILP 基准测试中取得了最新的任意时间性能。
large neighborhood searchheuristic algorithmcombinatorial optimization problemsinteger linear programslocal branching
发现论文，激发创造
  • 使用对比学习技术在大邻域内搜索整数线性规划问题

    本文介绍了一种新的算法 CL-LNS，通过使用正负样本集合学习一个次优解算法并使用图注意力网络和更丰富的特征进一步提高解决 LP 问题的性能。

    Feb, 2023

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

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

    Jul, 2021

  • 大领域优先搜索策略在组合优化与答案集编程中的应用

    我们提出了大邻域优先搜索（LNPS）用于解决回答集程序设计中的组合优化问题。LNPS 是一种元启发式方法，通过交替破坏和优先搜索当前解来寻找更好的解决方案。我们基于 ASP 实现了 LNPS，并通过 heulingo 求解器的实验证明了 LNPS 可以显著提高 ASP 在优化方面的求解性能。此外，我们通过与（自适应）大邻域搜索的对比来证明我们 LNPS 方法的竞争力。

    May, 2024

  • 整数线性规划的局部搜索

    该论文开发了第一个独立的本地搜索模型，使用紧密移动和提升移动两种算子，解决了复杂的整数线性规划问题，并在 MIPLIB 数据集上实现了比市场上同类解决方案更好的结果。

    Apr, 2023

  • 基于自适应约束分区的大规模整数线性规划优化框架（学生摘要）

    本文提出了一个基于自适应约束分区的优化框架，旨在解决解决大规模整数规划问题时可能会陷入局部最优解的问题。与现有的大邻域搜索算法相比，该框架可以更高效地利用任何现有优化求解器作为子例程来优化决策变量。实验结果表明，该框架在规定的墙钟时间内显示出比 SCIP 和 Gurobi 更好的性能。

    Nov, 2022

  • 利用深度强化学习进行自适应大邻域搜索的运算符选择

    本文提出了一种基于深度强化学习算法的算子选择方法，旨在提高 Adaptive Large Neighborhood Search（ALNS）算法的解题质量，实证结果表明，与基于机器学习的算法相比，所述方法训练次数更少，对小型问题与大型问题都能有效提高问题解决效率。

    Nov, 2022

  • 基于神经构造启发式算法的大邻域搜索

    本文提出了一种基于神经网络学习的建造启发式方法的大邻域搜索 (LNS) 方法，用于解决具有时间窗口的车辆路径问题 (VRPTW)。方法采用图形神经网络来编码问题，并通过强化学习在不需要监督标签的情况下训练构造任务。神经修复运算符与局部搜索例程、启发式销毁运算符和选择过程相结合，应用于小型人口来到达一个复杂的解决方案。关键思想是使用学习模型重新构造部分破坏的解决方案，并通过破坏启发式 (或随机策略本身) 引入随机性，以有效地探索大邻域。

    May, 2022

  • 学习控制组合优化中的局部搜索

    本研究提出了一种名为 NeuroLS 的本地搜索算法控制器，采用深度图神经网络作为策略模型，通过计算机学习方法，能够优于已知常规搜索控制器和最新的机器学习方法，在求解 NP 困难度的组合优化问题中，取得了比较理想的结果。

    Jun, 2022

  • 学习增强的邻域选择在车辆路径问题中的应用

    将机器学习技术应用于大邻域搜索算法（LNS）以提高解决优化问题的效率和结果质量。

    Mar, 2024

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

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

    May, 2020