5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you mean a mixed-integer quadratic program (MIQP)? $\endgroup$ – Geoff Oxberry May 17 '12 at 5:34
  • $\begingroup$ It would be useful to hear what you already tried? $\endgroup$ – Wolfgang Bangerth May 17 '12 at 8:32
  • $\begingroup$ Did you mean $A$ to be $20\times n$ instead of $n \times 20$? $\endgroup$ – Wolfgang Bangerth May 17 '12 at 14:55
  • 1
    $\begingroup$ 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? $\endgroup$ – Michael Grant Mar 26 '13 at 20:42
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.