[Utilities] maintain order of variables in default_copy_to

[odow]

This PR is an investigation of what we would need to implement to close #2493. It is still very rough around the edges; I need to clean it up and profile for performance, but as a demo, the case from #2493 now works:

julia> main()
NAME
ROWS
 N  OBJ
COLUMNS
    x         OBJ       1
    y         OBJ       1
RHS
RANGES
BOUNDS
 FR bounds    x
 LO bounds    y         0
 PL bounds    y
ENDATA

TODOs

• [x] Fix tests
• [x] https://github.com/jump-dev/MathOptInterface.jl/actions/runs/8946191513
• [x] Benchmark performance

[odow]

So this, somewhat surprisingly, didn't break any tests. I don't know if that is a good thing or a bad thing... I guess it's because we're completely agnostic to the ordering of columns, so we always use index_map.

[odow]

Okay there are a few failures to look at in solver-tests.

[odow]

using Revise
import MathOptInterface as MOI
function build_src(M, N, p)
    src = MOI.Utilities.Model{Float64}()
    x = MOI.add_variables(src, N)
    indices = unique(rand(1:N, round(Int, p * N)))
    ci = MOI.add_constraint.(src, x[indices], MOI.GreaterThan(0.0))
    indices = unique(rand(1:N, round(Int, p * N)))
    ci = MOI.add_constraint.(src, x[indices], MOI.LessThan(1.0))
    for _ in 1:M
        i = rand(1:N)
        indices = i:min(N, i + 10)
        MOI.add_constraint(
            src,
            MOI.VectorOfVariables(x[indices]),
            MOI.SecondOrderCone(length(indices)),
        )
    end
    return src
end

julia> src = build_src(500_000, 1_000_000, 0.5)
MOIU.Model{Float64}
├ ObjectiveSense: FEASIBILITY_SENSE
├ ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
├ NumberOfVariables: 1000000
└ NumberOfConstraints: 1287703
  ├ MOI.VectorOfVariables in MOI.SecondOrderCone: 500000
  ├ MOI.VariableIndex in MOI.GreaterThan{Float64}: 393979
  └ MOI.VariableIndex in MOI.LessThan{Float64}: 393724

master

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.415108 seconds (2.18 M allocations: 468.760 MiB, 7.19% gc time)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.462140 seconds (2.18 M allocations: 485.807 MiB, 7.48% gc time)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.292704 seconds (2.18 M allocations: 485.807 MiB)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.426020 seconds (2.18 M allocations: 468.760 MiB, 8.28% gc time)

This PR

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.684707 seconds (3.15 M allocations: 598.370 MiB, 9.53% gc time)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.691145 seconds (3.15 M allocations: 598.370 MiB, 8.83% gc time)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.664689 seconds (3.15 M allocations: 598.370 MiB, 8.72% gc time)

julia> dest = MOI.Utilities.Model{Float64}(); GC.gc(); @time MOI.copy_to(dest, src);
  1.805403 seconds (3.15 M allocations: 598.370 MiB, 8.82% gc time)

So things are a little slower, but that is as could be expected.

A few hundred ms slowdown for really large problems (10^6 variables and constraints) seems reasonable to ensure that we get ordered variables.

[odow]

https://github.com/jump-dev/MathOptInterface.jl/actions/runs/9490932918

[odow]

So there are a bunch of solver-test failures that look problematic.

[odow]

Let's just see how many are because of this PR: https://github.com/jump-dev/MathOptInterface.jl/actions/runs/9491359380

[odow]

I think a bunch might be because of https://github.com/jump-dev/MathOptInterface.jl/pull/2508

[odow]

https://github.com/jump-dev/MathOptInterface.jl/actions/runs/9493107312

[odow]

OSQP failure is unrelated: https://github.com/osqp/OSQP.jl/pull/126

[odow]

The DSDP failure is suspicious: test_conic_SecondOrderCone_out_of_order

I assume it's because the variables are out of order, so we end up bridging it with some slack variables, which increases the problem size. Previously, we would have added the constraint as a variable, permuting the original variable order.

[blegat]

I assume it's because the variables are out of order, so we end up bridging it with some slack variables, which increases the problem size. Previously, we would have added the constraint as a variable, permuting the original variable order.

Yes, I think we can ignore it

[odow]

My discussion with @blegat after the developer call is: this seems reasonable. There might be performance edge cases we haven't considered, but this is really a single sort, so it likely isn't the bottleneck. Fixing the order of variables is more important.

[odow]

So I didn't run solver-tests after removing the dead code.

BilevelJuMP was using _try_constrain_variables_on_creation:

https://github.com/joaquimg/BilevelJuMP.jl/blob/954467f72a93b3cd37b2846971dfbfd458019af8/src/moi_utilities.jl#L70