Warning: excessive time spent in model updates. when using read_from_file

[mipals]

I am currently using “read_from_file” to load a model from a cbf file. Unfortunately this approach seems to hit the “Warning: excessive time spent in model updates. Consider calling update less frequently.” pitfall mentioned in the readme. However, as I am not reading in the model myself I cannot apply possible fixes mentioned in the readme. Any ideas as to how to fix the issue?

[odow]

Can you share the cbf file and a reproducible code example of how you are calling it?

(Somewhat relatedly, what read a CBF file with Gurobi?)

[odow]

I guess the answer is: https://cblib.zib.de/download/all/

julia> m = read_from_file("chainsing-10000-1.cbf.gz");

julia> set_optimizer(m, Gurobi.Optimizer)

julia> optimize!(m)
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (mac64[x86] - Darwin 22.6.0 22G630)

CPU model: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads


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

Optimize a model with 99982 rows, 129976 columns and 239954 nonzeros
Model fingerprint: 0x2b705791
Model has 29994 quadratic constraints
Coefficient statistics:
  Matrix range     [7e-01, 1e+01]
  QMatrix range    [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e-01, 1e+00]
Presolve removed 39994 rows and 29994 columns
Presolve time: 0.22s
Presolved: 59988 rows, 99982 columns, 149970 nonzeros
Presolved model has 29994 second-order cone constraints
Ordering time: 0.02s

Barrier statistics:
 Free vars  : 5000
 AA' NZ     : 1.050e+05
 Factor NZ  : 5.099e+05 (roughly 70 MB of memory)
 Factor Ops : 5.050e+06 (less than 1 second per iteration)
 Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   4.68074155e+03 -4.99906250e+02  5.75e-01 1.00e-01  6.51e-02     0s
   1   4.69921548e+02 -7.73573774e+01  5.20e-02 1.10e-07  5.94e-03     0s
   2   3.45522818e+02  1.24176198e+02  3.19e-02 2.38e-08  2.92e-03     0s
   3   3.10078553e+02  2.70868745e+02  9.86e-03 1.72e-08  9.21e-04     1s
   4   3.01833318e+02  2.95055320e+02  1.61e-03 3.52e-09  1.69e-04     1s
   5   3.01590650e+02  3.00694119e+02  4.02e-04 2.53e-09  3.57e-05     1s
   6   3.02341676e+02  3.02337977e+02  7.32e-05 6.81e-10  5.03e-06     1s
   7   3.02588566e+02  3.02594472e+02  8.53e-06 1.78e-10  5.31e-07     1s
   8   3.02606087e+02  3.02608990e+02  1.46e-06 1.54e-11  7.19e-08     1s
   9   3.02610526e+02  3.02610336e+02  9.25e-08 7.79e-12  8.32e-09     1s

Barrier solved model in 9 iterations and 0.88 seconds (0.42 work units)
Optimal objective 3.02610526e+02


User-callback calls 161, time in user-callback 0.00 sec

Part of the problem is:

julia> m
A JuMP Model
Minimization problem with:
Variables: 129976
Objective function type: AffExpr
`Vector{VariableRef}`-in-`MathOptInterface.RotatedSecondOrderCone`: 29994 constraints
`Vector{AffExpr}`-in-`MathOptInterface.Zeros`: 1 constraint
`Vector{AffExpr}`-in-`MathOptInterface.Nonnegatives`: 5000 constraints
`Vector{AffExpr}`-in-`MathOptInterface.Nonpositives`: 5000 constraints
Model mode: AUTOMATIC
CachingOptimizer state: ATTACHED_OPTIMIZER
Solver name: Gurobi

CBF is a conic format, so we bridge everything.

We don't really have a fast mechanism for reading CBF models like this into a solver like Gurobi.

[mipals]

Ahh okay. Do you know if the bridging is due to Gurobi not directly supporting cones or if it is due to some missing implementation?

Anyway, I guess I will have to stick with MOSEK and Clarabel for now then.

[blegat]

Why would the bridges trigger to many model updates ? Because it doesn't go through copy_to ? Then I guess this is a workaround ?

set_optimizer(m, () -> MOI.instantiate(Gurobi.Optimizer, with_cache_type = Float64))

[odow]

I'm guessing because the second-order cones need to check for RHS.

[odow]

It's the _get_variable_lower_bound:

Gurobi.jl/src/MOI_wrapper/MOI_wrapper.jl

Lines 4281 to 4305 in 4112950

	function MOI.add_constraint(
	model::Optimizer,
	f::MOI.VectorOfVariables,
	s::MOI.SecondOrderCone,
	)
	if length(f.variables) != s.dimension
	error("Dimension of $(s) does not match number of terms in $(f)")
	end
	# SOC is the cone: t ≥ ||x||₂ ≥ 0. In quadratic form, this is
	# t² - Σᵢ xᵢ² ≥ 0 and t ≥ 0.
	# First, check the lower bound on t.
	t_info = _info(model, f.variables[1])
	lb = _get_variable_lower_bound(model, t_info)
	if isnan(t_info.lower_bound_if_soc) && lb < 0.0
	# If `t_info.lower_bound_if_bounded` is active, this just makes
	# `t_info.lower_bound_if_soc` equal to it. If `lower_bound_if_bounded`
	# is set after, then it will call `_set_variable_lower_bound` and
	# update `lower_bound_if_soc` accordingly.
	t_info.lower_bound_if_soc = lb
	ret = GRBsetdblattrelement(model, "LB", Cint(t_info.column - 1), 0.0)
	_check_ret(model, ret)
	end
	t_info.num_soc_constraints += 1

I guess we could cache the lower bound for every variable.

[odow]

But I think supporting SecondOrderCone in Gurobi.jl was a mistake. It doesn't support it.

[odow]

@mipals

Do you know if the bridging is due to Gurobi not directly supporting cones

It's because Gurobi does not support cones.

[mipals]

The work-around sort of works @blegat . It speed things up significantly, but the convergence of the problem changes slightly (one of my problems went from 54 barrier iterations to 71 - But from 60s to 7s total time).

@odow I believe I got confused due to a post on the Gurobi support forum which seem to explicitly mention SOCs as possible constraints https://support.gurobi.com/hc/en-us/articles/360013156432-What-types-of-models-can-Gurobi-solve . But I guess in reality Gurobi just handles them as a specific type of quadratic constraints and JuMP therefore has to do this conversion that is slow?

[odow]

But I guess in reality Gurobi just handles them as a specific type of quadratic constraints and JuMP therefore has to do this conversion that is slow?

Correct. Made slightly complicated by some internals of how JuMP goes from x in QR to the quadratic constraint in Gurobi. But also because of Gurobi's update mechanism, where we need to "update" the model after each quadratic constraint is added.

We could potentially improve this, but Gurobi likely won't be competitive with Mosek.