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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you mean a mixed-integer quadratic program (MIQP)? $\endgroup$
    – Geoff Oxberry
    May 17, 2012 at 5:34
  • $\begingroup$ It would be useful to hear what you already tried? $\endgroup$
    – Wolfgang Bangerth
    May 17, 2012 at 8:32
  • $\begingroup$ Did you mean $A$ to be $20\times n$ instead of $n \times 20$? $\endgroup$
    – Wolfgang Bangerth
    May 17, 2012 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, 2013 at 20:42

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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