Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
    
scicomp.stackexchange.com is a better place to ask such questions. –  user17762 May 17 '12 at 3:46
    
Is the meaning of the second constraint that x lies in the unit cube, or that x is a corner of the cube? If the fesable set is only the corners, that seems inconsistent with the first constraint $Ax=b$. –  Nick Alger May 17 '12 at 4:02

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.