M. Pawan Kumar 
HOME

Notation
The above example illustrates our notation. The random variables are shown as unfilled circles. The labels are shown as trellises over the random variables. Each branch of the trellis represents one label. The unary potential of a random variable V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise potential for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Similarly, the optimization variable corresponding to a random variable V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise optimization variable for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Linear Programming Relaxation
In constrast to the integer program, the variables x_{a}(i) are relaxed to take any value between (and including) 1 and 1. Furthermore, the nonconvex quadratic equality constraint is relaxed to the marginalization constraint (last constraint in the above problem). The resulting optimization problem is convex, with a linear objective function and linear constraints.
