What is the best way to introduce multiple variables in column generation scheme?

Specific Domains Optimization (Mathematical)
1

Hello!

I was wondering what is the optimal way to introduce a group of new variables into an existing variable container, and then update their values in the objective function. My main concern is that my current implementation is not vectorized, so I’d imagine it leaves some performance gains on the table, but I can’t find a way to introduce them all at once

The function I’m working with is below:

function updateModel!(SP::SPFormulation, newColumns::Vector{RouteInfo})
    println("======== Updating model =========")
    varCount = length(SP.model[:λ])
    for (i, column) in enumerate(newColumns)
        push!(SP.model[:λ], @variable(SP.model, base_name="λ[$(varCount + i)]", lower_bound=0))
        set_objective_coefficient(SP.model, SP.model[:λ][varCount + i], column.cost)
        for node in column.route
            if node == 1
                set_normalized_coefficient(SP.model[:depot], SP.model[:λ][varCount + i], 1)
            else
                set_normalized_coefficient(SP.model[:con][node], SP.model[:λ][varCount + i], 1)
            end
        end
    end
end
1 Like
2

Hi @lucasximenes, welcome to the forum!

What you have is the suggested approach.

Have you benchmarked it and found that adding the columns is a bottleneck?

My main concern is that my current implementation is not vectorized, so I’d imagine it leaves some performance gains on the table

Julia is not Python. You don’t really need to worry about vectorization.

3

Thank you for the quick answer, Oscar! I haven’t set up a proper benchmark to see if this model update is in fact problematic, but I wanted to be sure that the implementation was correct.

1 Like
4

I wanted to be sure that the implementation was correct

It looks like you have a good handle on things.

It’s a matter of style (should have minimal performance difference), but I might write your function like this:

function update_model(SP::SPFormulation, new_columns::Vector{RouteInfo})
    println("======== Updating model =========")
    λ, depot, con = SP.model[:λ], SP.model[:depot], SP.model[:con]
    i = length(λ)
    for column in new_columns
        i += 1
        push!(λ, @variable(SP.model, base_name = "λ[$i]", lower_bound = 0))
        set_objective_coefficient(SP.model, λ[end], column.cost)
        for node in column.route
            set_normalized_coefficient(node == 1 ? depot : con[node], λ[end], 1)
        end
    end
    return
end