I have a question about solving large sparse matrix LP problem. It really confused me for a long time.
If I have a form like this:
I have all Fi data, which are in sparse form. How can I build a LP model to solve this problem faster? Any clue? Thank you!
For example, if I have tr(AiX)=bi, i=1,2,…,100. Ai is 1000*1000, Ai, X are symmetrix. How to build a LP model to solve this problem?
Second, please read Please read: make it easier to help you. It’s a lot easier to help if you can share a minimum working example showing what you have already tried.
Rather than exclusively using Gurobi, you should use JuMP to model this problem. Here is the documentation: Introduction · JuMP, and here are some examples: https://github.com/JuliaOpt/JuMP.jl/tree/release-0.19/examples.
Thank you, odow! Actually, I use Julia JuMP. I am confused about how to realize the constraint ci’Xci>=0. X here is a large sparse matrix. The dimension of X is 1512*1512.
Q=sparse(eigvecs(Y)) //Y is value of variable X
if P[i]<=-1.0e-5 // P[i] is the ith eigenvalue of X
@constraint(model, Q[:,i]'*X*Q[:,i]>=0) //(Q[:,i] is the ith eigenvector of X)
When I run this code, I got this “Warning: The addition operator has been used on JuMP expressions a large number of times. This warning is safe to ignore but may indicate that model generation is slower than necessary. For performance reasons, you should not add expressions in a loop. Instead of x += , use append!(x,y) to modify x in place. Uf y is a single variable, you may also use push!(x, coef, y) in place of x += coef*y”.
Anyway to avoid this? Thanks!
I am sorry. I know this is similar with SDP, but for some reason I have to use LP solver to solve this ci’Xci>=0.
If it doesn’t take too much time to build, you can ignore the warning. Otherwise, you need to write out the full scalarized expression:
@constraint(model, sum(sum(Q[j,i] * X[j,k] for j in 1:N) * Q[k, i] for k in 1:N) >= 0)