# What is a suitable algorithm for solving a large mixed-integer quadratic program?

I am interested in the solutions of a very large quadratic programming (QP) problem

\begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n \end{align}

where $n=10^7$, $Q$ is a dense, positive-semidefinite matrix whose entries are natural numbers that can be computed rapidly, and $A \in \mathbb{N}^{n \times 20}$.

What is a suitable algorithm for such a large problem, and what is a good implementation?

-
Do you mean a mixed-integer quadratic program (MIQP)? – Geoff Oxberry May 17 '12 at 5:34
It would be useful to hear what you already tried? – Wolfgang Bangerth May 17 '12 at 8:32
Did you mean $A$ to be $20\times n$ instead of $n \times 20$? – Wolfgang Bangerth May 17 '12 at 14:55
It seems to me that the key here is that it is simply impractical to form Q or its square root. This is going to rule out most traditional MINLP solvers, frankly, including I think both of the suggestions below. Is this a fair assessment? – Michael C. Grant Mar 26 at 20:42

This is a mixed-integer QP, not a positive semidefinite QP. (One can make any QP with binary constraints psd by adding a large multiple of $x^Tx-e^Tx$.)