0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

You can linearize the quadratic constraint and use an integer linear programming solver. See https://or.stackexchange.com/questions/37/how-to-linearize-the-product-of-two-binary-variables

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .