Fix rounding in test_heuristic_callback

[odow]

I have seen the occasional failure in MOI's tests of third-party packages: https://github.com/jump-dev/MathOptInterface.jl/actions/runs/9539455292/job/26289809582

If the solution is not integer, then x_vals may contain a very large float that is not representable in Int64, and so round errors. We should try to round the solution only if the status is integer.

[odow]

There's an interesting failure on Windows: your status is incorrect:

[NCKempke]

@odow So I think there is a more fundamental bug here. Actually, I don't think the fix should be necessary.

Let me start from the beginning. When we build the test model, the callback_knapsack_model we add a bunch of variables and then call MOI.add_constraints(model, x, MOI.ZeroOne()). I think this add_constraints call is somewhat broken. My suspicion is, that these ZeroOne constraints get lost somewhere and COPT then just solves an LP, not a MIP.

I changed the failing test to look like

function test_heuristic_callback()
   model, x, item_weights = callback_knapsack_model()
   return MOI.optimize!(model)
end

and ran the test. The output is an LP solve with the barrier method.

This explains also the flakiness of the test - the solution returned is an LP solution, not an integral MIP one. Thus, the test only succeeds when the Simplex/Barrier randomly find an integral solution. The solution returned when the test fails is LP feasible and has the same objective as the 'correct one', but it is not integral.

I was then wondering where the MOI.ZeroOne constraints went - and only found 2 add_constraints methods in the MOI: https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1691 and https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L2088

I have only limited Julia knowledge - but to me it looks like neither of them implements the addition of the MOI.ZeroOne (and the MOI.Integer). The first one operates on

const _SCALAR_SETS = Union{
    MOI.GreaterThan{Float64},
    MOI.LessThan{Float64},
    MOI.EqualTo{Float64},
    MOI.Interval{Float64},
}

and the second one on

 <:Union{
    MOI.GreaterThan{Float64},
    MOI.LessThan{Float64},
    MOI.EqualTo{Float64},
},

if I get that correctly? So who handles the add_constraints for MOI.ZeroOne and MOI.Integer? There are methods to add these constraints for individual variables: https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1945 and https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1985

What I don't get is how the code can even run when the correct template method (or whatever the correct Julia term would be :D) is missing? Should this not crash? I'm not sure about anything - but adding println's to the two add_constraints methods showed that they were not being called. We looked at the Gurobi julia interface and found the same implementation - so either the test is broken there too (might be that Gurobi always polishes its solution/runs simplex on the model which then actually aims towards integer feasible solutions?) or my thoughts are wrong.

A fix would probably be to extend the _SCALAR_SETS based version of the add_constraints to also add the MOI.ZeroOne and MOI.Integer constraints (potentially by dispatching to the individual add_constraint methods).

[NCKempke]

@odow So I think there is a more fundamental bug here. Actually, I don't think the fix should be necessary.

Let me start from the beginning. When we build the test model, the callback_knapsack_model we add a bunch of variables and then call MOI.add_constraints(model, x, MOI.ZeroOne()). I think this add_constraints call is somewhat broken. My suspicion is, that these ZeroOne constraints get lost somewhere and COPT then just solves an LP, not a MIP.

I changed the failing test to look like

function test_heuristic_callback()
   model, x, item_weights = callback_knapsack_model()
   return MOI.optimize!(model)
end

and ran the test. The output is an LP solve with the barrier method.

This explains also the flakiness of the test - the solution returned is an LP solution, not an integral MIP one. Thus, the test only succeeds when the Simplex/Barrier randomly find an integral solution. The solution returned when the test fails is LP feasible and has the same objective as the 'correct one', but it is not integral.

I was then wondering where the MOI.ZeroOne constraints went - and only found 2 add_constraints methods in the MOI: https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1691 and https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L2088

I have only limited Julia knowledge - but to me it looks like neither of them implements the addition of the MOI.ZeroOne (and the MOI.Integer). The first one operates on

const _SCALAR_SETS = Union{
    MOI.GreaterThan{Float64},
    MOI.LessThan{Float64},
    MOI.EqualTo{Float64},
    MOI.Interval{Float64},
}

and the second one on

 <:Union{
    MOI.GreaterThan{Float64},
    MOI.LessThan{Float64},
    MOI.EqualTo{Float64},
},

if I get that correctly? So who handles the add_constraints for MOI.ZeroOne and MOI.Integer? There are methods to add these constraints for individual variables: https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1945 and https://github.com/COPT-Public/COPT.jl/blob/main/src/MOI/MOI_wrapper.jl#L1985

