Skip to main content

Objective value convergence and sub-optimal termination

Answered
Philipp Dunkel
First Comment
First Question
Gurobi-versary

Dear Gurobi team,

I am solving a large LP using the barrier algorithm without crossover.

However, in several model runs (only a minor subset of constaints are changed), the model sometimes:

1.) shows good convergence until a certain iteration after which there is significant divergence in the objective value for some iterations before the algorithm manages to recover and converges to optimal solution.
2.) The model run terminates either sub-optimally or with numerical trouble (especially without BarHomogeneous)

 

1) is not super problematic and only increases optimization time. But 2) results in unrealistic or non-existent solutions.

I have tried with different settings (e.g. NumericFocus, tighter tolerances, Presolve, with/ without BarHomogeneous). However, I have not yet found a set of setting for which I could consistently eliminate these issues.

Any advice is greatly appreciated.

Thanks in advance!

 

-----------------------------
Examples:
1.)

Set parameter Method to value 2
Set parameter Crossover to value 0
Set parameter Cuts to value 0
Set parameter BarHomogeneous to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64)

CPU model: Intel(R) Xeon(R) Gold 6334 CPU @ 3.60GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 8 threads

Optimize a model with 8945123 rows, 7875412 columns and 32062067 nonzeros
Model fingerprint: 0xfdb9ba73
Coefficient statistics:
  Matrix range     [1e-05, 7e+02]
  Objective range  [4e-10, 2e+05]
  Bounds range     [1e-05, 2e+06]
  RHS range        [1e-05, 5e+05]
Presolve removed 2261157 rows and 1750000 columns (presolve time = 5s) ...
Presolve removed 3032398 rows and 2521241 columns (presolve time = 10s) ...
Presolve removed 3033118 rows and 2734330 columns (presolve time = 25s) ...
Presolve removed 3958480 rows and 2734647 columns (presolve time = 37s) ...
Presolve removed 3958480 rows and 2734647 columns
Presolve time: 39.59s
Presolved: 4986643 rows, 5140765 columns, 23551666 nonzeros
Elapsed ordering time = 310s
Ordering time: 325.54s

Barrier statistics:
 Dense cols : 4375
 Free vars  : 34946
 AA' NZ     : 8.162e+07
 Factor NZ  : 2.200e+09 (roughly 20.0 GB of memory)
 Factor Ops : 3.163e+13 (roughly 80 seconds per iteration)
 Threads    : 8

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   3.83579965e+15 -2.39219260e+11  7.94e+10 4.50e-13  8.40e+09   433s
   1   3.16435614e+15 -6.23959340e+11  6.74e+10 4.28e+03  7.38e+09   480s
   2   2.50389155e+15 -2.77942370e+12  5.55e+10 3.56e+03  6.15e+09   588s
   3   1.59341232e+15 -7.41541684e+12  3.77e+10 2.80e+03  4.64e+09   715s
   4   6.07166909e+14 -1.48042081e+13  1.46e+10 8.00e+02  1.68e+09   851s
   5   1.39632030e+14 -1.13504660e+13  3.56e+09 1.40e+02  3.22e+08   983s
   6   3.80651001e+13 -5.64470247e+12  1.06e+09 3.39e+01  7.28e+07  1128s
   7   6.53769819e+12 -2.98508571e+12  2.30e+08 1.23e+01  1.49e+07  1271s
   8   8.79687818e+11 -1.46744014e+12  4.45e+07 4.00e+00  2.88e+06  1412s
   9   1.27223460e+10 -2.86461271e+11  2.88e+06 4.19e-01  1.47e+05  1564s
  10   5.49434230e+09 -1.04501051e+11  1.40e+06 1.48e-01  4.60e+04  1699s
  11   2.92746356e+09 -7.31019745e+10  8.62e+05 1.03e-01  2.80e+04  1841s
  12   1.59741953e+09 -4.48657790e+10  5.26e+05 6.26e-02  1.54e+04  2002s
  13   5.58963436e+08 -2.36403641e+10  1.91e+05 3.30e-02  6.48e+03  2141s
  14   1.15461990e+08 -2.71585548e+09  2.34e+04 3.86e-03  5.54e+02  2298s
