Jun, 2024

组合优化的深层符号优化：通过发现潜在启发式加速节点选择

PDF
TL;DR提出了一种结合深度符号优化学习框架的新型深度符号优化节点选择模块（Dso4NS）的方法，该方法通过数据驱动的方法在高维离散符号空间中搜索数学表达式，并将性能最佳的数学表达式纳入求解器，实现快速推理和高解释性。实验结果表明，Dso4NS 在学习高质量表达式方面表现优于现有方法，在 CPU 机器上达到与最新的 GPU 方法相当的性能。
combinatorial optimizationdeep learningnode selection modulesymbolic optimizationsolver
发现论文，激发创造
  • 神经组合优化算法的泛化

    本文采用元学习技术来在多种任务中训练一个模型，以优化适应新任务的能力，从而提高两个最先进的模型的泛化能力，实验表明该方法在两个 CO 问题上都有显著改善。

    Jun, 2022

  • 模拟引导的神经组合优化梁搜索

    通过引入模拟指导波束搜索（SGBS）和有效主动搜索（EAS）的组合，提高了神经组合优化的搜索效率。

    Jul, 2022

  • 黑盒组合求解器的区分

    本文介绍一种将组合优化算法和深度学习相结合的方法，利用神经网络中的组合构建块来解决原始输入数据中的组合问题，如机器人中的路线规划和多目标跟踪中的全局一致性保证。作者将 Gurobi MIP 求解器、Blossom V 算法和 Dijkstra 算法引入到结构中，实现了高效的反向传递，为旅行商问题，最小成本完美匹配问题和最短路径问题提供了特征提取方案。

    Dec, 2019

  • 面向决策的图神经网络在组合优化中的应用

    我们的研究工作的重点是通过决策导向的图学习，在组合优化问题中采用神经网络框架，提出了一个更高效和精确的框架。此外，我们引入了一个决策导向的框架，利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明，我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。

    Jun, 2024

  • 图上组合优化的统一预训练和适应框架

    通过最大可满足性问题（Max-SAT）提出了一种统一的图上组合优化问题（CO）的预训练和适应框架，能够提取可转移和可推广的特征，以解决图上不同 CO 问题。

    Dec, 2023

  • 图上组合优化求解器稳健性评估的通用框架

    本文提出第一个对组合优化求解器的实用鲁棒性度量方法，并针对 14 个算法和 CO 问题进行了广泛的实验，在给定时间限制下，发现目前的最先进算法（如 Gurobi）在指定的难例上的性能下降了超过 20％，使人们对组合优化求解器的鲁棒性产生担忧。

    Dec, 2021

  • 运用图指针网络在组合优化中的学习分支

    本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略，结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。

    Jul, 2023

  • COMBHelper：减少图组合问题搜索空间的神经方法

    设计了一种名为 COMBHelper 的神经方法，借助图神经网络（GNN）识别有前景的节点，压缩搜索空间并提高传统组合优化算法的效率；包括知识蒸馏模块和问题特定增强模块以进一步提升效果，实验证明传统算法利用 COMBHelper 至少快于原始版本 2 倍。

    Dec, 2023

  • 自我改进学习的可扩展神经组合优化

    提出了一种自我改进学习（Self-Improved Learning, SIL）方法，用于提高神经组合优化（neural combinatorial optimization, NCO）的可扩展性，包括有效的模型训练和解决大规模问题实例的线性复杂度注意机制。在旅行推销员问题（Travelling Salesman Problem, TSP）和容量车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）上进行的全面实验证明了该方法的出色可扩展性。

    Mar, 2024

  • 组合优化中的对称探索是自由的！

    提出了一种 “免费” 技术，通过利用对称性来增强任何基于深度强化学习（DRL）的求解器的性能，而不需要额外的目标函数评估。这种方法通过奖励保持变换来扩充 DRL 的训练，并且在 NP 硬路由优化、计划优化和革新物质优化等诸多领域得到了广泛的实证评估，展现了优异的样本效率。

    Jun, 2023