Number of QUBO variables
AnsweredHi Gurobi Team,
I am new here and wondering whether there is a limit of QUBO variables that can be solved by Gurobi, beyond which it would be difficult.
I am trying to solve a problem min x'*Q*x where Q is a very sparse symmetric matrix with 90% zero elements. When the length of x is below 200, the code 'result = solve_qubo(sp.csr_matrix(Q))' can return good results (I compared it with simulated annealing) very quickly, but when the length of x increases to about 500, it got stuck and showing below (very large gap)
Time: s, best objective: , best bound: , gap: 58.73%.
Could you advise please? I can also share the matrix Q in a file if you need.
Many thanks
Gan
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
I am working on QUBO problems too. From what I saw, Gurobi may not perform as good as simulated annealing on larger problems. Of course, the performance depends upon the problem instance too, but I think in general it is slightly worse.
Though, the gap of almost 60% does seem surprising. How are you calculating the gap exactly?0 -
You could try using a different setting of parameter PreQLinearize for QUBOs. This should help with larger models.
The gap is computed as usual. It's just the relative difference between the incumbent solution value and the dual bound. You can read more here: MIPGap
0
Post is closed for comments.
Comments
3 comments