Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 5 down vote favorite

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?

share|improve this question
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
1  
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

2 Answers

up vote 1 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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