@TechReport{Werner-TR-2005-25, IS = { zkontrolovano 30 Dec 2005 }, UPDATE = { 2005-10-03 }, author = {Werner, Tom{\'a}{\v s}}, title = {A Linear Programming Approach to Max-sum Problem: {A} review}, institution = {Center for Machine Perception, K13133 FEE Czech Technical University}, address = {Prague, Czech Republic}, year = {2005}, month = {December}, type = {Research Report}, number = {{CTU--CMP--2005--25}}, issn = {1213-2365}, pages = {40}, figures = {23}, authorship = {100}, psurl = {[Werner-TR-2005-25.pdf]}, project = { COSPAL IST-004176}, annote = {The max-sum (labeling) problem of the second order is defined as maximizing a sum of bivariate functions of discrete variables. It is a general optimization problem with numerous applications, e.g., computing a MAP configuration of a Markov random field on an arbitrary graph. Recently, it has received much attention in context of inference in graphical models, resulting in approaches based on linear programming and belief propagation. It is unknown that a similar approach, based on linear programming relaxation, was developed already in 1970's by Schlesinger \etal. This report surveys this unnoticed work in a unified framework, including published and several unpublished results. Compared to the known works, this old theory is simpler, easier to grasp, and brings several new insights and results. The Lagrangian dual of an integer linear programming formulation is solved first, which can be interpreted as minimizing the quantity called energy by equivalent transformations of the problem. The solution set of the original problem is obtained from the dual optimum by solving a consistent labeling problem. If this consistent labeling problem has no solution, the max-sum problem cannot be solved by the approach, in other words, the LP relaxation is not tight. We analyse the LP pair in detail and give an iterative and a combinatorial algorithm which sometimes solves the dual. We present examples of experiments with syntactic analysis of images.}, keywords = {pattern recognition, max-sum, max-prod, sum-prod, min-sum, consistent labeling, Markov random field, Gibbs distribution, constraint satisfaction, arc consistency, belief propagation, tree agreement}, }