How to solve large sparse LPs in Gurobi

Specific Domains Optimization (Mathematical)
,
1

Hi,

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:
image
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!

2

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?

3

First, welcome!

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.

2 Likes
5

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
for i=1:1512
   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)
   end
end

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!

6

It’s likely you want to create a semi-definite variable instead:
http://www.juliaopt.org/JuMP.jl/v0.19.2/variables/#Semidefinite-variables-1
Alternatively, you can use
http://www.juliaopt.org/JuMP.jl/v0.19.2/constraints/#Semidefinite-constraints-1

7

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.

8

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)
1 Like
9

Thank you!!!