What I don't get is how the code can even run when the correct template method (or whatever the correct Julia term would be :D) is missing? Should this not crash? I'm not sure about anything - but adding println's to the two add_constraints methods showed that they were not being called. We looked at the Gurobi julia interface and found the same implementation - so either the test is broken there too (might be that Gurobi always polishes its solution/runs simplex on the model which then actually aims towards integer feasible solutions?) or my thoughts are wrong.

A fix would probably be to extend the _SCALAR_SETS based version of the add_constraints to also add the MOI.ZeroOne and MOI.Integer constraints (potentially by dispatching to the individual add_constraint methods).

The output I get when running my modified callback test:

julia> include("/home/nckempke/git/COPT.jl/test/MathOptInterface/callback.jl")
WARNING: replacing module TestCallback.
Starting barrier solver using 22 threads

Iter       Primal.Obj         Dual.Obj      Compl  Primal.Inf  Dual.Inf    Time    Center P.Step D.Step NZeroPiv Ref       Tau
   0  -1.12573279e+03  -1.35395502e+02   6.37e+03    3.38e+02  1.31e+01   0.00s      0.00   0.00   0.00        0   0  1.00e+00
   1  -2.83560909e+02  -1.01530864e+02   1.63e+03    6.91e+01  2.68e+00   0.00s      0.00   0.75   0.75        0   0  1.25e+00
   2  -4.89183016e+01  -3.06788968e+01   3.88e+02    6.88e+00  2.67e-01   0.00s      0.02   0.77   0.77        0   0  2.99e+00
   3  -1.91602469e+01  -1.60094674e+01   9.37e+01    1.18e+00  4.59e-02   0.00s      0.01   0.77   0.77        0   0  4.20e+00
   4  -1.47423139e+01  -1.42883080e+01   1.57e+01    1.71e-01  6.62e-03   0.00s      0.01   0.84   0.84        0   0  4.89e+00
   5  -1.40162252e+01  -1.39863940e+01   1.11e+00    1.12e-02  4.36e-04   0.00s      0.00   0.93   0.93        0   0  5.26e+00
   6  -1.39625937e+01  -1.39625592e+01   1.32e-03    1.31e-05  5.07e-07   0.00s      0.00   1.00   1.00        0   0  5.35e+00
   7  -1.39625247e+01  -1.39625247e+01   1.32e-09    1.31e-11  4.76e-13   0.00s      0.00   1.00   1.00        0   0  5.35e+00

Barrier status:                  OPTIMAL
Primal objective:                -1.39625247e+01
Dual objective:                  -1.39625247e+01
Duality gap (abs/rel):           3.45e-11 / 2.47e-12
Primal infeasibility (abs/rel):  1.31e-11 / 1.31e-12
Dual infeasibility (abs/rel):    4.76e-13 / 1.67e-14

Starting crossover using 1 thread

       0 primal pushes remaining      0.00s
       0 dual pushes remaining        0.00s

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual             0   -1.3962524721e+01            0           0       0.00s

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual             0   -1.3962524721e+01            0           0       0.00s
Test Summary:           |Time
test_heuristic_callback | None  0.1s

[NCKempke]

It seems that even changing the code to

for var in x
    MOI.add_constraint(model, var, MOI.ZeroOne())
end

does not work? It still solves an LP for me.

[NCKempke]

@odow nevermind any of my comments earlier. I don't know what the print was that I was seeing - but I fixed my side now and see that the problem is correctly being solved as a MIP. I still don't understand where MOI.add_constraints(model, x, MOI.ZeroOne()) delegates to, but I can debug this now properly. Sorry.

[NCKempke]

Ok, the failing test is a bug in COPT where we hand some uninitialized memory to the user via the MIPSOL context. I opened a MR for COPT. The fix will be available with the next public release.

[NCKempke]

Ok, the failing test is a bug in COPT where we hand some uninitialized memory to the user via the MIPSOL context. I opened a MR for COPT. The fix will be available with the next public release.

This should also fix the test I hope. We could keep this MR until then and see whether it is still needed.

[odow]

If you don't implement a specialized add_constraints method, there is a default fallback in MOI that is essentially the loop: https://github.com/jump-dev/MathOptInterface.jl/blob/08d34003cd3d7500379d9440e92445bc4d9a8fa8/src/constraints.jl#L239-L242

[NCKempke]

If you don't implement a specialized add_constraints method, there is a default fallback in MOI that is essentially the loop: https://github.com/jump-dev/MathOptInterface.jl/blob/08d34003cd3d7500379d9440e92445bc4d9a8fa8/src/constraints.jl#L239-L242

That makes sense. And would also explain why I could not find it. Thanks ;)

[odow]

The spooky-action-at-a-distance is both a blessing and a curse for Julia.