MatrixOfConstraints and IndexMap

[blegat]

Document that solvers can rely on the fact that MatrixOfConstraints does not implement deletion of rows and columns and hence, the OptimizerCache can be done in a way such that the index map is identity.

When using OrderedProductOfSets, the solver will need to keep the product of set as a field after copy_to to handle the mapping of indices to ranges, such mapping is needed for conic solvers anyway.

For linear solvers, there is also the choice of using MixOfScalarSets for which the mapping is trivial so no need to keep the product of set as a field.

Since that would make many solvers use identity_index_map, it gives incentive to make this function cheaper. One option is to make CleverDict even more clever with a bool is_identity and only start using vector when the mapping starts being non-trivial. That would also benefit to solvers not using identity_index_map but for which the mapping is trivial most of the time.

See jump-dev/Cbc.jl#189 (comment)

[odow]

Is there any benchmark we could run that would show this is meaningful?

No one has complained about it, and I don't recall it ever appearing in our profiling, so I'm hesitant to add yet more complicated machinery to the index maps.

[blegat]

IIRC, you were mentioning a use case for the identity index map recently but I don't recall. Anyway, this comes from the benchmarking of SCS that we did for the MOI paper (which started the development of MatrixOfConstraints). Most of the time remaining was building the index maps. Now, for conic solvers, this is still negligible compared to the solve time so you won't see complaints, it's mostly when benchmarking to model creation time. For LP's, it might be more noticeable but LP solvers don't use MatrixOfConstraints for now (maybe they could ? :) )

[odow]

Now, for conic solvers, this is still negligible compared to the solve time so you won't see complaints, it's mostly when benchmarking to model creation time

This seems like a low priority then. I'm very hesitant to add more complexity to MOI to chase performance wins.

[blegat]

Yes, it's not high priority

[odow]

I'm very hesitant to add more complexity to MOI to chase performance wins.

I still believe this, and I'm tempted to close this issue because of it. I don't remember the last time that this was an issue in any benchmark or post on Discourse.

[blegat]

We've been discussing the overhead of IndexMap in a few other issues as well, I still think it is worth it, not only for MatrixOfConstraints