Improve performance of adding variables with bounds

[joaquimg]

From this simple example:

using JuMP
using HiGHS

using Profile
using PProf

function add_var()
    model = direct_model(HiGHS.Optimizer())
    @variable(model, 1 <= x[i in 1:10000] <= 2)
    return nothing
end

add_var()

Profile.clear()
@profile add_var()

pprof()

we get:

So, almost 2/3 of the time is spent on adding the bounds.

But, similar to many other solvers, HiGHS would be able to do both in a single call: Highs_addCol(model, 0.0, -Inf, Inf, 0, C_NULL, C_NULL)

One idea would be:

Create the function(s): MOI.Utilities.add_variable(s)_and_bounds_constraints The fallback would be add_variable(s) + add_constraint(s) But solvers could choose to implement this function, and JuMP would always use it (which would work, thanks to the fallback).

[guilhermebodin]

One of the problems related to this is that we should be able to query the bounds separately afterward and possibly we would like to query duals related to one of the bounds.

There is some discussion about this on this issue https://github.com/jump-dev/JuMP.jl/issues/3023

[odow]

So, almost 2/3 of the time is spent on adding the bounds.

I would expect this, since there are three things we need to do: add a variable, add a lower bound, add an upper bound.

Note that if you use Model(HiGHS.Optimizer), then we will do an efficient copy_to operation.

Do you have a real-world example where this operation is a performance problem?

[odow]

It seems like we could also make a more efficient method in HiGHS' C API to modify a single bound, instead of the iterator that they currently do. (We shouldn't need malloc and free to modify a bound.)

[joaquimg]

Yes, I do have a real example. The code is not public, though.

The model build time is dominated by add_variable (most of the adds in the last line in the graph). There are many variables (more than constraints), all of which have both upper and lower bounds.

[joaquimg]

Note that if you use Model(HiGHS.Optimizer), then we will do an efficient copy_to operation.

copy_to is not an option as it would lead to an even slower and more memory-demanding model build step.

[odow]

I think this is asking for a more efficient method in the C API, not JuMP

[odow]

The model build time is dominated by add_variable (most of the adds in the last line in the graph)

Okay... but how much time does this actually take

[joaquimg]

Okay... but how much time does this actually take

21% of the total running time (which includes loading data, building models, updating models, LP solving models)

[odow]

And how long in wall time is that?

[joaquimg]

Depends on the problem size... larger problems run for 10 hours, so 2 hours just adding variables. The example I posted runs for 100s so 20s of adding variables.

[odow]

This should be fixed in HiGHS then. There's no way that this overhead is because of JuMP.

[joaquimg]

I implemented it locally: HiGHS:

function MOI.Utilities.add_variable_and_bounds(
    model::Optimizer,
    lower_bound,
    upper_bound,
)
    # Initialize `_VariableInfo` with a dummy `VariableIndex` and a column,
    # because we need `add_item` to tell us what the `VariableIndex` is.
    index = CleverDicts.add_item(
        model.variable_info,
        _VariableInfo(MOI.VariableIndex(0), HighsInt(0)),
    )
    info = _info(model, index)
    lb = -Inf
    if lower_bound !== nothing
        lb = lower_bound
        _update_info(info, MOI.GreaterThan{Float64}(lb))
    end
    ub = Inf
    if upper_bound !== nothing
        ub = upper_bound
        _update_info(info, MOI.LessThan{Float64}(ub))
    end
    # Now, set `.index` and `.column`.
    info.index = index
    info.column = HighsInt(length(model.variable_info) - 1)
    ret = Highs_addCol(model, 0.0, lb, ub, 0, C_NULL, C_NULL)
    _check_ret(ret)
    return index
end

MOI:

function add_variable_and_bounds(
    model::MOI.ModelLike,
    lower_bound,
    upper_bound,
)
    v = MOI.add_variable(model)
    if lower_bound !== nothing
        MOI.add_constraint(model, v, MOI.GreaterThan(lower_bound))
    end
    if upper_bound !== nothing
        MOI.add_constraint(model, v, MOI.LessThan(upper_bound))
    end
    return v
end

JuMP:

function _moi_add_variable(
    moi_backend,
    model::GenericModel{T},
    v::ScalarVariable,
    name::String,
) where {T}
    lower_bound = v.info.has_lb ? v.info.lower_bound : nothing
    upper_bound = v.info.has_ub ? v.info.upper_bound : nothing
    index = MOI.Utilities.add_variable_and_bounds(moi_backend, lower_bound, upper_bound)
    var_ref = GenericVariableRef(model, index)
    _moi_constrain_variable(moi_backend, index, v.info, T, add_bounds = false)
    if !isempty(name) &&
       MOI.supports(moi_backend, MOI.VariableName(), MOI.VariableIndex)
        set_name(var_ref, name)
    end
    return var_ref
end
function _moi_constrain_variable(
    moi_backend::MOI.ModelLike,
    index,
    info,
    ::Type{T};
    add_bounds = true,
) where {T}
    # We don't call the _moi* versions (for example, _moi_set_lower_bound)
    # because they have extra checks that are not necessary for newly created
    # variables.
    if add_bounds
        if info.has_lb
            _moi_add_constraint(
                moi_backend,
                index,
                MOI.GreaterThan{T}(_to_value(T, info.lower_bound, "lower bound")),
            )
        end
        if info.has_ub
            _moi_add_constraint(
                moi_backend,
                index,
                MOI.LessThan{T}(_to_value(T, info.upper_bound, "upper bound")),
            )
        end
    end
    ...

The amount of change is really small, and for the example (in the OP) above it gets us to:

which is a 3x

[joaquimg]

I don't disagree HiGHS could do it better.

But, this is an issue in Xpress as well. I think JuMP is unnecessarily doing it in a different way from both these solvers.

[joaquimg]

I opened 3 PRs to clarify: https://github.com/jump-dev/MathOptInterface.jl/pull/2565 https://github.com/jump-dev/JuMP.jl/pull/3862 https://github.com/jump-dev/HiGHS.jl/pull/244

Does not look like a big change, code itself is less than 100 lines summing all 3 PRs

[blegat]

What's the difference with MOI.add_constrained_variable(model, MOI.Interval(lower, upper)) ?

[odow]

Closed by #2574