Constraint programming support

[odow]

This issue is to track support for a limited subset of constraint programming in MOI. At present, we don't envisage MOI having the same scope as MiniZinc, but we want users to be able to write down common constraint programs and solve them using a specialized constraint programming solver, or a MIP solver via bridges.

Background

• Improve support for constraint programming JuMP.jl#2227
• https://github.com/JuliaConstraints/ConstraintProgrammingExtensions.jl

MathOptInterface

Add new sets to MOI. Definitions taken from: https://www.minizinc.org/doc-2.5.5/en/lib-globals.html

• all_different: Add support for Constraint Programming #1825
  
• nvalue Add CountDistinct set #1826
  
• among Add CountBelongs set #1827
  
• at_least Add CountAtLeast set #1828
  
• count_gt Add CountGreaterThan set #1829
  
• bin_packing Add constraint programming sets #1837
  
• path Add constraint programming sets #1837
  
• cumulative Add constraint programming sets #1837
  
• table Add constraint programming sets #1837
  
• circuit Add constraint programming sets #1837
  

MOI.Bridges

• Add bridges from new sets to MILP reformulations as appropriate
  • AllDifferent [Bridges] add AllDifferentToCountDistinctBridge #1923
  • BinPacking [Bridges] update BinPackingToMILPBridge to final_touch #1925
  • Circuit [Bridges] add CircuitToMILPBridge #1929
  • CountAtLeast [Bridges] add CountAtLeastToCountBelongsBridge #1920
  • CountBelongs [Bridges] add CountBelongsToMILPBridge #1919
  • CountDistinct [Bridges] add final_touch #1901
  • CountGreaterThan [Bridges] add CountGreaterThanToMILPBridge #1927
  • Cumulative Agreed with Bill to not include
  • Path Agreed with Bill to not include
  • Table

MOI.FileFormats

• Add FlatZinc writer. Initial work here: https://github.com/JuliaConstraints/ConstraintProgrammingExtensions.jl/tree/master/src/FlatZinc
• Add MiniZinc writer https://github.com/jump-dev/MiniZinc.jl
• Add new sets to MathOptFormat [FileFormats.MOF] update to [email protected] #1954

MOI.Test

• Add new tests for constraint solvers

Solvers

Update solvers to new sets in MOI

• https://github.com/JuliaConstraints/Chuffed.jl
• https://github.com/JuliaConstraints/CPLEXCP.jl

Replaced by the MiniZinc interface: https://github.com/jump-dev/MiniZinc.jl

[odow]

I've opened PRs to add the first 5 sets, since they are the simplest. There's still some bike shedding to be done. For the next step, I'll add the FlatZinc file format to get things in place. One we have that, we can start some end-to-end tests with a CP solver, and that should flush out any issues before we work on the other 5 sets.

[odow]

I've been taking a look at FlatZinc support. it's actually slightly more complicated than it looks, because its effectively MOI without bridges, and each solver supports a different set of constraints. What would be easier to target is MiniZinc, and then have MiniZinc compile down to FlatZinc when passed a particular solver. For example, Chuffed_jll contains a directory of re-definitions, which are equivalent to our bridges.

First step is to get libminizinc building: JuliaPackaging/Yggdrasil#4861

[odow]

I now have https://github.com/jump-dev/MiniZinc.jl.

This writes the JuMP model into a flattened form of MiniZinc, and we then call out to different solvers. The benefit of this is that it automatically supports all of the solvers that MiniZinc supports, so it works for Chuffed and Gurobi, for example.

I have it working locally, but MiniZinc_jll is segfaulting: JuliaPackaging/Yggdrasil#4866

[odow]

Bill says

i assume that MOI++ including constraints you're working on will support reified constraints so that in principle we might
support something like
alldiff(x1,x3,x5) or alldiff(x2,x4,x6) which translates to:
alldif_reif(x1,x3,x5,b1) and
alldiff_reif(x2,x4,x6,b2) and
(b1 or b2)

we don't necessarily need models for all reified constraints now and those could be filled in over time.

We could probably add Reified{S} similar to how we have indicator constraints.

[odow]

Initial support for the sets has been merged, and MiniZinc.jl is being registered: JuliaRegistries/General#62010

[odow]

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!

Once #1931 is merged, I'll prep for v1.6.0, and then write a blog post showing off the new goods.

[odow]

I've started looking into reified constraints: jump-dev/MiniZinc.jl#13

[odow]

Blog post is: https://jump.dev/announcements/2022/07/12/constraint-programming/

[odow]

This issue is pretty close to completion. One blocker is deciding whether to add the Reified set. I've added Reified to MiniZinc.jl, but adding to MOI would add a lot more sets, and the reified to MILP bridges are much more complicated.