Inference in Higher Order Undirected Graphical Models and Binary Polynomial Optimization

References

• Ali AM, Farag AA, Gimel’Farb GL (2008) Optimizing binary MRFs with higher order cliques. Eur. Conf. Comput. Vision (Springer, New York), 98–111.Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• Beeri C, Fagin R, Maier D, Yannakakis M (1983) On the desirability of acyclic database schemes. J. ACM 30(3):479–513.Crossref, Google Scholar
• Boykov Y, Funka-Lea G (2006) Graph cuts and efficient ND image segmentation. Internat. J. Comput. Vision 70(2):109–131.Crossref, Google Scholar
• Boykov Y, Veksler O, Zabih R (2001) Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Machine Intelligence 23(11):1222–1239.Crossref, Google Scholar
• Buchheim C, Crama Y, Rodríguez-Heck E (2018) Berge-acyclic multilinear 0–1 optimization problems. Eur. J. Oper. Res. 273(1):102–107.Crossref, Google Scholar
• Crama Y (1993) Concave extensions for non-linear 0–1 maximization problems. Math. Programming 61(1):53–60.Crossref, Google Scholar
• Crama Y, Rodríguez-Heck E (2017) A class of valid inequalities for multilinear 0–1 optimization problems. Discrete Optim. 25:28–47.Crossref, Google Scholar
• Del Pia A, Di Gregorio S (2021) Chvátal rank in binary polynomial optimization. INFORMS J. Optim. 3(4):315–349.Link, Google Scholar
• Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• Del Pia A, Khajavirad A (2018a) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2):1049–1076.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2018b) On decomposability of multilinear sets. Math. Programming Ser. A 170(2):387–415.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2021) The running intersection relaxation of the multilinear polytope. Math. Oper. Res. 46(3):1008–1037.Link, Google Scholar
• Del Pia A, Khajavirad A (2023) A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Math. Programming Ser. A 207:269–301.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2025) Constrained multilinear sets: Decomposability and polynomial size extended formulations. Working paper, University of Wisconsin Madison, Madison, WI.Google Scholar
• Del Pia A, Walter M (2023) Simple odd β-cycle inequalities for binary polynomial optimization. Math. Programming Ser. B 206:203–238.Crossref, Google Scholar
• Del Pia A, Khajavirad A, Sahinidis N (2020) On the impact of running-intersection inequalities for globally solving polynomial optimization problems. Math. Programming Comput. 12:165–191.Crossref, Google Scholar
• Fagin R (1983) Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30(3):514–550.Crossref, Google Scholar
• Feldman J, Wainwright MJ, Karger DR (2005) Using linear programming to decode binary linear codes. IEEE Trans. Inform. Theory 51(3):954–972.Crossref, Google Scholar
• Feldman J, Malkin T, Servedio RA, Stein C, Wainwright MJ (2006) LP decoding corrects a constant fraction of errors. IEEE Trans. Inform. Theory 53(1):82–89.Crossref, Google Scholar
• Felzenszwalb PF, Huttenlocher DP (2006) Efficient belief propagation for early vision. Internat. J. Comput. Vision 70:41–54.Crossref, Google Scholar
• Fix A, Wang C, Zabih R (2014) A primal-dual algorithm for higher-order multilabel Markov random fields. Proc. IEEE Conf. Comput. Vision Pattern Recognition, 1138–1145.Google Scholar
• Fix A, Gruber A, Boros E, Zabih R (2011) A graph cut algorithm for higher-order Markov random fields. 2011 Internat. Conf. Comput. Vision (IEEE, Piscataway, NJ), 1020–1027.Crossref, Google Scholar
• Gallager R (1962) Low-density parity-check codes. IRE Trans. Inform. Theory 8(1):21–28.Crossref, Google Scholar
• Glover F, Woolsey E (1974) Converting a 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res. 22(1):180–182.Link, Google Scholar
• Goemans M, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Ishikawa H (2009) Higher-order clique reduction in binary graph cut. 2009 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 2993–3000.Crossref, Google Scholar
• Ishikawa H (2010) Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Machine Intelligence 33(6):1234–1249.Crossref, Google Scholar
• Ishikawa H (2014) Higher-order clique reduction without auxiliary variables. Proc. IEEE Conf. Comput. Vision Pattern Recognition, 1362–1369.Google Scholar
• Jeroslow RG (1975) On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 11(2):119–124.Crossref, Google Scholar
• Khajavirad A (2023) On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2):146–152.Crossref, Google Scholar
• Khajavirad A, Wang Y (2025) Inference in higher order undirected graphical models and binary polynomial optimization: Repository. http://dx.doi.org/10.1287/ijoc.2024.0776.cd, https://github.com/INFORMSJoC/2024.0776.Google Scholar
• Kolmogorov V, Rother C (2007) Minimizing nonsubmodular functions with graph cuts—A review. IEEE Trans. Pattern Anal. Machine Intelligence 29(7):1274–1279.Crossref, Google Scholar
• Kolmogorov V, Zabin R (2004) What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Machine Intelligence 26(2):147–159.Crossref, Google Scholar
• Komodakis N, Paragios N (2009) Beyond pairwise energies: Efficient optimization for higher-order MRFs. 2009 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 2985–2992.Crossref, Google Scholar
• McEliece RJ, MacKay DJC, Cheng JF (1998) Turbo decoding as an instance of Pearl’s “belief propagation” algorithm. IEEE J. Selected Areas Comm. 16(2):140–152.Crossref, Google Scholar
• Meltzer T, Yanover C, Weiss Y (2005) Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation. 10th IEEE Internat. Conf. Comput. Vision, vol. 1 (IEEE, Piscataway, NJ), 428–435.Google Scholar
• Nesterov Y (1998) Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Software 9(1–3):141–160.Crossref, Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1–3):139–172.Crossref, Google Scholar
• Richardson TJ, Urbanke RL (2001) The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. Inform. Theory 47(2):599–618.Crossref, Google Scholar
• Rother C, Kohli P, Feng W, Jia J (2009) Minimizing sparse higher order energy functions of discrete variables. 2009 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1382–1389.Crossref, Google Scholar
• Sherali H, Adams W (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• Szeliski R, Zabih R, Scharstein D, Veksler O, Kolmogorov V, Agarwala A, Tappen M, Rother C (2008) A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Trans. Pattern Anal. Machine Intelligence 30(6):1068–1080.Crossref, Google Scholar
• Wainwright M, Jordan M (2008) Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning.Crossref, Google Scholar
• Wainwright MJ, Jaakkola TS, Willsky AS (2005) MAP estimation via agreement on trees: Message-passing and linear programming. IEEE Trans. Inform. Theory 51(11):3697–3717.Crossref, Google Scholar
• Willsky AS (2002) Multiresolution Markov models for signal and image processing. Proc. IEEE 90(8):1396–1458.Crossref, Google Scholar