Add bridge from Cumulative to MILP

[schlichtanders]

MILP bridges are largely done. I haven't done Path and Cumulative because they're quite complicated, but Cbc, HiGHS, and Gurobi are all passing tests with the new constraint programming sets!

Originally posted by @odow in https://github.com/jump-dev/MathOptInterface.jl/issues/1805#issuecomment-1170632492

Which Solver supports MOI.Cumulative?

I am just starting to use MOI.Cumulative, however I am lost about which solver supports it. You mentioned Cbc, HiGHS and Gurobi, but the docs do not mention that MOI.Cumulative would be supported by any of these.

Actually the Cumulative test explicitly skips those solvers who do not support Moi.Cumulative, so I guess the mentioned test is not run for these.

(I also tried a little example with HiGHS, but it says VectorOfVariables-in-Cumulative is not supported)

Failing Example

m = Model(HiGHS.Optimizer)
n = 10
@variable(m, test_start[1:n] >= 0)
@variable(m, test_duration[1:n] >= 1)
@variable(m, resources[1:n] == 1)
@variable(m, resource_bound == 1)
# constraint to be after another
@constraint(m, [test_start; test_duration; resources; resource_bound] in MOI.Cumulative(3*n+1))

# objective
@variable(m, total_end >= 0)
@constraint(m, total_end .>= (test_start .+ test_duration))
@objective(m, Min, total_end)

optimize!(m)

@show value.(test_start) value.(test_duration)

which fails with

Constraints of type MathOptInterface.VectorOfVariables-in-MathOptInterface.Cumulative are not supported by the solver.

If you expected the solver to support your problem, you may have an error in your formulation. Otherwise, consider using a different solver.

The list of available solvers, along with the problem types they support, is available at https://jump.dev/JuMP.jl/stable/installation/#Supported-solvers.

error(::String)@error.jl:35
_moi_add_constraint(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{HiGHS.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}, ::MathOptInterface.VectorOfVariables, ::MathOptInterface.Cumulative)@constraints.jl:686
add_constraint(::JuMP.Model, ::JuMP.VectorConstraint{JuMP.VariableRef, MathOptInterface.Cumulative, JuMP.VectorShape}, ::String)@constraints.jl:713
macro expansion@[Local: 133](http://localhost:1234/edit?id=d74b46c6-aed3-11ee-0b56-c17eddcbfb9c#)[inlined]
macro expansion@[Local: 375](http://localhost:1234/edit?id=d74b46c6-aed3-11ee-0b56-c17eddcbfb9c#)[inlined]
top-level scope@[Local: 9](http://localhost:1234/edit?id=d74b46c6-aed3-11ee-0b56-c17eddcbfb9c#)[inlined]

As there seems to be no bridge, I am really struggling, how to use this constraint.

[schlichtanders]

It seems the only option is MiniZinc.jl, it is pretty slow though...

It would be great if Cumulative (and Path) could also get a MOI bridge

[odow]

As there seems to be no bridge It would be great if Cumulative (and Path) could also get a MOI bridge

Correct, see:

I haven't done Path and Cumulative because they're quite complicated

It seems the only option is MiniZinc.jl, it is pretty slow though...

What size problem are you solving?

[odow]

This looks useful: https://www.diva-portal.org/smash/get/diva2:1041663/FULLTEXT01.pdf

[blegat]

It seems the only option is MiniZinc.jl, it is pretty slow though...

What is slow exactly ? The time taken by MiniZinc.jl, the time taken by minizinc to reformulate or the time it takes for the MILP solver because the MILP reformulation is not appropriate ?

[odow]

the time it takes for the MILP solver because the MILP reformulation is not appropriate ?

I assume this. The cumulative constraint is non-trivial to reformulate. (See PDF above.)

[schlichtanders]

Thank you for the pdf pointer.

I can confirm that MiniZinc.jl performance is unacceptable slow for even tiny cases. Unfortunately I probably won't find time to implement the PDF algorithm for a MOI bridge, (in case I find another quicker workaround).

[odow]

I think I'm going to close this issue as out-of-scope because the reformulation is very non-trivial and this set is not widely used.

I will reconsider this if we get more feature requests, so if you, future reader, are interested, please comment below and I will re-open.