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:
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:
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
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
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!
Please sign in to leave a comment.