ICMLJun, 2024

学习解决方案感知的变压器以高效解决二次分配问题

PDF
TL;DR利用机器学习的能力，针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案，该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。
optimization problemsmachine learningquadratic assignment problemlearn-to-improve categorysolutions aware transformer
发现论文，激发创造
  • 利用深度强化学习解决二次分配问题

    通过深度强化学习的方法解决 Quadratic Assignment Problem（QAP）的 Koopmans-Beckman 公式，使用双指针网络（double pointer network）在选择下一个设施放置位置和上一个位置放置设施之间交替，并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中，我们的解决方案与高质量的局部搜索基线相比，平均准确率达到了 97.5%，在 1.2% 的实例中表现优于基线。

    Oct, 2023

  • 通过两阶段图指针网络和强化学习解决 QAP 问题

    本文提出了一种基于深度强化学习模型的两阶段图指示器网络（GPN）来解决二次分配问题（QAP），实验结果表明它可以为 TSPLib 和 QAPLIB 的基准问题提供半最优解。

    Mar, 2024

  • 极具挑战的平方分配问题的研究：QAP-SAT 实例

    本研究探讨了 Quadratic Assignment Problem 的相变现象，通过引入新的基于子模块性的 QAP-SAT 设计来捕捉问题的复杂度，并使用分支界限和禁忌搜索求解器对其进行实验研究，在此基础上提出了相变参数，发现禁忌搜索的相变满意度和解决努力与关键参数高度相关，从而可以预测出困难的实例。

    Mar, 2024

  • 大规模（脑）图匹配的快速近似二次规划

    本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。

    Dec, 2011

  • 半定规划方法求解稀疏图的二次分配问题

    本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。

    Mar, 2017

  • 神经图匹配网络：学习 Lawler 的二次分配问题，并扩展到超图和多图匹配

    本篇论文提出了一种利用权值矩阵进行学习的网络来解决 Quadratic Assignment Problem (QAP) 及图匹配的问题，该模型利用嵌入网络对顶点进行分类，并通过 Sinkhorn 归一化和交叉熵损失进行端到端的学习。实验结果表明，该方法在合成数据和现实图像上均取得了很好的效果。

    Nov, 2019

  • 利用谐波分析将领域知识纳入匹配问题

    探究加速解决二次分配问题（QAP）的新方法，利用特殊的优化函数方法在傅里叶空间中优化对称群 Sn，以及在多个优化任务中学习参数。实验表明，新方法在实际领域中可以优于现有方法。

    Jun, 2012

  • 基于 Transformer 革新混合整数规划问题的求解方法

    利用变压器模型解决容量限制批量问题，并通过深度学习框架和线性规划解决被认为是 NP - 难的问题，提供了解决时效、优化率和可行性等方面超越当前最先进解法的算法。

    Feb, 2024

  • 迈向超大规模 Transformer 的下一级后训练量化

    本文提出了一种新颖的 PTQ 算法 aespa，通过逐层量化实现高效性，同时考虑跨层依赖以保留注意力分数，通过对多种语言模型的广泛实验和复杂度分析，证明了 aespa 在量化 Transformer 模型时具备准确性和高效性。

    Feb, 2024

  • 基于图神经网络的二次分配学习算法修订笔记

    研究逆向问题的计算困难性及使用基于图神经网络的数据驱动模型来解决这类问题的效果。

    Jun, 2017