# Discrete graphical models -- an optimization perspective

arXiv: https://arxiv.org/abs/2001.09017 · HTML: https://mlsanity.com/paper/2001.09017/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2020.

## Built on by (most cited first, 8 of 8)

- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Comparative Study of Graph Matching Algorithms in Computer Vision](https://mlsanity.com/paper/2207.00291/) (2022)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Discrete-Continuous Smoothing and Mapping](https://mlsanity.com/paper/2204.11936/) (2022)
- [Relative-Interior Solution for the (Incomplete) Linear Assignment Problem with Applications to the Quadratic Assignment Problem](https://mlsanity.com/paper/2301.11201/) (2023)
- [Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective](https://mlsanity.com/paper/2201.02018/) (2022)
- [Efficient and Flexible Sublabel-Accurate Energy Minimization](https://mlsanity.com/paper/2206.09596/) (2022)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)

## Abstract (arXiv)

This monograph is about discrete energy minimization for discrete graphical models. It considers graphical models, or, more precisely, maximum a posteriori inference for graphical models, purely as a combinatorial optimization problem. Modeling, applications, probabilistic interpretations and many other aspects are either ignored here or find their place in examples and remarks only. It covers the integer linear programming formulation of the problem as well as its linear programming, Lagrange and Lagrange decomposition-based relaxations. In particular, it provides a detailed analysis of the polynomially solvable acyclic and submodular problems, along with the corresponding exact optimization methods. Major approximate methods, such as message passing and graph cut techniques are also described and analyzed comprehensively. The monograph can be useful for undergraduate and graduate students studying optimization or graphical models, as well as for experts in optimization who want to have a look into graphical models. To make the monograph suitable for both categories of readers we explicitly separate the mathematical optimization background chapters from those specific to graphical models.