Jump.jl: Proposal: parameters/constants in linear models

[joaquimg]

I think it would be useful if linear models had special Parameters similar to the ones we currently have in Non-Linear models.

I would start using them as Parametric RHS constants to solve decompositions, where

the slave is:

m_slave = Model()

@constant(m_slave, x[1:n] == ctes)
@variable(m_slave, y[1:m])

@constraint(m_slave, D*y = d - B*x)

@objective(m_slave, dot(f,y))

solve(m_slave)

pi = getdual(x)
p = getobjectivevalue(m_slave)

and the master is:

m_master = Model()

@variable(m_master, x[1:n] >= 0)
@variable(m_master, z)

@constraint(m_master, A*x >= b)

@constraint(m_master, z >= dot(pi,x) + p)

@objective(m_slave, dot(c,x) + z)

there are 2 important thing in @constant:
1 - once the change its (fixed) value, this change is reflected in the problem´s RHS
2 - duals are easily computed for x by applying the chain rule once we know its coefficients and constraints

Another possible use would be in the problem coefficients that appear more than once in the A matrix.
A Variable could have a mixed coefficient (Number+@constant)
In this case querying duals is not useful, but letting the user easily update the model is very helpful.

[mlubin]

As far as I'm concerned, the case of parametric RHS is adequately addressed by using fixed variables. We already have the syntax @variable(m_slave, x[i=1:n] == ctes[i]) and JuMP.fix. The LP solver will compute correct duals in this case. (They're passed as variables with lower and upper bounds equal.) There is possibly a bit of unnecessary overhead by adding a few extra variables in the LP solver, but I'd need to see benchmarks to be convinced that we're losing more than 10% in performance.

I'll address the "Another possible use" in a separate comment.

[joaquimg]

My first idea was to use fixed variables, they are good solutions for many cases with a small number of constants. However if the number of constants is large the extra variables might slow everything. I will try to come up with a simple benchmark for that.

[mlubin]

I can see the issue with using fixed variables in a way that forces you to include the B matrix in the problem data in the example above. You'd really want to fix the variables to the value of d - B*x and compute the dual of x manually.

[joaquimg]

Thats what I do with the current version of JuMP I fix the RHS to d - B*x, but then collecting the dual to x is a bit of a pain. And doing that manually increases the chances of errors. I saw this sort of generic pattern and began thinking how to abstract that, since it would be useful in many decomposition cases´and sensibility analisys. I could start that as a JuMP extension.

[joaquimg]

Also not using the fixed variables would have the extra variable reduction which is very useful for mid-sized problems where we turn presolve off.

[mlubin]

For the case of decomposition algorithms, you can also use https://github.com/StructJuMP/StructJuMP.jl for modeling, which makes it easy to collect D and B from the original model.

[blegat]

Doing it in a JuMP extension is a good idea.

[mlubin]

Regarding parameters that propagate arbitrarily, the previous discussion is at #669 and the conclusion hasn't changed. It requires a massive rewrite of JuMP and is out of scope for 1.0.

[joaquimg]

I made a sketch here: https://github.com/joaquimg/ParameterJuMP.jl
I am currently using the GenericAffExpr with a type that includes both a Variable and Parameter. A second option is to create a new ParameterGenericAffExpr type that has more fields.

[joehuchette]

Do you have any sense of the performance penalty you pay using this approach?

[joaquimg]

I just done some benchmarks for 'Fixed Variables' versus 'Parameters' in problem building.
In my test the number of common variables and parameters in a model is the same (say 1000 each) and there are many constraints (100) with all these variable and parameters.
Using my parameters make it 5x slower.

Almost 2/3 of this time is saving additional data and converting the GenericAffExpr{C,VariableOrParameter} into a GenericAffExpr with only variable and other with only constraints.

If I remove the above two problems, it is still 2x slower (only collecting variable, constants and parameters to build a LinearConstraint). Almost half of this time is spent in some promotions from AffExpr to GenericAffExpr{C,VariableOrParameter}.

I will do some tests including solving and presolving. I don´t think the current time penalty is too big, because there are usually way less parameter and they don´t appear in all constraints. However, the current benchmarks are indicating that if I create a new ParameterGenericAffExpr with more fields it could be faster. Because conversion, promotion and building LinearConstraint will be faster.

[joaquimg]

With this new version https://github.com/joaquimg/ParameterJuMP.jl/pull/2 the time overhead is zero and allocation overhead is less than 10%

[joehuchette]

That's pretty impressive!

[bbrunaud]

Hi. I like the parameters idea. I am currently doing some Lagrangean decompositions, and to avoid regenerating the entire model I just regenerate the objective. In this case, the parameter is the multiplier which is a coefficient in the objective.

Related, I would like to have the JuMPArray machinery available for parameters as well. I currently use lots of Dicts and Arrays. A usual operation is to want to set a slice of the parameters to a certain value, which currently requires a lot of for loops.

p = Dict(
(:A, :black) => 2,
(:A, :white) => 4,
(:B, :black) => 6,
(:B, :white) => 8,
)

p[:,:white] = 5 # something like that would be great.

I also would like to create a parameter straight from a DataFrame (or Excel file)

[joaquimg]

using parameters as coefficients is on my radar. But its harder than parameter on RHS. On RHS we have at most one extra linear expression per constraint, but as coefficient we have many options. If we allow coefficients to multiply each other it becomes much heavier. If we just allow coefficients to sum each other we would have one linear expression per variable and constraint. The lightest option is to allow just one parameter per variable in each constraint, but I don't know if thats too little.
What do you all think?

[odow]

My take on this is that introducing parameters is out of the scope of JuMP in the short- to medium-term. Exploration of the space is best done in a package such as ParameterJuMP.

Given that, is there any utility in keeping this issue open?

[joaquimg]

I agree it can be closed