Supplement: Novel Upper Bounds for the Constrained Most Probable Explanation Task

It is well known that any MPE task can be encoded as an integer linear programming (ILP) problem (cf. A popular or widely used formulation is to associate a Boolean variable with each entry in each function of the log-linear model. When the Boolean variable is assigned the value 1, the entry is selected, otherwise it is not. For instance, a type of consistency constraint encodes the restriction that only entry from each function must be selected. A second type of consistency constraint ensures that if two functions share a variable then only entries which assign the shared variable to the same value are selected.