Dec, 2023

学习旅行推销员问题的拉格朗日乘子

PDF
TL;DR应用图神经网络预测准确的 Lagrangian 乘子，作为生成 Held-Karp 松弛界限的初始值，并通过这种方法改进分支界定算法的过滤过程，从而加速优化证明的过程。
lagrangian relaxationoptimization problemgraph neural networksheld-karp relaxationtravelling salesman problem
发现论文，激发创造
  • 预测混合整数线性规划的准确拉格朗日乘数

    采用图卷积网络的深度学习方法来优化通过拉格朗日松弛解决复杂约束的混合整数线性规划问题，通过训练编码器和解码器来最大化连续松弛和最佳拉格朗日界限之间的间隙，并提供一个高质量的下降启动点。

    Oct, 2023

  • 使用 Lagrangian Relaxation 学习解决软约束车辆路径问题

    该研究提出了一种基于强化学习的方法，结合拉格朗日松弛技术和约束策略优化，用于解决软限制的车辆路径规划问题，并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证，表明其对解决已有方法难以解决的问题有很好的竞争力。

    Jul, 2022

  • 图形模型中的 MAP 估计的 Lagrangian 松弛

    采用拉格朗日松弛技术，将不可解的估计问题重新定义为更可处理的图上问题，通过相应约束的松弛最大化优化问题，并应用于离散和高斯图模型的 MAP 估计及优化问题中。

    Sep, 2007

  • 面向旅行商问题的图神经网络引导局部搜索

    提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。

    Oct, 2021

  • 使用置换不变汇聚网络学习多个旅行商问题

    本文设计一种神经网络方法，利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合，通过搜索方法和特定的损失函数来输出最优解，实验结果表明该方法优于现有领域最先进的元启发式算法。

    Mar, 2018

  • 提前预计以避免迟到：解决困难约束旅行推销员问题

    使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。

    Mar, 2024

  • 学会解决旅行商问题要重新思考泛化

    本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

    Jun, 2020

  • NeuroLKH: 结合深度学习模型与 Lin-Kernighan-Helsgaun 启发式算法求解旅行商问题

    NeuroLKH 采用深度学习和 LKH 启发式算法相结合，通过训练 Sparse Graph Network 模型来解决旅行商问题等路由问题，得出实验结果表明能够优于传统启发式算法并泛化到更大范围问题。

    Oct, 2021

  • 在无限维希尔伯特空间中学习一些玩具约束优化问题的解决方案

    我们在无限维希尔伯特空间中提出了两种受限优化算法的深度学习实现，分别是罚函数法和增广拉格朗日法。通过在变分法或物理学中起源的一些玩具问题上测试这些算法，我们证明这两种方法能够为测试问题提供相当准确的近似，并且在不同误差方面具有可比性。利用拉格朗日乘子更新规则在计算上比在罚函数法中求解子问题更便宜的常见情况，当约束函数的输出本身是一个函数时，我们实现了显著的加速。

    Jan, 2024

  • 旅行商问题的 Transformer 网络

    本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

    Mar, 2021