计算科学 - 求解大型混合整数二次规划的合适算法是什么？ - 吾爱随笔录

计算科学优化二次规划混合整数规划

2021-12-19 06:15:02

我对一个非常大的二次规划 (QP) 问题的解决方案感兴趣

\begin{aligned} min_{x \in R^{n}} & x^{T} Q x \\ s u b j e c t t o & A x = b \\ x \in {0, 1}^{n} \end{aligned}

$\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}$

其中，是一个密集的半正定矩阵，其条目是可以快速计算的自然数，而。 $n=10^7$ $Q$ $A \in \mathbb{N}^{n \times 20}$

对于这么大的问题，什么算法适合，什么是好的实现？

2个回答

这是一个混合整数 QP，而不是一个半正定 QP。的大倍数来制作具有二进制约束 psd 的任何 QP 。） $x^Tx-e^Tx$

Couenne ( https://projects.coin-or.org/Couenne ) 可能是一个合适的求解器。

您也可以尝试GloMIQO。它在 GAMS 中可用（从 23.8 版开始），专门设计用于求解具有线性或二次约束的混合整数二次规划，并有一些有希望的结果。如果购买 GAMS 许可证不可行，您也可以尝试直接联系软件的作者。

其它你可能感兴趣的问题