ICLRDec, 2019

黑盒组合求解器的区分

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

    本文提出了一种可端到端学习的深度图匹配体系结构，其中包含未修改的组合求解器，并使用优化的组合求解器和架构设计的改进推进了关键点对应的深度图匹配基准的最新进展。

    Mar, 2020

  • 组合结构的贝叶斯优化

    该篇论文提出了一种基于半定规划的自适应、可扩展模型的算法，用于优化机器学习、离散优化和贵重求值黑盒函数所需的组合结构，该算法在实验中表现优于组合和贝叶斯优化等其他方法。

    Jun, 2018

  • 基于图神经网络的组合优化和推理

    本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。

    Feb, 2021

  • 带时序注意力图神经网络的精确组合优化

    通过替换启发式成分，结合机器学习算法的时间特征与注意力机制，优化了组合优化求解器在变量选择方面的性能。

    Nov, 2023

  • 使用图卷积神经网络进行精确组合优化

    本文提出了一种基于图卷积神经网络的分支定界变量选择新模型，通过模仿学习和强分支专家规则训练，成功解决了组合优化问题。实验结果表明，该方法不仅在分支机制上优于现有的机器学习方法，而且在大问题上也优于现有的专家设计分支规则。

    Jun, 2019

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

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

    Dec, 2021

  • 神经组合优化：领域的新玩家

    本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

    May, 2022

  • 使用无数据神经网络的可微组合优化方法

    本研究提出了一种基于神经网络的无数据训练方法，用于解决组合优化问题，特别是最大独立集和最大团的问题，并提出了通用的图缩小过程来处理大规模图形。这种方法在无需数据的情况下，可与有监督学习、强化学习和基于机器学习的现有方法相媲美或更优，具有广泛的适用性。

    Mar, 2022

  • 面向基于学习的方法的组合问题的通用表示

    通过构建图形表示并引入图神经网络结构，本文旨在实现对组合问题的全面通用表示，并在四个组合问题的实验结果中展示了与专用架构相当的性能和广泛适用性。

    Mar, 2024

  • 物理启发图神经网络的组合优化

    本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

    Jul, 2021