研究了一种计算 Markov 随机场上最大后验概率的最优配置的方法，通过将原始分布分解为树形分布的凸组合来得到上限，提出了两种尝试获得紧密上限的方法，并建立了模式搜索问题 LP 松弛和最大乘积（最小和）消息传递算法之间的联系。
Aug, 2005
本文提出了一种新的多项式时间算法来解决最小化无向图模型的能量问题，利用凸松弛方法得到部分最优非松弛积分解，并采用迭代修建策略优化算法，相较之前的方法表现更好。
Oct, 2014
针对基于图模型的最大后验概率推断问题，本研究提出了一系列不同于 Sherali-Adams 层次结构的松弛方法，将问题分解为一个简单的 LP-tight 部分和一个困难的组合求解器部分，实验证明对小部分问题可以显著降低计算时间。
Apr, 2020
使用双重消息传递算法对线性规划进行松弛，通过迭代选择具有保证改进的集群，解决集群选择问题，成功地在蛋白质侧链放置、蛋白质设计和立体化问题中找到了最有可能的 MAP 配置。
Jun, 2012
本文提出了一种用于找到 NP 难问题下离散图像模型 MAP 推理的部分最优解的算法，并通过使用一个线性规划松弛的精确求解器，标记出一些标签作为其最大可能的标签。
Aug, 2015
本文提出了一种凸型置信传播算法，可以在满足一定条件下，使用单循环图或重加权树的置信传播算法，在准确性上更加理论化地实现最大概率赋值 (MAP)。并且在实验中证明了该方法对一些无法使用传统算法的大型图具有较高的准确率。
本论文提出了一种基于 Junction chains 和线性规划的算法来处理图模型中的近似 MAP-MRF 推断问题，并且在计算机视觉领域取得了一定的性能提升。
May, 2012
本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。
Sep, 2017
应用图神经网络预测准确的 Lagrangian 乘子，作为生成 Held-Karp 松弛界限的初始值，并通过这种方法改进分支界定算法的过滤过程，从而加速优化证明的过程。
Dec, 2023
本文介绍了 LP-SparseMAP，这是 SparseMAP 的一个扩展，它通过本地多面体松弛来解决 SparseMAP 的一个限制。LP-SparseMAP 使用因子图的领域特定语言来定义和回溯任意隐藏结构，支持粗分解，硬逻辑约束和高阶相关性。在三个结构化预测任务中的实验显示了与 SparseMAP 和结构化 SVM 相比的优势。
Jan, 2020