Efficiently solving SDP relaxation of an integer quadratic program

Question

I have an integer quadratic program of the form,

\begin{align} \underset{x}{\max}&\;\;\|Ax-b\|_2^2\\ \text{subject to}&\;\;x\in{\bf Z}\geq0 \end{align}

I'm currently using the (admittedly crude) convex approximation which relaxes the integer constraint, and then recovers a feasible point by rounding each component of $x^*$ to the nearest integer.

I would like to instead use the more sophisticated semidefinite relaxation presented in equation (11) of (Park & Boyd, 2017),

\begin{align} \underset{X,\hspace{1mm}x}{\max}&\;\;\text{tr}(PX)+2q^Tx\\ \text{subject to}&\;\;\text{diag}\hspace{0.5mm}X\geq x\\[3pt] &\;\;[X\;x;\;x^T\;1] \succcurlyeq 0\\[3pt] &\;\;x\geq0 \end{align}

where $P=A^TA$ and $q=-A^Tb$.

I've tried several different free solvers, and the SCS solver seems to work the best, however if we suppose that $P$ is an $n\times n$ matrix, then on a single machine I can only scale the problem up to about $n=100$. Ideally I would like to scale the problem up to at least $n=1000$, and beyond if possible.

Is this possible? For what it's worth, $P$ is approximately a band matrix, and for $n\geq1000$, the number of nonzero entries of $P$ is less than 1%, and it continues to get sparser as $n$ gets larger.

I have access to servers with many CPU cores and GPUs if necessary.

Answer 1

As a follow up to my comment, where I say that the model has to be interpreted from the primal model side, here it implements the model for $n=1000$ and then tells the modelling layer YALMIP that it should extract a model interpreting this a representation of the primal. The SDP solver Mosek solves this in 1 minute on an old laptop

n = 1000;
P = sprandn(n,n,1/n);
P = P*P'+eye(n);
q = randn(n,1);
Z = sdpvar(n+1);
X = Z(1:n,1:n);
x = Z(1:n,end);
Model =[Z >= 0, 
        Z(end,end)==1,
        diag(X)>=x, 
        x>=0];
Objective = P(:)'*X(:)+2*q'*x;
optimize(Model,Objective,sdpsettings('dualize',1))

I did not wait for SCS to terminate, but for $n=100$ SCS solved it in 2 seconds.