# Solution to quadratically constrained binary integer program

I'm trying to solve a problem for $$x$$ which is a vector of length $$n$$ with only binary elements, i.e. each $$x_{i}$$ is either $$0$$ or $$1$$.

There are two constraints on $$x$$, one quadratic and one linear:

$$x^{T}Ax + b^{T}x = 0 \\ Ex = d$$

All of $$A$$, $$b$$, $$E$$, and $$d$$ have integer elements. $$A$$ is relatively sparse and not invertible, not PSD. $$E$$ is also sparse and has only $$1$$'s on some of the diagonal elements. $$d$$'s values are either $$0$$ or $$1$$.

I am looking for any solution satisfying the constraints, not necessarily all solutions. And, at least one solution is guaranteed to exist based on how the constraints are formulated (this is a bit out of scope but there will be a solution).

The catch is, the problem size can be very large, on the order of $$n = 10^{3}$$ to $$n = 10^{5}$$. Any suggestions for solving this problem? I have many tools at my disposal, MATLAB, cplex, numpy, scipy, etc.