barrier and crossover restart

I'm trying to solve an energy system model with ~2*10^6 rows and columns and ~7*10^6 non-zeros (after presolve) with barrier and crossover on gurobi 8.1.1.. The problem seems to have a large numeric range:

Coefficient statistics:
      Matrix range [1e-08, 1e+05]
   Objective range [1e+00, 1e+00]
             range [5e+01, 2e+06]
         RHS range [3e-01, 4e+07]
Warning: Model contains large matrix coefficient range

The Gurobi log indicates that the barrier method is restarted after 156 iterations:

Objective                                  Residual
Iter   Primal             Dual             Primal     Dual       Compl      Time
  0    1.94025385e+14     -1.73667811e+15  8.90e+09   6.03e+02   3.97e+10    53s
...
156    8.89097638e+10     8.89019533e+10   7.90e-02   1.38e-07   1.52e+00   591s
157    1.94025385e+14     -1.73667811e+15  8.90e+09   6.03e+02   3.97e+10   596s

Q1: What causes the barrier method to restart?

Q2: And what is changed internally after the restart in order to succeed the second time?

In the same run, after the barrier method finishes successfully, crossover is started. First dual variables are pushed to their bounds. Also this phase needs to be restarted:

820785 DPushes remaining with DInf 0.0000000e+00 1585s
...
   690 DPushes remaining with DInf 0.0000000e+00 6351s
     0 DPushes remaining with DInf 2.2690080e-07 6354s
Restart crossover...
1859027 variables added to crossover basis 6359s
1984357 variables added to crossover basis 6360s
1996397 variables added to crossover basis 6365s
820785 DPushes remaining with DInf 0.0000000e+00 6370s

I have encountered tightening of the Markowitz tolerance before, but this does not seem to happen here. Thus again my question:

Q3: what causes the DPushes phase to restart? (it seems to have reached its goal at the time of restart)

Q4: and what is changed in the second run to ensure success?

Both issues are alleviate by scaling the problem in a way that reduces the numerical range of the matrix:

the barrier method no longer needs to be restarted
the DPushes phase is restarted immediately instead of after 4800s of DPushes and thus finishes faster:

257   3.62514692e+06  3.62513983e+06  2.55e-06 5.87e-08  1.15e-06  1097s
Barrier solved model in 257 iterations and 1097.03 seconds
Optimal objective 3.62514692e+06
Crossover log...
Restart crossover...
1870125 variables added to crossover basis 1101s

In order to improve my scaling (and make it work consistently for all models) I would like to understand the exact nature of the numerical problems that cause these algorithms to restart.

Q5: are there publications describing the barrier and crossover implementations in Gurobi? I only know about "Recovering an optimal LP basis from an interior point solution" by Bixby from 1993. Is this still relevant?

Thank you very much in advance!

Best,

Manuel

Coefficient statistics:
Matrix range [1e-08, 1e+05]
Objective range [1e+00, 1e+00]
range [5e+01, 2e+06]
RHS range [3e-01, 4e+07]
Warning: Model contains large matrix coefficient range

Official comment

Yuriy Zinchenko

Gurobi Staff

September 08, 2020 16:41

Hello Manuel:

The issues you are seeing with both barrier and crossover restarts are largely due to the poor numerics, think very large ranges of the coefficients, for starters, on the order of 10^13, as can be seen from the log

You may want to read through our guideline to numerical issues to get a better idea what typically work and what does not

https://www.gurobi.com/documentation/9.0/refman/num_grb_guidelines_for_num.html

Basically, when the barrier restarts (just as the crossover) we turn on more numerical "fail-safe" routines which in turn are more computationally expensive, but in some cases this does help to stabilize the computations. Barrier restarts when the algorithm gets off-track or stagnates, and likewise, for the crossover phase; for the latter, you can also see that there are some changes to the basis being introduced, as most likely the starting basis candidate is nearly singular.

As you mention, rescaling the model helps, and this is indeed the way to go.

Besides the above link, if you are curios about the crossover itself, the below is a cool paper to read that should tell you a bit more about how crossover works,

http://theory.stanford.edu/~megiddo/pdf/bases.pdf

Hope this helps.

Simranjit Kaur

December 06, 2024 00:42

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 why not try our AI Gurobot?.

Markus Groissböck

November 25, 2020 09:39

Dear Yuriy,

Thanks for your feedback.
I get the same warning and also wanted to know what to do to improve the situation.

My question is: What do you mean with "rescaling the model helps"?

Kind regards,
Markus

November 25, 2020 16:55

Hi Markus,

have you had a chance to review the guide to numerics

for example

https://www.gurobi.com/documentation/9.0/refman/num_advanced_user_scaling.html

November 26, 2020 15:03

Thanks for the hint and the links. Will do so.

Regards,
Markus

barrier and crossover restart

Comments

Didn't find what you were looking for?