Performance issue with large number of variables

[parkyr]

Execution time is long for large number of variables in converting to ToQUBO models.
The JuMP model:

A JuMP Model
├ solver: none
├ objective_sense: MIN_SENSE
│ └ objective_function_type: QuadExpr
├ num_variables: 528
├ num_constraints: 2144
│ ├ AffExpr in MOI.EqualTo{Float64}: 32
│ ├ AffExpr in MOI.LessThan{Float64}: 528
│ ├ VariableRef in MOI.GreaterThan{Float64}: 528
│ ├ VariableRef in MOI.LessThan{Float64}: 528
│ └ VariableRef in MOI.Integer: 528
└ Names registered in the model
  └ :x, :y

The code:

function convert_to_qubo(config!::Function, m::JuMP.Model; optimizer=ToQUBO.Optimizer(nothing)) 

    # Convert the JuMP model to a QUBO model
    set_optimizer(
        m,
        () -> optimizer
    )

    config!(m)

    optimize!(m)

    return m
end

qubo_model = convert_to_qubo(identity, model)
qubo_model1 = unsafe_backend(qubo_model).target_model
qt_model = unsafe_backend(qubo_model).target_model |> QUBOTools.Model

"model" is the JuMP model as described above.

"qubo_model1" looks like this:

ToQUBO.QUBOModel{Float64}
├ ObjectiveSense: MIN_SENSE
├ ObjectiveFunctionType: MOI.ScalarQuadraticFunction{Float64}
├ NumberOfVariables: 9941
└ NumberOfConstraints: 0
  └ MOI.VariableIndex in MOI.ZeroOne: 0

Last line takes a long time, see interrupted error message:

InterruptException:

Stacktrace:
  [1] _growat!(a::Vector{Float64}, i::Int64, delta::Int64)
    @ Base ./array.jl:1140
  [2] insert!
    @ ./array.jl:1746 [inlined]
  [3] _insert!
    @ ~/.julia/juliaup/julia-1.11.5+0.x64.linux.gnu/share/julia/stdlib/v1.11/SparseArrays/src/sparsematrix.jl:3218 [inlined]
  [4] _setindex_scalar!(A::SparseMatrixCSC{Float64, Int64}, _v::Float64, _i::Int64, _j::Int64)
    @ SparseArrays ~/.julia/juliaup/julia-1.11.5+0.x64.linux.gnu/share/julia/stdlib/v1.11/SparseArrays/src/sparsematrix.jl:3207
  [5] setindex!
    @ ~/.julia/juliaup/julia-1.11.5+0.x64.linux.gnu/share/julia/stdlib/v1.11/SparseArrays/src/sparsematrix.jl:3180 [inlined]
  [6] (QUBOTools.Model{MathOptInterface.VariableIndex, Float64, Int64, F} where F<:QUBOTools.AbstractForm{Float64})(variable_set::Set{MathOptInterface.VariableIndex}, linear_terms::Dict{MathOptInterface.VariableIndex, Float64}, quadratic_terms::Dict{Tuple{MathOptInterface.VariableIndex, MathOptInterface.VariableIndex}, Float64}; scale::Float64, offset::Float64, sense::QUBOTools.Sense, domain::Symbol, kws::@Kwargs{})
    @ QUBOTools ~/.julia/packages/QUBOTools/70p3F/src/library/model/model.jl:156
  [7] Model
    @ ~/.julia/packages/QUBOTools/70p3F/src/library/model/model.jl:126 [inlined]
  [8] (QUBOTools.Model{MathOptInterface.VariableIndex, Float64, Int64, F} where F<:QUBOTools.AbstractForm{Float64})(linear_terms::Dict{MathOptInterface.VariableIndex, Float64}, quadratic_terms::Dict{Tuple{MathOptInterface.VariableIndex, MathOptInterface.VariableIndex}, Float64}; scale::Float64, offset::Float64, kws::@Kwargs{sense::QUBOTools.Sense, domain::Symbol})
    @ QUBOTools ~/.julia/packages/QUBOTools/70p3F/src/library/model/model.jl:123
  [9] Model
    @ ~/.julia/packages/QUBOTools/70p3F/src/library/model/model.jl:109 [inlined]
 [10] _extract_bool_model(::Type{Float64}, model::ToQUBO.QUBOModel{Float64}, Ω::Set{MathOptInterface.VariableIndex})
    @ QUBOTools_MOI ~/.julia/packages/QUBOTools/70p3F/ext/QUBOTools_MOI/model_parser.jl:144
 [11] _parse_moi_model(::Type{Float64}, model::ToQUBO.QUBOModel{Float64})
    @ QUBOTools_MOI ~/.julia/packages/QUBOTools/70p3F/ext/QUBOTools_MOI/model_parser.jl:82
 [12] Model
    @ ~/.julia/packages/QUBOTools/70p3F/ext/QUBOTools_MOI/model_parser.jl:6 [inlined]
 [13] Model
    @ ~/.julia/packages/QUBOTools/70p3F/ext/QUBOTools_MOI/model_parser.jl:2 [inlined]
 [14] |>(x::ToQUBO.QUBOModel{Float64}, f::Type{QUBOTools.Model})
    @ Base ./operators.jl:926
 [15] top-level scope
    @ ~/repos/qubo/QUIO_Dell/jl_notebook_cell_df34fa98e69747e1a8f8a730347b8e2f_X36sdnNjb2RlLXJlbW90ZQ==.jl:1

