Inference in Higher Order Undirected Graphical Models and Binary Polynomial Optimization
将高阶无向图模型的推理问题转化为二元多项式优化，提出多种线性规划松弛并比较其理论强度，通过图像恢复和纠错码解码验证有效性。
We consider the problem of inference in higher order undirected graphical models with binary labels. We formulate this problem as a binary polynomial optimization problem and propose several linear programming relaxations for it. We compare the strength of the proposed linear programming relaxations theoretically. Finally, we demonstrate the effectiveness of these relaxations by performing a computational study for two important applications, namely, image restoration and decoding error-correcting codes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-23-1-0123]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0776 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0776 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .