Add Parameter{T} <: AbstractScalarSet

[odow]

Today I had a call with @sstroemer and @jd-lara, and we discussed the logistics of adding a Parameter{T} <: AbstractScalarSet to MOI.

Motivation

The Parameter{T} set is similar to the EqualTo{T} set, but with the special case that solvers could support add_constrained_variable(model, ::Parameter) and not add the index as a decision variable to the underlying solver object.

The goal is to support JuMP syntax like:

model = Model()
@variable(model, x)
@variable(model, p in MOI.Parameter(1.0))
# or
@variable(model, p == 1.0, Parameter)
@constraint(model, p * x <= p + 1)
@objective(model, Min, p * x + 3 * p)
optimize!(model)
fix(p, 2.0)
optimize!(model)

The benefits of an explicit parameter are that, compared to EqualTo, they can reduce the problem size and allow solvers to interpret p * x as an affine function instead of quadratic.

Backstory

We've tried quite a few ways to achieve this over the years...

EqualTo

The easiest approach is just to use fixed variables a parameters and let the solvers presolve them out. This works for additive parameters, but fails for p * x if the solver does not support quadratic constraints.

Another downside is that it leads to more decision variables in the problem because p is added as a decision variable.

Nonlinear

JuMP already has nonlinear parameters, which are added via @NLparameter. If we add a NonlinearFunction, #2059, then we'll need some way to add parameters to MOI anyway.

The current parameter implementation is very specialized inside MOI.Nonlinear.Model.

ParameterJuMP

@joaquimg started ParameterJuMP.jl to support right-hand side parameters in JuMP.

The core premise is that it is a JuMP extension which defines a new ParameterRef <: AbstractVariableRef, and then stores parameterized JuMP expressions as a double expression:

struct ParameterizedAffExpr
    lhs::GenericAffExpr{V,VariableRef}
    rhs::GenericAffExpr{V,ParameterRef}
end

There are two main downsides to this approach:

• Two expressions, coupled with Julia's compiler optimizations which can sometimes put an AffExpr on the stack instead of heap, means that memory overhead can be 2-3X larger than a JuMP model with the EqualTo approach.
• It doesn't support p * x; only additive terms are supported.

ParametricOptInterface

To work-around the two problems in ParameterJuMP, the PUC-Rio/PSR folks (@guilhermebodin, @rafabench, and @tomasfmg) have been developing https://github.com/jump-dev/ParametricOptInterface.jl.

This is a MOI solver layer that adds a ParametricOptInterface.Parameter set, and then intercepts the model to replace parameters by their fixed constants.

The main downsides are the complexity of the implementation, and how much state is needed to be stored inside the optimizer to track where and when the parameters are stored.

Recent work

@sstroemer has been hard at work exploring this, also motivated by an energy systems model.

One idea is to use the recently added Bridges.final_touch to rewrite quadratic constraints to affine:
#2092

Another is to add support at the JuMP-level to track parameters: jump-dev/JuMP.jl#3215.

Loosely, these correspond to the approaches in ParametricOptInterface and ParameterJuMP.

Proposal

The basic part of the proposal is to add a MOI.Parameter set to MOI. We already know this is useful, because it is identical to what is added by ParametericOptInterface. In addition, we're going to need it for the nonlinear stuff.

The more complicated question is what should happen after that.

ParameterToEqualToBridge

We should add a bridge from Parameter to EqualTo. This would be a pretty trivial fallback that'll mean it should work across all solvers.

FixParametricVariablesBridge

We can update #2092 to use only Parameter instead of EqualTo. This should let p * x be re-written to affine for solvers not supporting quadratic.

But for solvers supporting quadratic, and for additive parameters to be efficient, we'll need...

Solver support

Solvers will need to declare support for MOI.Parameter, and then parse constraints as they're added to extract parameters into the constant terms. They'll also need to maintain a mapping so that updating a parameter updates all of constraints inside the solver.

Why not double down on ParametricOptInterface

This is a good question. At minimum, adding Parameter will also help POI.

I don't have a good answer on the rest. One objection is that the POI codebase is complicated, and there is a lot of internal state to maintain. The bridge in #2092 is very simple in comparison. But perhaps the overhead of adding native parameter support to Gurobi.jl (for example) would be equally challenging.

The argument in favor of solver-specific implementations is that they could make their updates more efficient.

[blegat]

There is yet another alternative: have a variable bridge for constrained variables in Parameter. We have have the whole substitution worked out in the variable bridging which is already doing what #2092 is doing.
In fact, if you add a constrained variable in EqualTo to a solver like CSDP, it is variable-bridged into a variable in Zeros and then variable-bridged into nothing. So this is already doing the job of substituting the parameters ! But it is not done in case a solver supports creating variables constrained in EqualTo.
The downside is that you cannot get the dual of the variable then! This is not implemented by the bridge as it would then need to implement all the bookkeeping that POI does.

What I would suggest is:

• Define the Parameter set in MOI
• Implement a variable bridge similar to https://github.com/jump-dev/MathOptInterface.jl/blob/master/src/Bridges/Variable/bridges/vectorize.jl and https://github.com/jump-dev/MathOptInterface.jl/blob/master/src/Bridges/Variable/bridges/zeros.jl. The advantage over [Bridges] Add FixParametricVariablesBridge #2092 is that the implementation is much more simple and robust (e.g., no need for final_touch, it also works for substituting variables in function types that the solver support) but it's only made possible thanks to the fact that we define this new Parameter set, it would not work with EqualTo since solvers supports this set so no variable bridge could get called.
• Have POI use this Parameter instead of its own set

Then we would have:

• If a user create a variable with EqualTo then it will not be substituted and he would get a dual (unless it is bridged by the variable bridged, e.g., for CSDP but I always remove that bridge if I know I need duals)
• If a user create a variable in Parameter then there are three cases
  • The solver supports it, then anything can happen
  • The solver does not support it but you add the POI layer, then it gets substituted and you get a dual for it!
  • The solver does not support it and you don't add the POI layer, then it gets substituted by the variable bridges which does no bookkeeping but you don't get a dual for it.

[guilhermebodin]

I agree that adding a Parameter to MOI would help POI.

Here is my small contribution to the discussion:

The POI codebase is a little complicated and has to store a lot of internal states because supporting parametric operations anywhere within the problem and supporting most F-in-S is not super simple. We did try to keep the caches at a minimum trying not to lose performance.

Adding support for parameters directly in solvers would end up in rewriting a subset of POI on each solver. This could make each small POI wrapper very efficient for the solver in question but would also require additional hours to maintain it. Also, it would not be trivial to maintain it on every solver.

