Mar, 2024

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

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

    利用机器学习的能力，针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案，该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。

    Jun, 2024

  • 利用深度强化学习解决二次分配问题

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

    Oct, 2023

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

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

    Dec, 2011

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

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

    Jun, 2012

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

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

    Mar, 2017

  • 2+p-SAT：典型情况复杂性与相变性质的关系

    这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题，介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中，在计算代价随问题规模呈指数级增长的情况下，首次发现了 “随机一阶相变” 的本质，并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。

    Oct, 1999

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

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

    Mar, 2024

  • SAT 相变

    本文探讨了在随机 k-SAT 模型下，随着变量与子句的比例 r 的增加，满足问题的可满足性呈现相变现象，并在阈值点出现真值分配的突变，从而使得满足真值分配的相似度由之前开始相对差异变为非常相似的过程。

    May, 2000

  • 绝热演化量子计算

    本文提出了一种基于绝热演化的量子算法，用于解决可满足性问题，其中 Hamiltonian 函数随时间变化，插入了初始 Hamiltonian 和最终 Hamiltonian，通过保证时间足够长，来确保系统演化到预期的最终基态，算法时间复杂度在某些可满足性问题的对称情况下为多项式时间。

    Jan, 2000

  • QAP 的 SDP 松弛问题的 ADMM 算法

    本文提出使用 ADMM 算法来解决 SDP 松弛问题，该方法具有低成本迭代、获取低秩解的方式以及简单添加切平面约束的优点，在与目前最佳算法比较中表现出出色的鲁棒性、效率和改进的结果。

    Dec, 2015