...
 165   3.93880637e+02  3.92788834e+02  9.04e-07 4.98e-08  5.79e-08  25052s
 166   3.93873914e+02  3.92802367e+02  8.95e-07 5.44e-08  5.70e-08  25195s
 167   3.93866714e+02  3.92809415e+02  8.84e-07 7.92e-08  5.62e-08  25340s
 168   3.93866228e+02  3.92810670e+02  8.84e-07 7.87e-08  5.61e-08  25488s
 169   3.93865356e+02  3.92813831e+02  8.83e-07 7.87e-08  5.60e-08  25657s
 170   3.83579921e+15 -2.39219263e+12  7.94e+10 7.10e-12  8.09e+10  25956s
 171   2.24962586e+15 -6.33627324e+13  4.71e+10 2.52e+04  4.18e+10  26124s
 172   6.31178818e+14 -4.09707261e+13  1.40e+10 5.55e+03  5.76e+09  26300s
 173   5.61200395e+13 -1.83961316e+13  1.50e+09 5.28e+02  3.01e+08  26453s
 174   2.16707463e+12 -3.31902111e+12  9.60e+07 5.14e+01  9.38e+06  26600s
 175   5.60568321e+10 -2.71671410e+11  6.26e+06 3.80e+00  2.26e+05  26765s
 176   9.20143564e+09 -7.33532380e+10  1.36e+06 8.50e-01  3.16e+04  26899s
 177   4.39815713e+09 -4.00313406e+10  8.59e+05 4.56e-01  1.59e+04  27037s
 178   2.48977366e+09 -1.90719079e+10  5.75e+05 2.10e-01  7.40e+03  27197s
 179   3.00545803e+08 -3.43703654e+09  9.38e+04 4.02e-02  8.88e+02  27355s
 180   3.30543742e+07 -3.11213216e+08  1.05e+04 3.46e-03  6.07e+01  27502s
 181   7.87475708e+06 -3.42880229e+07  2.18e+03 4.32e-04  6.65e+00  27656s
 182   9.21337454e+05 -2.84100587e+06  1.40e+02 4.76e-05  5.16e-01  27784s
 183   2.34596754e+05 -7.25077224e+05  7.01e+00 1.39e-05  1.21e-01  27927s
 184   1.23313448e+05 -3.51472994e+05  9.12e-01 2.46e-05  5.75e-02  28069s
 185   7.50035079e+04 -1.82230930e+05  4.69e-02 1.33e-05  3.02e-02  28208s
 186   4.98466497e+04 -8.82045275e+04  1.84e-02 6.78e-06  1.58e-02  28357s
 187   2.91814807e+04 -3.68245132e+04  9.26e-03 3.83e-06  7.33e-03  28520s
 188   2.49061133e+04 -2.31957046e+04  7.71e-03 3.81e-06  5.25e-03  28640s
 189   2.33319301e+04 -2.09419218e+04  7.12e-03 3.49e-06  4.82e-03  28773s
 190   1.25628020e+04 -1.23182983e+04  3.16e-03 2.24e-06  2.68e-03  28924s
 191   4.21914975e+03 -5.66737239e+03  3.16e-04 8.27e-06  1.06e-03  29077s
 192   2.46467696e+03 -3.29083078e+03  4.96e-05 5.32e-06  6.21e-04  29233s
 193   1.99784413e+03 -3.01739659e+03  3.62e-05 4.96e-06  5.41e-04  29382s
 194   1.26092177e+03 -1.79633355e+03  2.05e-05 3.36e-06  3.33e-04  29535s
 195   1.04416613e+03 -1.07545555e+03  1.48e-05 2.35e-06  2.33e-04  29686s