In my opinion, adding the Parameter set to MOI would give the option of either using POI or using another implementation (possibly solver-specific) but we could also try to refactor POI in a way that maintaining it would be less of a burden and friendlier. In the future, POI could possibly be integrated into MOI (I don't know if you guys think that this is reasonable).

[joaquimg]

POI has 2 reasons to be a bit scary in terms of bookkeeping:

1. It does more than simply pre-solve parameters. As commented by @blegat , it computes duals in special cases.
2. It was never refactored to be cleaner. We simply focused on improving speed more and more without special care to the data structure. It can certainly be improved, probably without much effort.

If solvers want to have POI functionality native in their wrapper, the code complexity will grow meaningfully, mainly if they want that to be efficient, and if they will end up requiring dual (which they will, just a matter of time between considering parameters and then requiring duals). So, as @guilhermebodin mentioned, I am also a bit worried that solvers will start doing that on their own.

About the bridges, for me, is the same reasoning as the solvers. Now people want parameters. There is a not-very-complicated fix for that. But tomorrow, they will want duals (they already want them). Bridges will get more complicated and painful to maintain. I think there will be no free lunch.

What is the difference between bridges and layers like POI?
Not much, bridges are layers, but they have some common infrastructure that might make them easier to implement in some cases. It has been suggested to use bridges instead of layers in some cases, which is great. But by design bridges are especially good if constraints are independent. So for presolving parameters it might seem simple, but computing duals will be messy.

I'd say that some refactoring to simplify POI is the more general and more sustainable alternative and should not be a complex task, as things already work: we have benchmarks and working tests.

I have no objection to adding MOI.Parameter, which might even simplify POI.

My fears are: complicating the solver wrappers or adding a bridge that only does half of the work and is not better than POI.

On a very side note, MOI.Parameter might be useful in DiffOpt, although it might just need all of POI infrastructure anyway. So not clear if Parameter being on POI or MOI makes much difference.

[blegat]

I agree that implementing parameter support in solver wrappers is not a good idea. It would only be meaningful if the underlying solver already has support for it.

About the bridges, for me, is the same reasoning as the solvers. Now people want parameters. There is a not-very-complicated fix for that. But tomorrow, they will want duals (they already want them). Bridges will get more complicated and painful to maintain. I think there will be no free lunch.

I agree, this is why I suggest the variable bridge approach instead of #2092. It is easy to add since all the complicated part is already part of the variable bridging mechanism which is common to all variable bridges. The advantage is that we don't have to implement support for MOI.Parameter in solvers. Users will be able to use MOI.Parameter and it will always just work with every solver thanks to the variable bridge. Once they will start asking for duals, they will get an error saying that they need to explicitly add a POI layer.

[jd-lara]

I'd say that the complexity of POI has other issues besides maintenance. I was never able to get all the features from JuMP implemented in PowerSimulations.jl when the model used POI. Simple tasks like getting the model variable bounds or querying a parameter value after a problem modification became intractable and require many workarounds.

After testing with ParameterJuMP, POI and also just using variables and letting the solver manage the equalities we had to go with the later solution which wasn't ideal because we end up hitting the limits on the number of variables in the solvers. However, it was the only way to get all the JuMP model exploration features working and also not hit the issue of the double dict of parametrized expressions. Further, when benchmarking build and solve time POI against adding variables and using JuMP.fix there was no difference in the timing for medium size models in the order of 80k variables/constraints.

The idea of having native support for parameters in the solver will allow to optimize how the solvers manage updating, specially the the RHS. We know that Gurobi is better on an element by element basis while Xpress is better on batch updates. It stands to reason that if every solver has a "best" way to do parameter update the support for that lives in the solver.

[joaquimg]

I was never able to get all the features from JuMP implemented in PowerSimulations.jl when the model used POI.

These are bugs, and must be fixed. Are all of them issues in POI already?

not hit the issue of the double dict of parametrized expressions

Is it detailed somewhere?

Further, when benchmarking build and solve time POI against adding variables and using JuMP.fix there was no difference in the timing for medium size models in the order of 80k variables/constraints.

I think this is expected, mainly in commercial solvers. The issues are with much larger problems, as you mentioned, and that it does not extend to multiplicative parameters.

The idea of having native support for parameters in the solver will allow to optimize how the solvers manage updating, specially the the RHS. We know that Gurobi is better on an element by element basis while Xpress is better on batch updates. It stands to reason that if every solver has a "best" way to do parameter update the support for that lives in the solver.

• But you agree that this will add a lot of complexity, code replication and maintenance burden to wrappers, right?

• We have added methods for batch updates in MOI, we can add more if needed and remain generic.

• In this, I agree with @blegat , solvers should only support MOI.Parameter if they actually support parameters as a solver feature.

[jd-lara]

I was never able to get all the features from JuMP implemented in PowerSimulations.jl when the model used POI.

These are bugs, and must be fixed. Are all of them issues in POI already?

Yes, I opened issues for every case I ran into. However, the crux of the issue is that POI was no better than using JuMP.fix with additional variables in build and solve time + the added complexity.

not hit the issue of the double dict of parametrized expressions

Is it detailed somewhere?

Lots of detail here JuliaStochOpt/ParameterJuMP.jl#85

Further, when benchmarking build and solve time POI against adding variables and using JuMP.fix there was no difference in the timing for medium size models in the order of 80k variables/constraints.

I think this is expected, mainly in commercial solvers. The issues are with much larger problems, as you mentioned, and that it does not extend to multiplicative parameters.

But the multiplicative parameter update optimizations are very solver dependent, I would argue even more than RHS. Each solver handles very differently how refactor or update the LHS matrix. Multiplicative parameter update would be an argument to add parameter support at the solver level.

The idea of having native support for parameters in the solver will allow to optimize how the solvers manage updating, specially the the RHS. We know that Gurobi is better on an element by element basis while Xpress is better on batch updates. It stands to reason that if every solver has a "best" way to do parameter update the support for that lives in the solver.

• But you agree that this will add a lot of complexity, code replication and maintenance burden to wrappers, right?

Yes, this is true. That being said, it is worth exploring how much more code that is. If we take it as a simple index container like ParameterJuMP it doesn't seem to be that much of a deal IMO but I might be wrong.

• We have added methods for batch updates in MOI, we can add more if needed and remain generic.
• In this, I agree with @blegat , solvers should only support MOI.Parameter if they actually support parameters as a solver feature.

[joaquimg]

Yes, I opened issues for every case I ran into. However, the crux of the issue is that POI was no better than using JuMP.fix with additional variables in build and solve time + the added complexity.

Benchmarks in POI showed that you would need 3 or 4 update+solve after build to have an improvement. We can try improving if there is a MWE.
On the other hand, JuMP.fix is great and hard to beat because (commercial) solvers are fast. However, you mentioned it does not scale for very very large models and it certainly does not work for multiplicative parameters.
If your models are not super large and you don't need multiplicative parameters, it might well be that JuMP.fix is as good as it gets (again, depending on the problem structure and number of update_solves). JuMP.fix will be the best option for a variety of cases.

Lots of detail here JuliaStochOpt/ParameterJuMP.jl#85

Ok, it is a ParameterJuMP only issue, it is not an issue in POI. I got confuse because there is a helper data structure in MOI called DoubleDict which is extensively used in POI. Hence I was (incorrectly) worried about some issues with their usage that led to some problems.

But the multiplicative parameter update optimizations are very solver dependent, I would argue even more than RHS. Each solver handles very differently how refactor or update the LHS matrix. Multiplicative parameter update would be an argument to add parameter support at the solver level.

First, we have to check if this is really not doable from POI. The one issue I know is gurobi requires a call to "update" between getters and setters. This can be avoided with batch methods and with a Gurobi wrapper attribute to change this behaviour to some manual mode, which would be way simpler than moving all the work that POI does to Gurobi.jl.

Yes, this is true. That being said, it is worth exploring how much more code that is. If we take it as a simple index container like ParameterJuMP it doesn't seem to be that much of a deal IMO but I might be wrong.

ParameterJuMP does not handles multiplicative parameters, so it can be much simpler. At the same time we can refactor POI a bit to reduce code. I do not see how a wrapper level implementation of parameters would be simpler than a cleaned-up POI. You have to cache the very same information at the end.

[blegat]

I agree with @joaquimg I tend to find a solver-independent implementation such as POI more readable and I don't see how specializing the code for a solver would simplify it so much. I might be wrong but we should have a clear idea why a solver-independent solution is not possible before implementing something solver specific. If there is something missing in the MOI modification API then improving the MOI API would be a win for other applications as well