The goal is to solve an integer linear program q, which is defined as We partition the constraints into two sets, say The assumption is that in the absence the constraints C 2 , the inference problem becomes computationally easier to solve.
we can assume the existence of a subroutine that can efficiently compute the solution of the relaxed problem q : We define Lagrange multipliers Λ ≥ 0, with one λ i for each constraint in C 2 .