Gurobi and Runtime Variation

回答済み

Avery Chan

2025年07月29日 18:36

• 
• 

I'm working on an MIQP optimization project involving a 2D matrix Q and a 1D vector of variables x, where I'm trying to minimize x^T Q x.

I have a few questions and would really appreciate it if you were able to help me:

1. My original code was model.setObjective(x @ Q @ x, GRB.MINIMIZE), but I had to change Q to a sparse matrix as Gurobi was returning memory errors. Now my code to set the objective is

But this has caused my code to run slower? Is there any way I can replicate the speed of the original? Also, does Gurobi have a way of managing dense matrices with many zero values?

2. Does Gurobi utilize randomization? In one such trial, I noticed that shrinking my matrix Q from 18,000 x 18,000 to 16,000 x 16,000 drastically increased the amount of time Gurobi took to solve the program. Or is it a function of the data - the 18,000 x 18,000 trial didn't explore many nodes whereas the 16,000 x 16,000 trial did.

3. When does Gurobi “decide” to check nodes? I remember one time I ran my program (normalizing my covariance matrix and making it positive definite) and it took a while during root simplex and went through many different iterations, but only searched one node and the program took less than 20 minutes. After that, I ran the program with slightly different data (still normalizing my covariance matrix and making it positive definite). This time, it didn't take very long during the root simplex phase but had to search through hundreds of thousands of nodes and still kept running after hours. I'm not sure why this is as I did not change the constraints or variables in the program at all. 

 

関連

• Performance
• MIQP

0

• 

  Riley Clement

  • Gurobi Staff

  2025年07月31日 01:48

  Hi Avery,

  Now my code to set the objective is ….

  I think we're missing something here.

  Also, does Gurobi have a way of managing dense matrices with many zero values?

  Under the hood yes, or are you asking about some API functionality?  Which programming language are you using?

  Does Gurobi utilize randomization? …

  Yes, see the following articles:

  • Is Gurobi random?
  • What is performance variability?
  • How can I make accurate comparisons?

  When does Gurobi “decide” to check nodes?

  Gurobi will start exploring the branch and bound tree after presolve and after solving the linear relaxation.  These two videos may help:

  *  Intro to Algorithms (44m50s mark) 

  * Advanced algorithms 

  - Riley

   

  0

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