Performance issue with L-Shaped when using Gurobi in subproblems

[maramos874]

Hi, I was investigating why L-Shaped was not performing well and tracked the problem to subproblem generation with Gurobi. Linear subproblems are solved in less than 1/10 of second, and the master is solved in less than 10 seconds. Nevertheless, the overhead time between those two solves is overwhelming. Thus, I tried changing the subproblem solver to GLPK and to my surprise there was almost no overhead between solving the master and the subproblems. Please don't hesitate to tell me what can I provide you to track the issue.

Kind regards

[martinbiel]

Performance is very problem dependent. I cannot say if there is a problem here without access to the model.

[maramos874]

I understand, does an MPS file could work for you? This message is also thrown by Gurobi in each subproblem:

Warning: excessive time spent in model updates. Consider calling update less frequently.

[martinbiel]

What are your problem dimensions and how many iterations do you end up with?

[maramos874]

Warning: excessive time spent in model updates. Consider calling update less frequently.
Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
Optimize a model with 47872 rows, 96228 columns and 112112 nonzeros
Model fingerprint: 0xcdd977a5
Coefficient statistics:
  Matrix range     [5e-01, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [2e+00, 2e+00]
  RHS range        [8e-04, 3e+01]

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 47872 rows and 96228 columns
Presolve time: 0.06s
Presolve: All rows and columns removed
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    1.3702252e+04   0.000000e+00   0.000000e+00      0s

Solved with barrier
Solved in 0 iterations and 0.13 seconds
Optimal objective  1.370225186e+04

The overhead time is just after each master solve.

[martinbiel]

If you send me the problem I can look into it when I have time.

[maramos874]

I'll send it next week then. Thanks! Regarding the warning message, could it be related to this? (Gurobi.jl reference)

Common Performance Pitfall with JuMP
Gurobi's API works differently than most solvers. Any changes to the model are not applied immediately, but instead go sit in a internal buffer (making any modifications appear to be instantaneous) waiting for a call to GRBupdatemodel (where the work is done).

This leads to a common performance pitfall that has the following message as its main symptom:

Warning: excessive time spent in model updates. Consider calling update less
frequently.
This often means the JuMP program was structured in such a way that Gurobi.jl ends up calling GRBupdatemodel each iteration of a loop. Usually, it is possible (and easy) to restructure the JuMP program in a way it stays solver-agnostic and has a close-to-ideal performance with Gurobi.

To guide such restructuring it is good to keep in mind the following bits of information:

GRBupdatemodel is only called if changes were done since last GRBupdatemodel (i.e., the internal buffer is not empty).
GRBupdatemodel is called when JuMP.optimize! is called, but this often is not the source of the problem.
GRBupdatemodel may be called when ANY model attribute is queried even if that specific attribute was not changed, and this often the source of the problem.
The worst-case scenario is, therefore, a loop of modify-query-modify-query, even if what is being modified and what is being queried are two completely distinct things.
As an example, prefer:

# GOOD
model = Model(Gurobi.Optimizer)
@variable(model, x[1:100] >= 0)
# All modifications are done before any queries.
for i = 1:100
    set_upper_bound(x[i], i)
end
for i = 1:100
    # Only the first `lower_bound` query may trigger an `GRBupdatemodel`.
    println(lower_bound(x[i]))
end
to:

# BAD
model = Model(Gurobi.Optimizer)
@variable(model, x[1:100] >= 0)
for i = 1:100
    set_upper_bound(x[i], i)
    # `GRBupdatemodel` called on each iteration of this loop.
    println(lower_bound(x[i]))
end

[martinbiel]

Yes most likely, but it is not entirely clear to me why that would happen when solving the master. I will think about it.

[maramos874]

It appears to happen rather when assembling the subproblems and/or querying duals, since when solving the master with Gurobi and the subproblems with GLPK, performance is way better than when solving both master and subproblems with Gurobi

[martinbiel]

How many constraints are there in the subproblems?

[maramos874]

Short less than 100000

[martinbiel]

Eventually, updating all first-stage decision values in every subproblem will become a bottle-neck when you increase the number of second-stage constraints. It could possibly be improved by switching to using fixed variables when the number of constraints is large, but I am not sure how much it will help and I will need some time to implement and test it.

[martinbiel]

This has been addressed on the master branch according to the above suggestion. I can at least see improvements on my problems. I do not have any further major design suggestions for dealing with large subproblems at the moment, save for further decomposition, so I will close this for now. Thanks for bringing it up!