Improve support for constraint programming

[dourouc05]

I'm making this new issue to track the progress on CP support in JuMP. (Brief reminder: started with #2014; then, a few changes in #2051 to make more constraints parse.) I'm opening this issue to discuss the progress on this side (maybe this should be marked as 1.0?).

For now, these things have been implemented:

• Several CP sets, an extension to MOI: ConstraintProgrammingExtensions.jl
• New constraints in JuMP to create CP constraints easily: JuCP.jl; this absolutely requires Add extension points for more generic @constraint syntax #2051 to be merged
• A first solver is partially wrapped: CPLEXCP.jl

There are many more details about all this in JuCP, including design considerations and next steps. Some of these steps could be made into GSoC projects (dealing with tests, writing new wrappers, mostly), if it's not too late for inclusion.

---

More complete list of things:

• On MOI's side:
  • Discuss the best way to deal with functions: Next-generation nonlinear MathOptInterface.jl#846 (comment)
• On JuMP's side:
  • Strict inequality: already possible. https://github.com/dourouc05/JuCP.jl/blob/0c2d0f359e882baf4ff06d404e47d9ee542b05e0/src/sets.jl#L51-L53
  • New syntax (functions as constraints): @constraint(m, constraint(x, y)). PR Add extension points for more generic @constraint syntax #2051.
  • New syntax (reification): @constraint(m, x := { constraint(x, y) }), @constraint(m, x := { x < y }). PR Add parse_constraint_expr and parse_constraint_head #2228 (split from Add extension points for more generic @constraint syntax #2051).
  • New syntax (new expressions in very limited cases): @constraint(m, x == count(y .== 1)). PR Add rewrite_call_expression. #2229 or PR Add rewrite_call_expression through _rewrite_expr. #2241 (split from Add extension points for more generic @constraint syntax #2051).
  • New syntax (new expressions in less limited cases): @constraint(m, x == y[z]) with either y or z variables. No PR for now. Is an overload of getindex enough?
  • New syntax (Boolean algebra): @constraint(m, x \land y), @constraint(m, x & y). PR Add rewrite_call_expression through _rewrite_expr. #2241.
  • New syntax (Boolean expressions as constraints): @constraint(m, x) to be understood as @constraint(m, x == true). PR Add extension points for more generic @constraint syntax #2051?
  • Documentation for these new PRs on JuMP's side.
  • Bug fixes: parse_one_operator_constraint: clash with parse_ternary_constraint when there are four arguments #2246 (hack in JuCP).
• On CPE's side to extend MOI:
  • Many new sets implemented, review process started: https://github.com/dourouc05/ConstraintProgrammingExtensions.jl
  • Discussion about Element: [RFC] Element: limit to two elements? JuliaConstraints/ConstraintProgrammingExtensions.jl#3
  • Discussion about BinPacking: [RFC] BinPacking: what about forced fixed sizes? JuliaConstraints/ConstraintProgrammingExtensions.jl#4
  • Discussion about constraint mixing: Constraints that are "simple" compositions of other constraints JuliaConstraints/ConstraintProgrammingExtensions.jl#6
  • FlatZinc:
    • Output format
      • Standard sets
      • Nonlinear functions
    • Input format
      • Standard sets
      • Nonlinear functions
    • Optimizer interface
  • XCSP3:
• On JuCP's side to extend JuMP:
  • Provide basic, nice syntax for the wrapped constraints:
  • Provide more natural syntax for constraints that could benefit from it, like element
• On solvers' side:
  • Write generic tests for solvers, specifically for constraint engines (bad support for purely continuous problems).
  • Wrap CPLEX CP Optimizer in CPLEXCP.jl
    • Base wrapper around Java API
    • CP sets
    • Support for intervals and interval sequences
  • Wrap Choco
  • Wrap Chuffed
  • Wrap Gecode
  • Wrap JaCoP
  • Wrap LocalSolver (without the usual limitations of CP solver)

[dourouc05]

New PR #2241 that ought to replace #2229 to add more flexibility in rewriting expressions.

[dourouc05]

I have more general questions that would need a larger audience:

• [RFC] Element: limit to two elements? JuliaConstraints/ConstraintProgrammingExtensions.jl#3
• [RFC] BinPacking: what about forced fixed sizes? JuliaConstraints/ConstraintProgrammingExtensions.jl#4

Any comment welcome :)!

[dourouc05]

A version version of the CPLEX CP Optimizer wrapper is being tagged: JuliaRegistries/General#28051. However, it does not meet all guidelines, but that's on purpose (name close to CPLEX.jl, of course; not importable, because the CI environment doesn't have CPLEX; https://github.com/JuliaRegistries/General/pull/28051/checks?check_run_id=1711999279 is unrelated, I think).

[dourouc05]

A few notes on the recent developments. CPLEXCP.jl has a version 0.1.0 tagged; it should really be useful in many cases. Very specific features such as tuning the branching process are not available at all, but the modelling side is quite advanced (except where Concert uses complex-typed variables). There are quite a few remaining questions to answer, have a look at jump-dev/MathOptInterface.jl#1253 (more feedback is welcome there). Similarly, ConstraintProgrammingExtensions.jl has a 0.1.0 tagged, and should be useful to implement other solver wrappers (JuliaConstraints/ConstraintProgrammingExtensions.jl#7).

For longer-term issues, I also added a paragraph to highlight the fact that CP could really benefit from the new NLP features, once they are developed: https://docs.google.com/document/d/1SfwFrIhLyzpRdXyHKMFKv_XKeyJ6mi6kvhnUZ2LEEjM/edit#, under Use Cases (from jump-dev/MathOptInterface.jl#846).

[odow]

To update this issue:

• @dourouc05 wrote a blog post https://jump.dev/blog/constraint-programming-update/
• Development effort should go into https://github.com/dourouc05/ConstraintProgrammingExtensions.jl
• Extending syntax via parse_constraint is now documented: https://jump.dev/JuMP.jl/dev/developers/extensions/#Parse

[odow]

To update this issue:

• MOI v1.4.0 includes a number of new constraint programming sets
• MOI v1.6.0 includes a number of new bridges from constraint programming to MILP formulations

So this mainly needs some documentation to advertise the new features.