...
 314   3.93042155e+02  3.93042132e+02  1.55e-08 3.47e-09  2.07e-12  49414s
 315   3.93042154e+02  3.93042132e+02  1.60e-08 3.30e-09  1.97e-12  49494s
 316   3.93042154e+02  3.93042132e+02  1.59e-08 3.26e-09  1.95e-12  49574s
 317   3.93042152e+02  3.93042132e+02  1.51e-08 3.22e-09  1.88e-12  49655s

Barrier solved model in 317 iterations and 49655.01 seconds (60753.09 work units)
Optimal objective 3.93042152e+02

 

2)

Set parameter Method to value 2
Set parameter Crossover to value 0
Set parameter Cuts to value 0
Set parameter BarHomogeneous to value 1
Set parameter QCPDual to value 1
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64)

CPU model: Intel(R) Xeon(R) Gold 6334 CPU @ 3.60GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 8 threads

Optimize a model with 8939339 rows, 7869620 columns and 32038008 nonzeros
Model fingerprint: 0x191094ca
Coefficient statistics:
  Matrix range     [1e-05, 7e+02]
  Objective range  [4e-10, 2e+05]
  Bounds range     [1e-05, 2e+06]
  RHS range        [1e-05, 5e+05]
Presolve removed 2259040 rows and 1747598 columns (presolve time = 6s) ...
Presolve removed 3031981 rows and 2520539 columns (presolve time = 10s) ...
Presolve removed 3031981 rows and 2520539 columns (presolve time = 15s) ...
Presolve removed 3032701 rows and 2733612 columns (presolve time = 30s) ...
Presolve removed 3032701 rows and 2733612 columns (presolve time = 30s) ...
Presolve removed 3958047 rows and 2733929 columns (presolve time = 45s) ...
Presolve removed 3958047 rows and 2733929 columns
Presolve time: 47.75s
Presolved: 4981292 rows, 5135691 columns, 23513622 nonzeros
Elapsed ordering time = 9s
Elapsed ordering time = 455s
Ordering time: 494.56s

