1
$\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?

  • 0
    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$.2012-05-17

0 Answers 0