# 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 Grant Mar 26 '13 at 20:42

## 2 Answers

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$.)

Couenne ( https://projects.coin-or.org/Couenne ) might be an appropriate solver for this.

You could also try GloMIQO. It's available in GAMS (as of version 23.8) and designed specifically to solve mixed-integer quadratic programs with linear or quadratic constraints, and has some promising results. You could also try contacting the authors of the software directly, if purchasing a GAMS license is not a viable option.