[parkyr]

function to_qubo_form(varmap::Function, n::Integer, f::MOI.ScalarQuadraticFunction{T}, sense) where {T}
    L = spzeros(T, n)
    Q = spzeros(T, n, n)
    a = one(T)
    b = zero(T) + f.constant

    for t in f.affine_terms
        j = varmap(t.variable)
        c = t.coefficient

        L[j] += c
    end

    for t in f.quadratic_terms
        j = varmap(t.variable_1)
        k = varmap(t.variable_2)
        c = t.coefficient

        if j == k
            @error("PLS NO!")
            L[j] += c/2
        else
            Q[j, k] += c
        end
    end

    return QUBOTools.Form{T}(
        n,
        QUBOTools.SparseLinearForm{T}(L),
        QUBOTools.SparseQuadraticForm{T}(Q),
        a,
        b;
        sense  = sense,
        domain = :bool,
    )
end

function to_qubo_form(model::MOI.ModelLike)
    F = MOI.get(model, MOI.ObjectiveFunctionType())
    f = MOI.get(model, MOI.ObjectiveFunction{F}())
    n = MOI.get(model, MOI.NumberOfVariables())

    sense = MOI.get(model, MOI.ObjectiveSense()) === MOI.MIN_SENSE ? :min : :max

    return to_qubo_form(vi -> (@assert 1 <= vi.value <= n; vi.value), n, f, sense)
end

to_qubo_form(model::JuMP.Model) = to_qubo_form(unsafe_backend(model).target_model)

function to_qubotools_model(model, V = MOI.VariableIndex, T = Float64, U = Int, F = QUBOTools.SparseForm{T})
    form         = to_qubo_form(model)
    n            = form.n
    variable_map = QUBOTools.VariableMap{V}(V.(1:n))
    metadata     = Dict{String,Any}()
    solution     = QUBOTools.SampleSet{T,U}()
    start        = Dict{Int,U}()

    return QUBOTools.Model{V,T,U,F}(
        variable_map,
        form,
        metadata,
        solution,
        start,
    )
end

[parkyr]

Revisions made to accelerate:

function to_qubo_form(varmap::Function, n::Integer, f::MOI.ScalarQuadraticFunction{T}, sense) where {T}
    L = zeros(T, n)
    Q = zeros(T, n, n)
    a = one(T)
    b = zero(T) + f.constant

    # sizehint!(L, length(f.affine_terms))
    # sizehint!(Q, length(f.quadratic_terms))

    for t in f.affine_terms
        j = varmap(t.variable)
        c = t.coefficient

        L[j] += c
    end

    for t in f.quadratic_terms
        j = varmap(t.variable_1)
        k = varmap(t.variable_2)
        c = t.coefficient

        if j == k
            @error("PLS NO!")
            L[j] += c/2
        else
            Q[j, k] += c
        end
    end

    return QUBOTools.Form{T}(
        n,
        QUBOTools.SparseLinearForm{T}(sparse(L)),
        QUBOTools.SparseQuadraticForm{T}(sparse(Q)),
        a,
        b;
        sense  = sense,
        domain = :bool,
    )
end