Number of QUBO variables

回答済み

Gan Zheng

2024年07月26日 15:48

• 

Hi 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

 

 

関連

• QUBO

0

• 

  Vishwajeet Ohal

  2024年09月13日 19:41

  • 

  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
• 

  Matthias Miltenberger

  • Gurobi Staff

  2024年09月17日 14:04

  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

サインインしてコメントを残してください。