Abstract

This monograph is about combinatorial optimization. More precisely, about a special class of combinatorial problems known as energy minimization or maximum a posteriori (MAP) inference in graphical models, closely related to weighted and valued constraint satisfaction problems and having tight connections to Markov random fields and quadratic pseudo-boolean optimization. What distinguishes this monograph from a number of other monographs on graphical models is its focus: It considers graphical models, or, more precisely, MAP-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. Combinatorial optimization as a field is largely based on five fundamental topics: (i) integer linear programming and polyhedral optimization; (ii) totally unimodular matrices and the class of min-cost-flow problems; (iii) Lagrange decompositions and relaxations; (iv) dynamic programming and (v) submodularity, matroids and greedy algorithms. Each of these topics found its place in this monograph, although to a variable extent. The covering of each respective topic reflects its importance for the considered MAP-inference problem. Since optimization is the primary topic of this monograph, we mostly stick to the terminology widely used in optimization and where it was possible we tried to avoid the graphical models community-specific technical terms. The latter differ from sub-community to sub-community and, in our view, significantly complicate the information exchange between them. The same holds also for the presentation of material in this monograph. If there is a choice when introducing mathematical constructs or proving statements, we prefer more general mathematical tools applicable in the whole field of operations research rather than to stick to graphical modelspecific constructions. We additionally provide the graphical model-specific constructions if it turns out to be easier than the more general one. This way of presentation has two advantages. A reader familiar with a more general technique can grasp the new material faster. On the other hand, the monograph may serve as an introduction to combinatorial optimization for readers unfamiliar with this subject. To make the monograph even more suitable for both categories of readers we explicitly separate the mathematical optimization background chapters from those specific to graphical models. We believe, therefore, that 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. Moreover, we believe that even experts in graphical models can find new views on the known facts as well as a novel presentation of less known results in the monograph. These are for instance (i) a simple and general proof of equivalence of different acyclic Lagrange decompositions of a graphical model; (ii) a general scheme for analyzing convergence of dual block-coordinate descent methods; (iii) a short and self-contained analysis of a linear programming relaxation for binary graphical models, its persistency properties and its relation to quadratic pseudo-boolean optimization. The present monograph is based on lectures given to undergraduate students of Technical University of Dresden and Heidelberg University. The selection of material is done in a way that it may serve as a basis for a semester course.

Discrete Graphical Models — An Optimization Perspective

Discrete Graphical Models — An Optimization Perspective 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.

This 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.