If I were going to feed this problem to an ILP solver, then this is the formulation that I would try first. (Emphasis on first, because this activity usually involves a fair amount of trial and error.)
min sum_{species i measured true} x_i
- sum_{species i measured false} x_i
subject to
for each species i inhibiting reaction j:
x_i + y_j <= 1
for each species i activating reaction j:
x_i - y_j >= 0
for each non-input species i:
x_i - sum_{reaction j producing species i} y_j <= 0
(binary)
for each species i:
x_i in {0, 1}
for each reaction j:
y_j in {0, 1}
I split your constraint (1) because I don't think that it does what you want with binary constraints on the variables. I don't have a lot of intuition about what the relaxation quality will be like (if it's bad, my guess is that summing the y_j
s will be to blame). Another possibility would be to use a constraint solver; I have much less experience with those.
Researchers in combinatorial optimization tend to favor experimental evaluations over theoretical asymptotic time bounds, because the latter are hard to come by and usually unduly pessimistic. In the worst case, branch and bound won't obtain any useful bounds, and the cost will be brute force times the cost of evaluating each node (probably polynomial).