Column generation

[dourouc05]

For now, if you want to use column generation, the common advice seems to be staying on JuMP 0.18. I will need this feature in the near future, and I'm not willing to go back to an old JuMP.

In MOI, everything seems plumbed (https://github.com/JuliaOpt/MathOptInterface.jl/blob/master/docs/src/apimanual.md#column-generation). If I'm not mistaken, what would be required in JuMP? The old interface was just inside @variable (https://github.com/JuliaOpt/JuMP.jl/blob/v0.18.6/doc/probmod.rst):

@variable(m, 0 <= z <= 1, objective = 10, inconstraints = [con], coefficients = [1.0])

Would there be any problem to carry over this notation? Maybe inconstraints and coefficients could be merged in a dictionary, so that the generation of the coefficients would be simpler (you would have dict[constraint] = coeff instead of updating two lists: push!(ls, constraint) and push!(lc, coeff)).

Is there any design considerations before I sketch something? I could not find anything in this repository or on Discourse.

[odow]

Without meaning to speak for the others, I don't think anyone has invested much time into thinking about what a nice column-generation syntax would look like at the JuMP level. If you want to sketch some ideas, that would be great. No need to stick to the old syntax if you can think of something better. It would be nice to be able to add a column, then set the coefficients, as well as add a column with coefficients.

[mlubin]

From the docs you pointed to,

If the solver has a special API for setting coefficients in existing constraints when adding a new variable, it is possible to queue modifications and new variables and then call the solver's API once all of the new coefficients are known.

I believe that no solver interfaces currently implement this "modification queuing" approach, so column generation goes through the same pathway as coefficient modifications. We haven't done benchmarks to verify that this is a reasonable thing to do.

But anyway you can already do the following:

@variable(model, 0 <= z <= 1)
set_objective_function(model, objective_function(model) + 10z) # This probably should be replaced with set_objective_coefficient.
set_coefficient(con, z, 1.0)

I would prefer to not add extra bells and whistles to the macros when functions work instead.

[dourouc05]

This makes me think: the objective might be quadratic (I guess that, if the objective is a convex function, it should be represented by a simple variable in the objective and at least one conic constraint?).

So, your opinion is: column generation is sufficiently implemented right now in MOI/JuMP (except for something like set_objective_coefficient), we need more performance numbers to see if anything else is required (in which case it would be best to leave the largest part of the burden on the solver implementation)? That seems reasonable to me.

(Pyomo seems to do something very similar, when I look at the code many people use in my team -- I could not find a "standard" way of doing column generation in Pyomo.)

[mlubin]

column generation is sufficiently implemented right now in MOI/JuMP (except for something like set_objective_coefficient), we need more performance numbers to see if anything else is required (in which case it would be best to leave the largest part of the burden on the solver implementation)?

Yes. The solution could be as simple as implementing set_objective_coefficient and then adding a section in the documentation on how to do column generation based on the example above. If there are strong performance reasons to do something more complex, then we'll have to revisit this.

[mlubin]

the objective might be quadratic

AFAIK solvers don't have any special interface for adding variables and setting quadratic objective coefficients at the same time, so this would be processed as a regular modification.

[dourouc05]

Maybe the guys from Coluna would have something to say here? @FD-V @guimarqu

[mtanneau]

@dourouc05, my experience with doing column-generation is the following:

If you're using MOI, use the MOI.add_variable followed by MOI.modify to set the coefficients (for the constraints). Looks like this:

# Add the column
vidx = MOI.add_variable(model)
MOI.add_constraint(model, MOI.SingleVariable(vidx), MOI.GreaterThan(0.0))

# Set column Coefficients
# `col` is a sparse vector
for (i, v) in zip(col.nzind, col.nzval)
    MOI.modify(model, constr[i], MOI.ScalarCoefficientChange(vidx, v))
end

where model is the MOI model, constr is a vector of indices of all the constraints in m, and col is a sparse vector (of the right dimension) that contains the column to be added.
To make changes in the objective, you should be able to do something similar, see the docs here. MOI.modify works for ScalarAffine and ScalarQuadratic functions, so you should be in the clear.

In terms of pure performance, it's probably not optimal, but I haven't had to complain so far.
I would advice against using MultirowChange because of this

If you're using JuMP, I'd say Miles' solution is the most practical.

[guimarqu]

Thanks for mentioning us.

About the modeling language, Coluna uses BlockDecomposition which is a package built on top of JuMP. BlockDecomposition annotates each variable and constraint to indicate whether it is in the master or subproblems.

The user writes the compact formulation, describes the decomposition with BlockDecomposition, and then Coluna reformulates the problem using BlockDecomposition annotations.
We want that the user does not worry about how to handle variables like z. It is automatically done by Coluna.

Coluna has data structures to store its formulations, it interacts with MOI to update formulations when master or subproblems are solved with LP/MIP solvers.

If the user wants to model the problem with explicit column generation, I think it will be best that JuMP provides a callback like what was done for cut generation.

[mlubin]

Addressed by #2010, until we have evidence that this approach isn't efficient enough.