numerical issues
Answered
Hello,
I have a model with the coefficient statistics and the solution process shown below.
The LP files with original user-defined variable names (fn_OrigVarNames.lp -- Please use this file since I would be able to recognize the variable names) and Gurobi internal variable names are uploaded here. The full log file is also uploaded in the same folder.
Set parameter IterationLimit to value 2147483647
Set parameter TimeLimit to value 10000000000
Set parameter MIPGapAbs to value 0
Set parameter Threads to value 1
Let GUROBI read option file /local/user/proj/osigurobi.opt
Set parameter Threads to value 28
Set parameter LogFile to value "gurobilog.log"
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 32 physical cores, 32 logical processors, using up to 28 threads
Optimize a model with 1258117 rows, 1968422 columns and 5301728 nonzeros
Model fingerprint: 0xedd5dae2
Coefficient statistics:
Matrix range [1e-01, 1e+03]
Objective range [1e+00, 1e+00]
Bounds range [3e+00, 2e+04]
RHS range [1e+01, 2e+05]
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Presolve removed 648230 rows and 1505070 columns
Presolve time: 3.92s
Presolved: 609887 rows, 463352 columns, 2603465 nonzeros
......
Elapsed ordering time = 385s
Elapsed ordering time = 390s
Ordering time: 425.21s
Barrier statistics:
Dense cols : 288
Free vars : 10584
AA' NZ : 4.234e+07
Factor NZ : 8.403e+08 (roughly 7.0 GB of memory)
Factor Ops : 6.658e+12 (roughly 30 seconds per iteration)
Threads : 26
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.32073097e+09 -1.51922653e+07 5.79e+08 1.04e+00 1.06e+06 895s
1 1.19500460e+09 -2.34311380e+07 5.06e+08 7.11e+00 9.74e+05 911s
2 1.01794067e+09 -4.00567195e+07 4.07e+08 6.82e+00 8.25e+05 934s
.......................
306 5.48334123e+05 5.48334167e+05 4.16e-06 2.47e-05 1.98e-10 9811s
307 5.48334123e+05 5.48334167e+05 4.15e-06 2.47e-05 1.98e-10 9841s
308 5.48334123e+05 5.48334167e+05 4.15e-06 2.47e-05 1.98e-10 9870s
Barrier performed 308 iterations in 9870.20 seconds (8142.67 work units)
Sub-optimal termination - objective 5.48334139e+05
Crossover log...
222528 DPushes remaining with DInf 0.0000000e+00 9871s
77187 DPushes remaining with DInf 0.0000000e+00 9880s
61190 DPushes remaining with DInf 0.0000000e+00 9881s
41656 DPushes remaining with DInf 0.0000000e+00 9885s
30859 DPushes remaining with DInf 0.0000000e+00 9890s
6673 DPushes remaining with DInf 0.0000000e+00 9895s
1541 DPushes remaining with DInf 0.0000000e+00 9901s
737 DPushes remaining with DInf 0.0000000e+00 9906s
0 DPushes remaining with DInf 0.0000000e+00 9911s
58993 PPushes remaining with PInf 2.6050666e+00 9911s
46945 PPushes remaining with PInf 2.5803912e+00 9915s
39212 PPushes remaining with PInf 9.8335314e-01 9920s
29753 PPushes remaining with PInf 7.6699042e-01 9925s
19842 PPushes remaining with PInf 2.2915850e-01 9930s
11582 PPushes remaining with PInf 9.8435985e-02 9935s
4843 PPushes remaining with PInf 5.4658912e-02 9940s
325 PPushes remaining with PInf 0.0000000e+00 9945s
0 PPushes remaining with PInf 0.0000000e+00 9948s
Push phase complete: Pinf 0.0000000e+00, Dinf 3.2712997e+02 9948s
Iteration Objective Primal Inf. Dual Inf. Time
149937 5.4833386e+05 0.000000e+00 3.271300e+02 9948s
150339 5.4833346e+05 0.000000e+00 5.089857e+02 9953s
150741 5.4833312e+05 0.000000e+00 1.679922e+02 9957s
151143 5.4833300e+05 0.000000e+00 6.220078e+01 9961s
151454 5.4833279e+05 0.000000e+00 6.031184e+00 9967s
151724 5.4833263e+05 0.000000e+00 2.967971e+01 9972s
.......
158841 5.4833153e+05 0.000000e+00 3.129375e+02 10103s
159121 5.4833152e+05 0.000000e+00 3.730525e-02 10109s
Warning: 1 variables dropped from basis
Warning: switch to quad precision
159521 5.4833152e+05 0.000000e+00 3.730659e-02 10116s
159711 5.4833152e+05 0.000000e+00 1.596853e+00 10125s
159931 5.4833151e+05 0.000000e+00 2.109175e+01 10135s
160201 5.4833150e+05 0.000000e+00 1.387103e+01 10146s
.............
162717 5.4833149e+05 0.000000e+00 0.000000e+00 10260s
Extra simplex iterations after uncrush: 239
Solved with barrier
Solved in 162717 iterations and 10260.47 seconds (8659.47 work units)
Optimal objective 5.483314906e+05
User-callback calls 863051, time in user-callback 0.55 sec
Wrote requested result file 'fn_Gurobi.lp'
Reading through this forum and Gurobi documentation, my conclusion was that the model has numerical issues. However, the range of coefficients does not seem to be very wide. This is an LP problem.
The below is written by CPLEX; it indicates that the model has 492 dense columns (I don't know how to get the number of dense columns from Gurobi).
DUAL formed by presolve
LP Presolve eliminated 592040 rows and 1448954 columns.
Aggregator did 55628 substitutions.
Reduced LP has 463841 rows, 613886 columns, and 2607640 nonzeros.
Presolve time = 4.90 sec. (3319.20 ticks)
Parallel mode: using up to 20 threads for barrier.
***NOTE: Found 492 dense columns.
Number of nonzeros in lower triangle of A*A' = 3212945
Using Nested Dissection ordering
Total time for automatic ordering = 19.97 sec. (19185.60 ticks)
Summary statistics for Cholesky factor:
Threads = 20
Rows in Factor = 464333
Integer space required = 2089260
Total non-zeros in factor = 56400467
Total FP ops to factor = 168481270181
I would appreciate it if you could help me identify the source of the numerical issues. I have used scaling to bring the range of coefficients down to 1e4 (as can be seen from the coefficients statistics). What can be changed to fix the numerical issues?
I intend to add more constraints to the model later on; however, recognizing that there are numerical issues in the model, I would like to address those issues first, before adding other constraints.
-
Official comment
-
Gurobi Staff
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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
The below is written by CPLEX; it indicates that the model has 492 dense columns (I don't know how to get the number of dense columns from Gurobi).
The number of dense columns is reported in the Barrier statistics
Elapsed ordering time = 385s
Elapsed ordering time = 390s
Ordering time: 425.21s
Barrier statistics:
Dense cols : 288
Free vars : 10584
AA' NZ : 4.234e+07I would appreciate it if you could help me identify the source of the numerical issues. I have used scaling to bring the range of coefficients down to 1e4 (as can be seen from the coefficients statistics). What can be changed to fix the numerical issues?
You introduce many constraints of the form
- c x + 1000 y = 0
which looks like you are trying to change the order of magnitude of \(x\) to fit \(y\) (or vice versa). It would be better to use a different order of magnitude for \(y\) to start with. So, if you mean to say that \(c x\) equals \(1000 y\) where \(y\) are, e.g., $. Then, it would be better to work with thousands of $ and define the above constraint as
- c x + y = 0
This can dramatically improve numerical and overall performance of the algorithm. The only thing you have to do after the optimization procces finished, is to re-scale the solution point and objective values to the order of magnitudes you need for your application. Of course, I am just guessing what your equalities mean but I hope that the overall idea is still applicable.
Note that overall your model performs quite well. Crossover is able to turn the sub-optimal solution into an optimal one.
Best regards,
Jaromił0 -
-
Thank you very much Jaromił Najman
The cost is in millions of dollars, and if I were to convert it to thousands of dollars, I would have multiplication by 1000 in other places. I will try this suggestion and will report back.
The overall run-time is long since I will be adding many more constraints/variables to the model. Is there any other aspect of the model that I can improve to make it run faster?
I have updated the file by converting it to thousands of dollars and scaling the equations/variables. I would appreciate it if you could take a look again.
0 -
-
Hi Ali,
The model looks fine. At this point, I would recommend to try to find parameters which improve performance. The easiest way is to use Gurobi's parameter tuning tool. I would run the tuner for at least 1-2 days on the machine you are planning to use for your models. You could also try some manual tuning with parameters listed as most important ones. Your model is an LP thus, many parameters don't apply for your model. I think, the most interesting ones would be Method, Presolve, Aggregate.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
4 comments