Skip to main content

numerical issues

Answered
Ali Jahanbani Ardakani
Edited

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.

0

Comments

4 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • 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.
  • Jaromił Najman
    • Gurobi Staff
    Edited

    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+07

    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?

    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
  • Ali Jahanbani Ardakani
    Edited

    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
  • Jaromił Najman
    • Gurobi Staff

    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.

Didn't find what you were looking for?

New post