Is it possible to incorporate the relational algebra technique into JuMP in the future to expedite model generation?

Specific Domains Optimization (Mathematical)
4

I tried their benchmark, with n = 2800, 92% of the time is spent on this line

    x_list = [
        (i, j, k, l, m)
        for (i, j, k) in IJK
        for (jj, kk, l) in JKL if jj == j && kk == k
        for (kkk, ll, m) in KLM if kkk == k && ll == l
    ]

which is not even using JuMP. Let n, m, l size of the arrays IJK, JKL and KLM.
The complexity of this algorithm is O(n * m * l). It actually possible to do reduce the complexity considerably by doing.
In complexity O(n + m), you can merge the first two with something like

jk_i = Dict{Tuple{String,String},Vector{String}}()
for (i, j, k) in IJK
    if !haskey(jk_i, (j, k))
        jk_i[(j, k)] = String[]
    end
    push!(jk_i(j, k)], i)
end
IJKL = NTuple{4, Int}[]
for (j, k, l) in jkl
    for i in jk_i[(j, k)]
        push!(IJKL, (i, j, k, l))
    end
end

Suppose the length of the resulting array IJKL is o, the complexity of this algorithm is O(n + m + o). You can then merge IJKL with KLM with a complexity of O(o + l + p) where p is the length of the final array in a similar fashion.
So the final complexity is O(m + n + l + o + p) which is much smaller than O(m * n * l) !
So if I’m not mistaken, the benchmark is showing that the algorithm of complexity O(m * n * l) is inefficient (I assume the Python and GAMS version use a better algorithm), this has nothing to do with JuMP.

4 Likes