One readily checks that \(\mathbf {X}\rightarrow \mathbf {A}\)  if and only if (REF ) has a solution in \(\lbrace 0,1\rbrace \) . Unless P=NP, this system is not solvable in polynomial time over \(\lbrace 0,1\rbrace \) . Relaxing it by allowing that the variables can be assigned rational nonnegative values (resp. integer values) results in the so-called basic linear programming (BLP) relaxation (resp. affine integer programming (AIP) relaxation).
Note that both these relaxations (as well as all relaxations we shall use in this work) result in algorithms that are complete but not necessarily sound, in the sense that they always output \(\textsc {Yes}\)  if \(\mathbf {X}\rightarrow \mathbf {A}\) , but may fail to output \(\textsc {No}\)  if \(\mathbf {X}\lnot \rightarrow \mathbf {A}\) .
The \(\operatorname{BA}\)  relaxation described in [1]} combines the two relaxations mentioned above as follows: It outputs \(\textsc {Yes}\)  if and only if there exist a solution to \(\operatorname{BLP}\)  and a solution to \(\operatorname{AIP}\)  such that the following so-called refinement condition holds: Whenever a variable is zero in the first solution, it is zero in the second solution. It follows that \(\operatorname{BA}\)  is at least as strong as both \(\operatorname{BLP}\)  and \(\operatorname{AIP}\) ; in fact, as shown in [1]}, it is strictly stronger, in the sense that there exist templates
that are solved by \(\operatorname{BA}\)  but not by \(\operatorname{BLP}\)  or \(\operatorname{AIP}\) .
