极稀疏整数二次规划

Question

我正在研究具有大量变量（数亿以上）的优化问题。他们每个人都应该是一个0-1的二进制变量。

我可以将其写成 (maximize x'Qx) 的形式，其中 Q 是半正定的，而且我使用的是 Julia，所以包 COSMO.jl 看起来非常合适。但是，我的问题有很多稀疏性。除了大约 sqrt(|Q|) 个条目外，Q 为 0，并且对于约束，变量上有大约 sqrt(|Q|) 线性约束。

我可以使用 SparseArrays 很容易地描述这个系统，但将问题输入 COSMO 的最自然方式似乎是使用标准数组。有什么方法可以利用这个大问题的稀疏性？

Answer 1

虽然您的文档中没有示例代码，但也许这会有所帮助：

JuMP 适用于稀疏数组，所以也许最简单的事情就是在目标函数的构造中使用它：

julia> using JuMP, SparseArrays, COSMO

julia> m = Model(with_optimizer(COSMO.Optimizer));

julia> q = sprand(Bool, 20, 20,0.05) # for readability I use a binary q
20×20 SparseMatrixCSC{Bool, Int64} with 21 stored entries:
⠀⠀⠀⡔⠀⠀⠀⠀⡀⠀
⠀⠀⠂⠀⠠⠀⠀⠈⠑⠀
⠀⠀⠀⠀⠀⠤⠀⠀⠀⠀
⠀⢠⢀⠄⠆⠀⠂⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠄⠀⠀⠌

julia> @variable(m, x[1:20], Bin);

julia> x'*q*x
x[1]*x[14] + x[14]*x[3] + x[15]*x[8] + x[16]*x[5] + x[18]*x[4] + x[18]*x[13] + x[19]*x[14] + x[20]*x[11]

您可以看到方程得到了正确的简化。

确实，您可以使用具有 1 亿个元素的非常稀疏 q 来检查性能：

julia> q = sprand(10000, 10000,0.000001)
10000×10000 SparseMatrixCSC{Float64, Int64} with 98 stored entries:
...

julia> @variable(m,z[1:10000], Bin);

julia> @btime $z'*$q*$z
  1.276 ms (51105 allocations: 3.95 MiB)

可以看到在构造目标函数的时候，你刚刚得到了预期的性能。

极稀疏整数二次规划

Extremely Sparse Integer Quadratic Programming

julia

sparse-matrix

julia-jump

quadratic-programming