How to use NumNZs value for assesing model

Answered

Baturay Yılmaz

December 21, 2020 19:24

• 
• 

Hello everyone,

I am solving a problem for my project by using Gurobi and now, for the report, I need to make some evaluations on the solution and on the problem. I have a question regarding to a model attribute NumNZs (number of nonzero coefficients in the constraint matrix). My question is, what is this attribute exactly measuring, and how can I interpret it? For example, can I use NumNZs value for assesing complexity of the problem? In other words, can someone claim that increase in the value of NumNZs makes the problem more complex and harder to solve. If this is a correct statement, I wonder how can we make such an argument/interpretation.

Thanks for any help in advance!

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 03:02 Edited

  This post is more than three 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 why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  December 22, 2020 12:10 Edited

  Hi Baturay,

  The number of nonzeros is measuring the density of the constraint matrix. As a concrete example let us have a look at the mip1.py example. The number of nonzeros is 5 while the size of the constraint matrix is \(2\times 3\), i.e., 5 out of possible 6 constraint coefficients are \(\neq 0\). One would say that this matrix is rather dense. The density of the constraint matrix affects most of the algorithmic steps in the solution of a linear program, e.g., factorization, i.e., it has a direct influence on the performance of the optimization algorithm but not on the complexity of the underlying problem.
  
  Solving extremely large optimization problems works well most of the time, because the constraint matrices are sparse, i.e., there are only a few nonzero coefficients compared to the maximum matrix size which have to be stored in memory. Additionally, large problems most often have some specific structure which can be exploited by the optimization algorithms. However, a dense matrix is no indicator for the complexity of the problem. One can formulate large problems with a dense constraint matrix which can be solved rather quickly while in contrast a different small problem with a sparse matrix cannot be solved within several hours. The MIPLIB2017 holds multiple such instances.

  What one can say is that a problem with more nonzeros will most likely require more memory to be stored, since more coefficients have to be held in memory.

  Best regards,
  Jaromił

  0

Post is closed for comments.