Barrier statistics:
 Dense cols : 4371
 Free vars  : 34542
 AA' NZ     : 7.893e+07
 Factor NZ  : 2.223e+09 (roughly 20.0 GB of memory)
 Factor Ops : 3.377e+13 (roughly 120 seconds per iteration)
 Threads    : 8

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   5.58224140e+15 -2.91957634e+11  1.29e+11 4.50e-13  1.31e+10   636s
   1   4.60302625e+15 -8.97426474e+11  1.10e+11 4.54e+03  1.15e+10   705s
   2   3.68581252e+15 -5.22390063e+12  9.02e+10 3.91e+03  9.81e+09   838s
   3   1.97824839e+15 -9.68938964e+12  5.28e+10 3.23e+03  6.94e+09   972s
   4   1.13987486e+15 -2.19081435e+13  3.07e+10 1.51e+03  3.89e+09  1114s
   5   2.88492803e+14 -2.09051729e+13  8.17e+09 3.08e+02  8.38e+08  1277s
   6   4.28557543e+13 -9.08247868e+12  1.41e+09 4.34e+01  9.71e+07  1418s
   7   1.73611675e+13 -4.71615765e+12  6.19e+08 1.30e+01  3.15e+07  1578s
   8   1.66976456e+12 -2.22015888e+12  8.88e+07 3.87e+00  4.38e+06  1719s
   9   1.64166702e+11 -1.02782054e+12  1.56e+07 1.51e+00  9.07e+05  1874s
  10   1.71110702e+10 -4.64744585e+11  3.44e+06 6.41e-01  2.53e+05  2024s
  11   6.07101168e+09 -1.65096566e+11  1.38e+06 2.27e-01  7.53e+04  2167s
  12   2.77081268e+09 -8.72131067e+10  7.03e+05 1.21e-01  3.64e+04  2330s
  13   1.24173477e+09 -4.89508188e+10  3.08e+05 6.82e-02  1.76e+04  2469s
  14   2.90074216e+08 -8.28066559e+09  4.86e+04 1.17e-02  2.12e+03  2650s
  15   1.01143953e+08 -1.16601604e+09  9.19e+03 1.73e-03  2.62e+02  2797s
  16   2.81088198e+07 -1.02248675e+08  1.67e+03 2.01e-04  2.29e+01  2962s
  17   7.68094902e+06 -1.69500163e+07  2.74e+02 2.58e-04  3.53e+00  3119s
  18   2.58496659e+06 -3.03824100e+06  4.09e+01 9.82e-05  6.84e-01  3289s
  19   1.00902006e+06 -8.54456131e+05  8.39e+00 4.24e-05  1.99e-01  3445s
  20   4.89255408e+05 -3.66089440e+05  2.28e+00 1.97e-05  8.44e-02  3606s
  21   2.47308340e+05 -1.42817607e+05  5.18e-02 1.16e-05  3.50e-02  3757s
  22   1.36983866e+05 -5.92116825e+04  2.13e-02 1.23e-05  1.58e-02  3903s
  23   8.29489251e+04 -3.44608397e+04  1.23e-02 7.69e-06  8.90e-03  4060s
  24   5.10003628e+04 -2.01981457e+04  7.23e-03 5.68e-06  5.19e-03  4180s
  25   3.89748912e+04 -1.41558453e+04  5.44e-03 5.24e-06  3.83e-03  4320s
  26   3.32466849e+04 -1.20009982e+04  4.62e-03 5.40e-06  3.30e-03  4504s
  27   2.97921878e+04 -1.05690478e+04  4.11e-03 6.25e-06  2.98e-03  4654s
  28   2.54272325e+04 -9.11874745e+03  3.44e-03 6.84e-06  2.57e-03  4833s
  29   2.28283130e+04 -6.98243918e+03  3.04e-03 7.58e-06  2.19e-03  4969s
  30   1.56796346e+04 -4.79248043e+03  1.89e-03 7.51e-06  1.47e-03  5141s
  31   8.31210046e+03 -2.96527945e+03  7.53e-04 7.56e-06  8.29e-04  5303s
  32   7.53415568e+03 -2.55103723e+03  6.55e-04 6.41e-06  7.37e-04  5451s
  33   6.74540857e+03 -2.18678399e+03  5.28e-04 6.07e-06  6.61e-04  5604s
  34   5.66999782e+03 -1.77879564e+03  3.46e-04 5.68e-06  5.57e-04  5788s
...
 172   3.94836648e+02  3.92661988e+02  1.81e-08 4.85e-07  1.07e-07  29335s
 173   3.94798471e+02  3.92607440e+02  1.80e-08 4.81e-07  1.06e-07  29501s
 174   3.94729083e+02  3.92545096e+02  1.78e-08 4.76e-07  1.05e-07  29681s
 175   3.94645507e+02  3.92471204e+02  1.76e-08 4.70e-07  1.03e-07  29867s

Barrier performed 175 iterations in 29866.92 seconds (34200.51 work units)
Sub-optimal termination - objective 3.98509567e+02

 

 

 

 

 

0

Comments

2 comments

Date Votes
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi,

    You might want to try the following parameters too:

    Refer to the Presolve section in the numerical guidelines for more details on how presolve can exacerbate numerical issues.

    Experimenting with different values of the BarOrder parameter is also worth trying.

    Given that your model has 32M nonzeros, the simplex algorithm might be slower than the barrier method, but it could help with numerics.

    Check the section "Making the algorithms less sensitive" in the numerical guidelines for parameters that can help different types of optimization models with numerical challenges.

    Best regards,

    Maliheh

    0
  • Philipp Dunkel
    First Comment
    First Question
    Gurobi-versary

    Dear Maliheh,

    thank you very much for your suggestions.

    I tried using the ScaleFlag parameter with different values first and had great success with it! With this set to 1 none of my runs had any of described issues anymore.

    Nevertheless, I will also try your other suggestions.

    Thank you,

    Philipp

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post