Variable deletion with bridges

[blegat]

All bridges in MOI are affine transformations except the QuadtoSOC bridge.
As deletion commutes with affine transformations, except for the QuadtoSOC bridge, there should be no issue just deleting the variable in the bridged solver model.
Deleting a variable part of a quadratic term of a quadratic function bridged by the QuadtoSOC bridged might be an issue though.
We should check that and add tests (with quadratic objective and quadratic constraints).

See https://github.com/jump-dev/MathOptInterface.jl/pull/2150/files#r1173436839

[blegat]

Replying to #2156 (comment)

That just seems like added complications for minimal benefit.

This is not about measuring benefit, it's about correctness, deleting a variable should have the same effect that rebuilding a model from scratch without that variable. This is currently the only exception I know. I'm not saying it should be fixed right away but we should keep this open at least

[odow]

Base MOI doesn't delete rows. And the internal workings of a bridge are private. We don't make any claims about efficiency etc. just that the transformation is correct. I don't think users could reasonably expect us to rebuild the transformation when we delete arbitrary variables. In theory, the user shouldn't be checking the inner bridged model, so they'd never know about the zero row.

And even if they did, I'm not sure the extra complication in the bridge is worth the trade-off.

julia> import MathOptInterface as MOI

julia> model = MOI.Utilities.Model{Float64}()
MOIU.Model{Float64}

julia> x = MOI.add_variables(model, 2)
2-element Vector{MathOptInterface.VariableIndex}:
 MOI.VariableIndex(1)
 MOI.VariableIndex(2)

julia> f = MOI.Utilities.operate(vcat, Float64, (1.0 .* x)...)
┌                              ┐
│0.0 + 1.0 MOI.VariableIndex(1)│
│0.0 + 1.0 MOI.VariableIndex(2)│
└                              ┘

julia> MOI.add_constraint(model, f, MOI.Nonnegatives(2))
MathOptInterface.ConstraintIndex{MathOptInterface.VectorAffineFunction{Float64}, MathOptInterface.Nonnegatives}(1)

julia> MOI.delete(model, x[1])

julia> print(model)
Feasibility

Subject to:

VectorAffineFunction{Float64}-in-Nonnegatives
 ┌              ┐
 │0.0           │
 │0.0 + 1.0 v[2]│
 └              ┘ ∈ Nonnegatives(2)

[blegat]

Some conic solvers might not behave so well with zero rows on the SOC constraints, as this constraint is indeed private to the bridge, the bridge is responsible to do the right thing in case of deletion. Throwing a DeleteNotAllowed would be better than the current behavior (then the CachingOptimizer would trigger a rebuild).

[odow]

Some conic solvers might not behave so well with zero rows on the SOC constraints

This might be a good motivation.

[odow]

So I've been looking into this. It's quite complicated. We'd need to add a final_touch to the bridge to loop through and check if any variables had been deleted, and if they had, if they were the only element in a row of the RSOC constraint. And then we'd have to delete the constraint and rebuild.

Isn't the alternative the solver throwing an error if it deletes a variable that ends up creating a zero row, and the solver doesn't support zero rows? Why does this need to be resolved in the bridge?

[blegat]

Isn't the alternative the solver throwing an error if it deletes a variable that ends up creating a zero row, and the solver doesn't support zero rows? Why does this need to be resolved in the bridge?

How would that error be useful for the user ? He didn't create the SOC constraint, the bridge is responsible.
We could also have a supports_variable_deletion in the bridge API which is true by default. In a bridge optimizer, we have a field indicating whether at least one bridge does not support deleting a variable. In that case, the bridge optimizer just throws that deletion is not supported. That will be caught by the CachingOptimizer and the model will be rebuilt at optimize!.

[odow]

How would that error be useful for the user ?

The solver would throw DeleteNotAllowed and the cache would then rebuild. User wouldn't see anything.

We could also have a supports_variable_deletion in the bridge API which is true by default. In a bridge optimizer, we have a field indicating whether at least one bridge does not support deleting a variable. In that case, the bridge optimizer just throws that deletion is not supported.

This feels complicated for something that we don't actually know is an issue yet. Can we wait for someone to complain?

[blegat]

The solver would throw DeleteNotAllowed and the cache would then rebuild. User wouldn't see anything.

Conic solvers don't support deletion (except Mosek), it's done in their cache. It's pretty hard to catch down the line.
At the end of the day, deletion does not commute with nonlinear model transformation so the current implementation of AbstractBridgeOptimizer makes an incorrect assumption. QuadtoSOC is an example but there could be more in extensions. It's best to fix what's wrong than trying to do damage control.

We could also have a supports_variable_deletion in the bridge API which is true by default. In a bridge optimizer, we have a field indicating whether at least one bridge does not support deleting a variable. In that case, the bridge optimizer just throws that deletion is not supported.

This feels complicated for something that we don't actually know is an issue yet. Can we wait for someone to complain?

Yes but I'd prefer we leave this open.

[odow]

Why does the bridge need to be responsible for deciding whether deletion is allowed here? The inner optimizer can throw DeleteNotAllowed if it doesn't support deleting a variable that results in a 0 row, or if it doesn't support deleting the epigraph variable in a conic constraint.

SCIP is an example of a solver that does this:

https://github.com/scipopt/SCIP.jl/blob/2d3897668d4f718f8a04e4a8d708ac938df48a93/src/MOI_wrapper/variable.jl#L60-L72

I guess there might be Cache(Bridge(Cache(Optimizer))) and the optimizer gets rebuilt from the inner cache, not the bridge.

I still think that this isn't an issue that will ever be a problem in practice, and I don't want to add complexity to MOI to deal with it.

I think the sticking point is:

deleting a variable should have the same effect that rebuilding a model from scratch without that variable

We have never made this claim, and it isn't true in the current implementation.

[blegat]

Suppose you solve a QP, the problem is long to solve because you have a lot of variables. You delete most of them, you solve again, it still long to solver, what's happening ???
The dimension of the SOC constraint created by the QuadToSOC is equal to the number of variables involved so it had to be decreased but it was not. IMO this is undesired behavior. The proposal of #2153 (comment) doesn't seem too complicated to implement. This function would return true by default so the cost of implementing a new bridge would be the same anyway. It will also not complicate the implementation of the bridge optimizer much, it's just one call when a bridge is created and one check when a variable deletion is made.

Users could also be implemented other bridges that would change if variables are deleted even though they act on quadratic/affine/nl functions. Not having this function in the API and in the docs would simply lead them to incorrectness without warning which isn't a good design.