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

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. The CMPE task adds a global constraint to the ILP formulation of MPE given in Eq. The LP-bound on the ILP given in Eq. This gives us the following linear programming relaxation.