"Error: converted symmetric Q matrix has more than two billion nonzeros" despite bilinear terms with binaries
Answered
Dear Gurobi-Team,
First of all, I would like to show an excerpt from the solver log:
Set parameter IntFeasTol to value 1e-06
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 16-Core Processor, instruction set [SSE2|AVX|AVX2]
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 [2e-01, 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 non-diagonal 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 non-diagonal 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 sub-processes require additional space for non-squares. So in the end, Gurobi might need #squares + 2*#non-squares. 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 root-node-simplex 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 root-node-simplex 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 -
Hi Jaromił Najman,
I would like to come back to my problems here.
I reformulated my problem (among other approaches with your help in the topic: https://support.gurobi.com/hc/en-us/community/posts/8434969582225-Parameter-PreSparsify) by
- finding some more compact formulations for my initial problem
- doing the bilinear reformulation of quadratic terms manually (so now I have a LP)
- and leaving out some constraints that I will add later via callback.
After I did this, the solving process took weeks for presolve without finishing and with only some deleted rows and columns shortly after starting. I am also quite unsure if these presolve actions will still be useful when the callbacks are added later, because by the number of actions I can guess what presolve is doing. So I have deactivated presolve completely.
However, I'm still running out of memory. I think this happens when the first relaxation is to be solved with Simplex. I'll give you a log here:
Set parameter Method to value 0
Set parameter Symmetry to value 0
Set parameter CliqueCuts to value 2
Set parameter LogFile to value "mip1.log"
Set parameter Presolve to value 0
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 16-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads
Optimize a model with 195773430 rows, 309356258 columns and 615288157 nonzeros
Model fingerprint: 0x6d9dad0f
Variable types: 195773424 continuous, 113582834 integer (97886712 binary)
Coefficient statistics:
Matrix range [9e-01, 1e+08]
Objective range [1e+00, 2e+09]
Bounds range [1e+00, 1e+08]
RHS range [6e+06, 3e+07]
Warning: Model contains large matrix coefficients
Warning: Model contains large objective coefficients
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 78s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 86s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 92s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 137s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 142s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 156s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 165s
User MIP start produced solution with objective -0 (178.49s)
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 172s
Loaded user MIP start with objective -0
Processed MIP start in 223.48 seconds (126.25 work units)
Presolve removed 0 rows and 0 columns (presolve time = 27s) ...
Presolve removed 0 rows and 0 columns (presolve time = 35s) ...
Presolve removed 0 rows and 0 columns (presolve time = 76s) ...
Variable types: 195773424 continuous, 113582834 integer (98065077 binary)
Explored 0 nodes (0 simplex iterations) in 2035.21 seconds (1356.69 work units)
Thread count was 1 (of 32 available processors)
Solution count 0
Solve interrupted (error code 10001)
Best objective -, best bound -, gap -
ERROR: Out of memory
Z:\Test\Project1.exe (Prozess "29824") wurde mit Code "1" beendet.
Drücken Sie eine beliebige Taste, um dieses Fenster zu schließen.I would now like to ask if there are some parameters I can change (in addition to the ones I have already changed) that might make Gurobi focus on memory savings rather than performance?
Additionally, I would like to ask if I am correct that a given MIP solution (from my given MIP start) is not necessarily a warm start for the relaxed simplex?
So I would like to ask if it might be helpfull to provide PStart, Dstart, Vbasis and/or Cbasis? Maybe I can provide such information. Is there any literature you can recommend on this topic and what exactly Gurobi does there (more or less)? I only have a rough idea.Thank you very much
Thomas
0 -
Hi Thomas,
I would now like to ask if there are some parameters I can change (in addition to the ones I have already changed) that might make Gurobi focus on memory savings rather than performance?
You already have used all parameter possibilities to reduce memory consumption. I think the only way from now would be to either change to a machine with even more memory or try to perform some simple presolve yourself to reduce the size of the model. Maybe some sort of a decomposition approach is applicable?
Additionally, I would like to ask if I am correct that a given MIP solution (from my given MIP start) is not necessarily a warm start for the relaxed simplex?
So I would like to ask if it might be helpfull to provide PStart, Dstart, Vbasis and/or Cbasis?The given MIP Start is not necessarily used as a warm start to Simplex. However, it is considered as an option internally. Providing PStart, DStart, VBasis, and CBasis would not help as they are ignored for MIPs, see PStart.
Is there any literature you can recommend on this topic and what exactly Gurobi does there (more or less)? I only have a rough idea.
Which topic exactly do you mean?
Best regards,
Jaromił0 -
Hi Jaromił Najman,
thanks for your reply.
Yes, decomposition is an option. I already have two ideas for grouping the variables reasonably.
I suppose the partition heuristic with PartitionPlace including 16 ("before the root relaxation is solved") won't help here, because even if the partition heuristic finds a better solution before the root relaxation is solved, the size of the root relaxation isn't reduced, or? But I will give it a try (and report here), because even finding a better solution than the given MIP-Start (with an objective of zero) would deliver some benefit.
Since my constraints don't have a block structure, I suppose Benders decomposition and Dantzig–Wolfe decomposition are not applicable.
I will try a manual decomposition approach by setting lb=ub=incumbent for all variables that are not part of the actual subproblem. I will then iterate through the subproblems. Maybe that already helps.
My question regarding a literature hint was about PStart, Dstart, Vbasis and Cbasis. For example, I don't understand why such information is ignored for the root relaxation of a MILP.
Best regards
Thomas
0 -
Hi Thomas,
I suppose the partition heuristic with PartitionPlace including 16 ("before the root relaxation is solved") won't help here, because even if the partition heuristic finds a better solution before the root relaxation is solved, the size of the root relaxation isn't reduced, or?
Correct.
My question regarding a literature hint was about PStart, Dstart, Vbasis and Cbasis. For example, I don't understand why such information is ignored for the root relaxation of a MILP.
I am not aware of any specific literature about these attributes. I would guess that any good MIP or LP textbook talk about warm-start basis. In theory providing a warm-start basis for the root node relaxation of a MIP could be possible. However, in practice one would have to carry this basis through all presolve steps which might destroy (dual) properties of the provided basis. One could argue that we could turn off presolve but then we would lose the most beneficial part of the MIP algorithm.
Best regards,
Jaromił0 -
Hi Jaromił,
I did some testing ...
I tried the partition heuristic (although I didn't expect a solution to my general memory problem, but I want to explore general properties ...). Here is the log:Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2))
CPU model: AMD EPYC 7302P 16-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads
Optimize a model with 195773430 rows, 309356258 columns and 615288157 nonzeros
Model fingerprint: 0x71db19a7
Variable types: 195773424 continuous, 113582834 integer (97886712 binary)
Coefficient statistics:
Matrix range [9e-01, 1e+08]
Objective range [1e+00, 2e+09]
Bounds range [1e+00, 1e+08]
RHS range [6e+06, 3e+07]
Warning: Model contains large matrix coefficients
Warning: Model contains large objective coefficients
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Using partitions.
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 80s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 81s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 87s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 93s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 137s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 142s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 157s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 166s
User MIP start produced solution with objective -0 (179.01s)
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 172s
Loaded user MIP start with objective -0
Processed MIP start in 222.93 seconds (126.25 work units)
Presolve removed 0 rows and 0 columns (presolve time = 26s) ...
Presolve removed 0 rows and 0 columns (presolve time = 34s) ...
Presolve removed 0 rows and 0 columns (presolve time = 74s) ...
Variable types: 195773424 continuous, 113582834 integer (98065077 binary)
Starting partition heuristic: 1712304 partitions, 1 threads
Explored 0 nodes (0 simplex iterations) in 1659.39 seconds (727.11 work units)
Thread count was 1 (of 32 available processors)
Solution count 0
Solve interrupted (error code 10001)
Best objective -, best bound -, gap -
ERROR: Out of memoryDoes that mean, that the memory error already occured during the partition heuristic oder did Gurobi finish the partition heuristic without further logging and the memory error occured during the following simplex of the root relaxation?
Then I gave a chance to the NoRel heuristic. The log is here:
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2))
CPU model: AMD EPYC 7302P 16-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads
Optimize a model with 195773430 rows, 309356258 columns and 615288157 nonzeros
Model fingerprint: 0x6d9dad0f
Variable types: 195773424 continuous, 113582834 integer (97886712 binary)
Coefficient statistics:
Matrix range [9e-01, 1e+08]
Objective range [1e+00, 2e+09]
Bounds range [1e+00, 1e+08]
RHS range [6e+06, 3e+07]
Warning: Model contains large matrix coefficients
Warning: Model contains large objective coefficients
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 79s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 80s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 86s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 93s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 136s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 141s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 157s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 165s
User MIP start produced solution with objective -0 (177.98s)
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 171s
Loaded user MIP start with objective -0
Processed MIP start in 222.68 seconds (126.25 work units)
Presolve removed 0 rows and 0 columns (presolve time = 26s) ...
Presolve removed 0 rows and 0 columns (presolve time = 34s) ...
Presolve removed 0 rows and 0 columns (presolve time = 75s) ...
Variable types: 195773424 continuous, 113582834 integer (98065077 binary)
Starting NoRel heuristic
Elapsed time for NoRel heuristic: 19s (best bound 6.46247e+15)
Explored 0 nodes (0 simplex iterations) in 2294.87 seconds (1972.62 work units)
Thread count was 1 (of 32 available processors)
Solution count 0
Solve interrupted (error code 10001)
Best objective -, best bound -, gap -
ERROR: Out of memorySimilarly, I would like to ask if this means that the memory error already occured during the NoRel heuristic or if Gurobi finished the NoRel heuristic and the memory error occured during the following simplex of the root relaxation?
And for a basic understanding (I have read the following information: https://support.gurobi.com/hc/en-us/community/posts/9282521673745-What-is-phase-1-solution-): Since my given MIP start resulted in a valid solution, I assume that the NoRel heuristic directly starts in phase 2, although there is no output in the log indicating this. Is that right?
Is the displayed best bound (6.46247e+15 - the problem is formulated as a maximization problem) a valid solution that has actually been found or is it a relaxation value?Best regards
Thomas
0 -
PS: I I would like to add that I set NoRelHeurTime = 36000 s. Therefore, the time limit will not be the reason for the program termination.
0 -
Hi Thomas,
Does that mean, that the memory error already occured during the partition heuristic oder did Gurobi finish the partition heuristic without further logging and the memory error occured during the following simplex of the root relaxation?
It looks like the machine ran out of memory during the partition heuristic.
Similarly, I would like to ask if this means that the memory error already occured during the NoRel heuristic or if Gurobi finished the NoRel heuristic and the memory error occured during the following simplex of the root relaxation?
Here, it looks like the machine ran out of memory during the NoRel heuristic.
The reason for this behavior is most likely that both heuristics generate a (way smaller) copy of the model, but given the size of the original model, it is very likely already enough to exceed the machine's total memory.
And for a basic understanding (I have read the following information: https://support.gurobi.com/hc/en-us/community/posts/9282521673745-What-is-phase-1-solution-): Since my given MIP start resulted in a valid solution, I assume that the NoRel heuristic directly starts in phase 2, although there is no output in the log indicating this. Is that right?
Yes, this is correct.
Is the displayed best bound (6.46247e+15 - the problem is formulated as a maximization problem) a valid solution that has actually been found or is it a relaxation value?
This is a relaxation value that is normally way below the root relaxation value. The NoRel heuristic computes a usually loose dual bound.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
10 comments