Improve support for constraint programming #2227
Comments
|
I have more general questions that would need a larger audience:
Any comment welcome :)! |
|
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). |
|
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). |
|
To update this issue:
|
|
To update this issue:
So this mainly needs some documentation to advertise the new features. |
|
Adding much better documentation here: #3202. I don't know if we'll ever get to a point of supporting a first-class constraint programming interface. Dealing with logical operators in a functional way seems hard. The best we could probably do is to support them in the nonlinear interface, and then have something like MiniZinc.jl try to parse them, and error if it encounters some nonlinearity that it doesn't support (like |
|
That would be awesome! Would we wait for the new nonlinear interface before trying this? |
I guess, technically, we could attempt this at present, just by parsing the Julia AST. I think the main issue is that something like |
|
The way it parses is the way I'd interpret it actually. We can think of constraints as expressions that must evaluate to true, in which case the above says either x (bool variable) is true, or y (int variable) is 1. We would want to support a new Bool type variable (not Bin) I think. |
The problem currently is that nonlinear constraints must be one- or two-sided (in)equalities. Let me have a play. I think originally I didn't go down this track because we were considering a fully fledged structure, but maybe a mix of function-in-set for things like all-different, and boolean relations gets us most of the way there. |
|
Maybe there could be a new type of constraint, a logical constraint, that is similar to nlconstraint but doesn't have this 1/2 sided inequality restriction. |
|
(let's start by dreaming big, and scale back if there's a clear reason why it's too hard 😁) |
|
Hah. This was easier than I thought. I'll make a PR. julia> using JuMP
julia> import MiniZinc
julia> model = Model(() -> MiniZinc.Optimizer{Int}(MiniZinc.Chuffed()))
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: MiniZinc
julia> set_optimizer_attribute(model, "model_filename", "test.mzn")
julia> @variable(model, x, Bin)
x
julia> @variable(model, y, Bin)
y
julia> @constraint(model, [x, y] in MOI.AllDifferent(2))
[x, y] ∈ MathOptInterface.AllDifferent(2)
julia> @NLconstraint(model, (x || y) == true)
(x || y) - 1.0 = 0
julia> @NLconstraint(model, (x && y) == false)
(x && y) - 0.0 = 0
julia> optimize!(model)
Warning: included file "count.mzn" overrides a global constraint file from the standard library. This is deprecated. For a solver-specific redefinition of a global constraint, override "fzn_<global>.mzn" instead.
Warning: included file "global_cardinality_low_up.mzn" overrides a global constraint file from the standard library. This is deprecated. For a solver-specific redefinition of a global constraint, override "fzn_<global>.mzn" instead.
julia> value(x), value(y)
(0.0, 1.0)
julia> print(read("test.mzn", String))
include "alldifferent.mzn";
var bool: x;
var bool: y;
constraint alldifferent([x, y]);
constraint ((x \/ y) - 1) == false;
constraint ((x /\ y) - 0) == false;
solve satisfy; |
|
So I'm pretty happy with that PR. It's a little tacky, but we could make it work much nicer if we added something like #3106. It's also quite a reasonable approach: use the structured function-in-set approach for combinatorial structure like |
|
Updated documentation is https://jump.dev/JuMP.jl/dev/tutorials/linear/constraint_programming/ |
Not sure I understand this sentence. Aren't you describing a bridge from ScalarNonliearFunction into structured boolean constraints ? Why does it have to be opt-in and not selected by the bridge hyper-graph ? |
Given that, in Julia, Another reason why the current parse seems totally fine: what about using For your original code sample, shouldn't it actually mean |
julia> dump(:(x || y == 1))
Expr
head: Symbol ||
args: Array{Any}((2,))
1: Symbol x
2: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol ==
2: Symbol y
3: Int64 1It lowers as The MiniZinc PR is now working for expressions like julia> dump(:(x || (b && (y < 5))))
Expr
head: Symbol ||
args: Array{Any}((2,))
1: Symbol x
2: Expr
head: Symbol &&
args: Array{Any}((2,))
1: Symbol b
2: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol <
2: Symbol y
3: Int64 5
julia> dump(:(x || (b && y < 5)))
Expr
head: Symbol ||
args: Array{Any}((2,))
1: Symbol x
2: Expr
head: Symbol &&
args: Array{Any}((2,))
1: Symbol b
2: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol <
2: Symbol y
3: Int64 5
julia> dump(:(x || b && y < 5))
Expr
head: Symbol ||
args: Array{Any}((2,))
1: Symbol x
2: Expr
head: Symbol &&
args: Array{Any}((2,))
1: Symbol b
2: Expr
head: Symbol call
args: Array{Any}((3,))
1: Symbol <
2: Symbol y
3: Int64 5So I think this is a pretty viable approach for solvers wanting to support boolean expressions. |
|
As far as I can see (I followed the latest developments from afar), there are all the required elements in MOI/JuMP. I can think of quality-of-life improvements, compared to other CP modelling systems, but not really in scope for JuMP. |
Yeah. I think I'm going to rule things like |
|
Is there a path forward for supporting more advanced CP variable types, e.g. set variables in minizinc: https://www.minizinc.org/doc-2.7.6/en/modelling2.html#set-constraints |
|
I don't think so. We ruled out more complicated variable types in MOI: jump-dev/MathOptInterface.jl#1253. Is the |
|
It can allow more natural modeling. And there could be bridges in place to do e.g. the binary vector of variables transformation for solvers that don't support it. Besides MiniZinc, LocalSolver seems to push using these set/list variable types too. There is some ongoing work (currently private, later to be released) to support that solver and those variable types. |
|
What syntax do you imagine at the JuMP level? What syntax at the MOI level? |
|
There is one possibility: |
|
the minizinc knapsack example is in Julia say we have |
|
At the JuMP level, you could do something like: model = Model()
@variable(model, x in List(N))but then what is the return type of The LocalSolver API is very nice (I've used it for a few models), but it is quite a large departure from JuMP's Math Programming roots. I think it is out-of-scope. |
|
Oops. Looks like we posted over the top of each other. Same question for:
So what is the type of |
|
These are feasible at the JuMP level, you can define at the JuMP level variables that behave like sets, I have done it in https://github.com/blegat/SetProg.jl. |
|
LocalSolver can do lots of things, but the API is very specific to LocalSolver, and isn't a widely used abstraction:
I don't think these belong in JuMP. |
|
JuMP, probably not; MOI should have a way to encode them (so we can access everything a solver has to offer), if these functions are available in other solvers. Then, another package could extend JuMP to provide a convenient way to use them (that's why I started JuCP, although I never really had time to work on that: https://github.com/JuliaConstraints/JuCP.jl). |
|
Yeah there are some common variable types between localsolver and MiniZinc that I would love to see MOI support somehow, like set variables. I'm not so concerned about JuMP support. I don't have the answers on how to do it right now but I don't think we should rule it out if we can come up with an abstraction for variables that is powerful and extensible like that of the sets/bridges. |
|
Like I wonder how far we could get by just using a normal moi variable index for a set variable, add a |
|
I think it breaks a very large number of assumptions about what Things like The answer has to be that There's also slight distinction. MiniZinc and LocalSolver both provide this functionality as modeling languages, not as solvers. But JuMP isn't designed like that, so it's not obvious that we can or should try to interface with them. It's also not obvious exactly how similar or different they are, both conceptually, and practically as they would be implemented in Julia. Nevertheless, perhaps a pathway forwards:
The first two steps can happen outside of JuMP and MOI, and don't need to be written by the JuMP contributors. (I'd say it would be a high-risk topic for an interested grad student, or requires $ with no concrete deliverables.) |
|
Looks like they can be implemented using a vector of
It seems to me that you could write a nice struct Subset{S}
set::S
selected::Vector{JuMP.VariableRef}
endwhich would be able to implement all these, e.g., function Base.in(s::Subset)
i = findfirst(s.set)
if isnothing(i)
return false
else
return s.selected[i]
end
endThis would give the nice abstraction at the MOI level. At the moment, I fail to see what useful structure would be lost by simply giving binary variables. |
This is kinda what I meant by:
JuMP can implement this at the modeling level, but that doesn't help us interface with the It's also the direction that @dourouc05 was going in with JuCP.jl. It can be a JuMP extension developed externally. It doesn't (and I think, probably shouldn't, at least in the near- to medium-term) need to be developed in JuMP directly. |
|
Right, the direction I was pushing for is to allow interfacing with MiniZinc/LocalSolver's common variable types, not building modeling abstractions in JuMP. |
|
What would the user gain with this interface ? Is that handled more efficiently than a vector of binary variables ? @variable(model, S in Subsets(1:3))
@variable(model, T in Subsets(1:3))
@constraint(model, 1 in S)
@constraint(model, partition(S, T) || (3 in S) && (2 in T) := true)as struct SubsetFamily
universe
containments::Vector{Vector{Int}} # containments[i] gives the list of boolean variables to create to represent whether the element belongs to the subset of id `i`
partitions::Vector{Vector{Int}} # partitions[i] gives the list of subset id and a boolean variable represent whether they are a partition
end
@variable(model, [s1, s3, t2, pST] in SubsetsFamily(1:3, [[1, 3], [2]], [[1, 2]]))
@constraint(model, s1 := true)
@constraint(model, pST || s3 && t2 := true)So MiniZinc and LocalSolver will need to implement support for adding constrained variables in |
|
The point is that @chriscoey want's to interface with the native support of MiniZinc and LocalSolver. He doesn't want a reformulation (though we'd probably want that as well, for things like HiGHS). It's not about what is more efficient. |
|
Thanks to everyone for thinking about this and proposing different solutions. @odow is right about what I want at least, though it's not necessarily what others want. It is conceivable to me at least that LocalSolver for example can do smarter things with Set or List variables compared to a reformulated binary IP type model (which loses structure), but I'm not sure what they do under the hood. |
|
The idea above with SubsetFamily is not a reformulation, it LocaSlolver can recover the user formulation as is |
|
I'd rather not rush (even a well considered proposal) to add new sets for this to MOI. It's not a concept that naturally fits into the I'll repeat my proposal that the next steps are:
Since no interface currently exists to LocalSolver (and I don't think anyone is planning on implementing it), this seems unlikely to happen anytime soon. For the purpose of this issue: Does JuMP need any more support for constraint programming? At this stage, no. But if new sets/features get added to MOI then we might have something concrete. Therefore, I think this issue can be closed. I'd prefer that we kept issues open only if there are concrete ideas and some tangible path to resolving them. The most appropriate next step would seem to be opening an issue in MiniZinc.jl to track how to add support for it's additional functionality that is not exposed by MOI, just like it is possible to access solver-specific functionality in Gurobi.jl via the C interface. |
And the second step could be to make these available from JuMP, e.g., by defining new MOI sets as the |
|
Perhaps to be clear: I don't like the design of |
|
I've added this to the agenda for next week's developer call. |
|
Monthly developer call agreed to close this issue. The consensus was that we've done as much as we can in the framework of MOI. We think that there is room/a desire/a need for things like interval variables, but these are best done as a JuMP extension for now. Adding them to MOI would likely require MOI 2.0 and at least an order of magnitude more work. |
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:
@constraintsyntax #2051 to be mergedThere 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:
@constraint(m, constraint(x, y)). PR Add extension points for more generic@constraintsyntax #2051.@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@constraintsyntax #2051).@constraint(m, x == count(y .== 1)). PR Addrewrite_call_expression. #2229 or PR Addrewrite_call_expressionthrough_rewrite_expr. #2241 (split from Add extension points for more generic@constraintsyntax #2051).@constraint(m, x == y[z])with eitheryorzvariables. No PR for now. Is an overload ofgetindexenough?@constraint(m, x \land y),@constraint(m, x & y). PR Addrewrite_call_expressionthrough_rewrite_expr. #2241.@constraint(m, x)to be understood as@constraint(m, x == true). PR Add extension points for more generic@constraintsyntax #2051?parse_one_operator_constraint: clash withparse_ternary_constraintwhen there are four arguments #2246 (hack in JuCP).Element: [RFC] Element: limit to two elements? JuliaConstraints/ConstraintProgrammingExtensions.jl#3BinPacking: [RFC] BinPacking: what about forced fixed sizes? JuliaConstraints/ConstraintProgrammingExtensions.jl#4elementThe text was updated successfully, but these errors were encountered: