"Error: converted symmetric Q matrix has more than two billion nonzeros" despite bilinear terms with binaries
AnsweredDear GurobiTeam,
First of all, I would like to show an excerpt from the solver log:
Set parameter IntFeasTol to value 1e06
Set parameter Method to value 0
Set parameter ConcurrentMethod to value 3
Set parameter NetworkAlg to value 1
Set parameter CliqueCuts to value 2
Set parameter LogFile to value "mip1.log"
Set parameter MIQCPMethod to value 1
Set parameter PreQLinearize to value 2
Set parameter PreSparsify to value 2
Set parameter Threads to value 1
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64  Windows 10.0 (19045.2))
CPU model: AMD EPYC 7302P 16Core Processor, instruction set [SSE2AVXAVX2]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads
Optimize a model with 6 rows, 671223170 columns and 503417383 nonzeros
Model fingerprint: 0x8c6a5bd7
Model has 1048786200 quadratic objective terms
Model has 111870528 quadratic constraints
Variable types: 111870529 continuous, 559352641 integer (545368824 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+06]
QMatrix range [1e+00, 9e+00]
QLMatrix range [2e01, 1e+06]
Objective range [6e+01, 2e+09]
QObjective range [2e+01, 1e+07]
Bounds range [4e+01, 2e+07]
RHS range [0e+00, 0e+00]
QRHS range [1e+06, 1e+07]
Warning: Model contains large objective coefficients
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Found heuristic solution: objective 0.0000000
Found heuristic solution: objective 2.768146e+15
Error: converted symmetric Q matrix has more than two billion nonzeros
Explored 0 nodes (0 simplex iterations) in 96.63 seconds (15.44 work units)
Thread count was 1 (of 32 available processors)
Solution count 2: 2.76815e+15 0
No other solutions better than 0
Best objective 2.768145962781e+15, best bound , gap 
ERROR: converted symmetric Q matrix has more than two billion nonzeros
The model starts with 1.048.786.200 quadratic objective terms, so with less than the limit of two billion.
I assume, Gurobi creates a symmetric Q matrix by mirroring the nondiagonal elements on the diagonal (and multiplication by 0.5) and so the resulting number of quadratic objective terms exceeds the limit of two billion. Is that assumption right?
In my example all quadratic objective terms (and all quadratic terms in the quadratic constraints) involve a binary variable. Maybe I am wrong (?), but I think for the presolve Q matrix linearization (PreQLinearize) it is not necessary to create a symmetric Q matrix. If I would model the linearization myself (which I would not like to do because of the effort and because Gurobi finds even better bounds), the single nondiagonal elements would be enough for me.
Are my thoughts correct and is there a way to prevent Gurobi from creating a symmetric matrix for the quadratic terms involving binaries?
Thank you very much
Thomas
P.S.: The number of rows is very small, but I am going to add a multitude through callbacks later (not implemented yet).

Hi Thomas,
You are right that Gurobi does not store the whole symmetric Q matrix. However, for some internal (presolve) algorithms double the space is required, i.e., some subprocesses require additional space for nonsquares. So in the end, Gurobi might need #squares + 2*#nonsquares. Thus, the error is triggered already with ~1 bil quadratic objective terms in your case.
I have to admit that I never faced a model with > 1 bil quadratic objective terms before so this is quite a new challenge overall. Is there a way to decrease the size of your model? Maybe divide it into smaller chunks? Or perform some manual presolve to reduce the number of quadratic objective terms?
Best regards,
Jaromił0 
Hi Jaromił,
thanks again for your continuous support.
I am in a(nother) testing phase of my work and it is not an actual problem to reduce the problem size for examples.
I already reduced the size below 1 billion quadratic objective terms and I don't receive the error mentioned above.
But shortly afterwards I got an "Out of memory" in the rootnodesimplex in one example,
 and a program abort during presolve withut error message in another example. I assume, it also happend due to memory issues.
Density is a problem of my approaches, even with ~500 GB of memory on my machine.
Even if I would buy more memory I would probably run into performance issues.
So I need to elaborate some ideas to sparsify my problem  I have a lot of ideas, so work goes on ;)Thanks again
Thomas
0 
Hi Thomas,
 "Out of memory" in the rootnodesimplex in one example,
 and a program abort during presolve withut error message in another example. I assume, it also happend due to memory issues.
For quadratic presolve, often more space is required compared to linear presolve. In particular, because we have to run over 2 variables in a product instead of only one. You could try running without presolve but this would probably deteriorate performance by a lot.
So I need to elaborate some ideas to sparsify my problem  I have a lot of ideas, so work goes on ;)
That's good to hear. Hopefully you can come up with something to make your algorithm work even with the memory limits.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments