Parametrise sets or have different sets?

[dourouc05]

What would be the best option to encode very similar sets? Currently, I have defined GlobalCardinality, GlobalCardinalityVariable, ClosedGlobalCardinality, and ClosedGlobalCardinalityVariable: there are also up-low and sliding variants of the GCC, which would make an awful lot of sets (sixteen). Plus less common variants, without loops and with a cost matrix, that would make 64 sets for all possible variants of GCC, i.e. a combinatorial explosion. (And then some user will ask for another kind, and that would be 128.)

The same kind of problem appeared with knapsacks and bin packing: every time a new parameter is added or a fixed parameter is allowed to be a variable, a slew of new sets must be added (with many new bridges, also).

The other solution would be to have more parameters for each set: that would mean only a GlobalCardinality set to replace the four existing GlobalCardinality, GlobalCardinalityVariable, ClosedGlobalCardinality, and ClosedGlobalCardinalityVariable. It would look like this:

struct GlobalCardinality{T, UpOrLow, VariableValues} <: MOI.AbstractVectorSet
    dimension::Int
    values::Vector{T}
end

# GlobalCardinalityVariable{T}: GlobalCardinality{T, false, true}
# ClosedGlobalCardinality{T}: GlobalCardinality{T, true, false}
# ClosedGlobalCardinalityVariable{T}: GlobalCardinality{T, true, true}

Instead of Booleans, we could do like MOI.Indicator and use an enum (https://github.com/jump-dev/MathOptInterface.jl/blob/9ceb2dee8820e14c1edb0f21b66115faa3469af6/src/sets.jl#L985-L1041). Using this kind of type parameters would be absolutely needed so that solvers can say exactly what version(s) they support and rely on bridges for the rest of them (for instance, Closed just means that the number of occurrences for each value is bounded below and above).

However, such a representation would make it hard to extend the available sets: adding a new GCC set, for instance, would require changing this package's code to remain consistent. It's still possible to create sets outside, however. I feel this would break the OCP principle, even though the code here would be easier to write and to use for users. To write new solver wrappers, I don't think having type parameters instead of many sets would be a great problem, but each change to CPE would force solvers/wrappers to be updated (I don't think there should be many of them either).

@Wikunia @Azzaare in your opinion, what would be best for the solvers and users?

[Azzaare]

This is a very fascinating key point that we need to agree upon!

I agree that differentiating, with a concrete type, each combination is not sustainable. Or we would need to make it meta-programming based (which is somewhat OK).

The more I think about, the more I feel meta-programming is the solution to add more variants. Note, that I use low-case names to make it distinct from the usual Set names in JuMP/MOI. What I would like to see (as a user) would be something like:

function global_cardinality(;
    up_or_low = false,
    variables_values = false,
    ... = ...,
    )
    # dispatch to the generated relevant struct if available
    # otherwise dispatch to default GCC with a warning
end 

As for the dev side, it would be nice to be able to generate the set following something similar to:

const GCC_OPTIONS = Dict(
    :up_or_low => Bool,
    :variables_values => Bool,
    :some_sliding_option => RelevantType,
)

@generate_sets :GlobalCardinality GCC_OPTIONS

That way, adding new options would be as simple as adding the relevant Pair in GCC_OPTIONS. We can even make the @generate_sets macro the basic way to add Set in CPE.
As we would rely on a keyarg based dispatcher when the user wants to create the relevant constraint, everything should be extensible without breaking anything.

I don't know if my proposal is clear or not, so do not hesitate to ask/modify/improve/reject ;)

[odow]

Are there any solvers which would only support a subset of these? If every solver supports all variation of the cardinality constraints, just have one type. The nice thing about having this in an extension package is that you're much freer to break things and try different approaches than if it was in MOI.

[Azzaare]

Most solvers aim to have broad list of constraints. Mature solvers are likely to support most of those.
CPLEX-CP is in that category.

I suppose that ConstraintSolver.jl and SeaPearl.jl are not there yet.

As for CBLS.jl, due to the nature of local search solvers, adding a new constraint is a matter of minutes.
So anything that is or will be in CPE will be interfaced.

@dourouc05 should we prepare an interface for every thing in the global constraint catalog ? :p
I wonder if we could generate the constraints sets automatically by scrawling their website ...

[dourouc05]

@Azzaare I already thought about metaprogramming instead of writing specific code for each variant, but I was stopped by documentation… In my opinion, it's best to have precise doc for each concrete set. I think it would be best, from that point of view, to have a base type that is extremely flexible and completely documented, and a lot of constructors to ease the use of the main struct. These constructors could be easily generated by metaprogramming. Otherwise, I was already thinking about the kind of interface you showed!

@odow Solver by solver, for the few I checked:

• CPLEX only has Distribution constraints and not many more of GCC (it used to have them, but they have been removed a while ago, roughly in 2006).
• JaCoP has the standard GCC and an up-low variant (but penalised, not a strong constraint).
• OscaR has many variants: standard, variable cardinality, up-low.

There is quite a lot of variability there. I bet that we'll need a way to dispatch on the exact variant of the GCC so that solvers can be precise about what they support (or need bridges for).

@Azzaare Well, there are quite a few constraints in the GCC :)! (I wonder why they took that acronym…) However, they have really so many variations of the sets that are only implemented by one solver (or just a few papers about the propagators), I'm not sure it's useful to implement all these constraints. For now, I really focused on what exists in solvers and in MiniZinc, that's already quite a lot of work! Maybe we could also have a look at Java's JSR-331, as a solver-agnostic interface for CP.

Instead of scraping, we could simply rely on the XML-like description of the catalog (normally, an XSD file just describes the structure of XML files); they also describe a Prolog version, but I can't find it.

[Azzaare]

@dourouc05 regarding the interface, it is great that I ended up having an idea similar to what you already had in mind. We should probably try to converge on something during the first Julia CP meeting.

Since the different solvers' implementation of constraints is quite different, maybe we could try to do it in a MOI style, but with more options. For instance, we could have something similar to:

# default to false unless the user set it explicitly to true
CPE.supports_constraint(::Optimizer, ::Type{VOV}, ::Type{GlobalCardinality}) = true

# we provide the most generic variant of the constraint as default
CPE.default_variant(::Optimizer, ::Type{GlobalCardinality}) = ClosedGlobalCardinality

# probably interface the different variants with the solver internals

Finally, regarding the GCC :/, I have a use-case to extract the content of their entire catalog for something else, so I can (and will) give a go at finding the Prolog/XML version of the catalog and convert it to something more convenient in Julia (probably a nested dict structure).
My proposition of the global_cardinality disptacher method (or something equivalent) could be the place where we store the doc. We could even try to get some inspiration of https://github.com/baggepinnen/AutomaticDocstrings.jl to generate some basic documentation based on the info we could extract from GCC (and then improve/modify them if necessary)

We could then select the families of constraints (for instance GlobalCardinality) and the members/variants (GlobalCardinalityVariable, etc.) we want to extract from GCC. So the effort on our part (beside making this metaprogramming and doc stuff automatic) would be to classify the family and variants we want to extract.
We could add default bridges per variants/family.

On the solver dev side, it would just be about indicating support (as in MOI), providing a default variant if necessary, and interface with the solver internals for each variants.

On the user side, it would be as simple as calling the base GlobalCardinality structure/constructor with optional arguments for the variants.

[dourouc05]

I'm not sure I completely understand your proposed design with default_variant. Could you expand a bit on how you would use default_variant?

Normally, it's up to the user to select the kind of GCC they need for their model (otherwise, they'll end up with a different model, possibly far away from way they wanted in the first place). In the end, each solver should indicate what variants they support (based on what MOI already does) and use bridges if the input from the user doesn't match exactly what they natively support.

The more I think about it, the more I'm convinced that using a parametrised type would be an excellent option, like GlobalCardinality{UpAndDown, Closed, whatnot}:

• solvers can have a truckload of supports_constraint for each variation they support, because these definitions are extremely short;
• if a new variant is added, we can add a few constructors to default to some sane value. For instance:

struct X{A, B, C} end # Set with a third parameter
X{A, B}() where {A, B} = X{A, B, false}() # Compatibility constructor to default the new parameter 
    # to a sane default (i.e., equivalent to the previous definition)
X{true, false}() # Users can still use their previous code
f(::X{A, B}) where {A, B} = 42 # Unfortunately, if a function does not yet support the third argument, 
    # it's simply ignored; see next point

• to deal with the new parameters, we can do some Holy-trait dispatching:

MOI.supports_constraint(o, f, s::Type{GlobalCardinality}) = 
    MOI.supports_constraint(o, f, s, Val(s.first), Val(s.second), Val(s.third))

MOI.supports_constraint(o, f, s::Type{GlobalCardinality}, first, second, third::Val{false}) = 
    MOI.supports_constraint(o, f, s::Type{GlobalCardinality}, first, second) 
    # If the third parameter is not yet used by the solver (because not yet updated), 
    # ignore it if not used for this set.
    # This is easily overridden by the solver if they want to.

[dourouc05]

I made all the (breaking) changes I had in mind regarding this issue; we can still add more sugar if need be to ease writing solver wrappers.

@Azzaare I'll be tagging a v0.4 quite soon!

[Azzaare]

Great! I'll be waiting for it and try to interface my solver with 0.4.

I will probably make a CBLS2.jl package to interface with CPE and see if there are some additional features that I could use.

(I might be a bit slow to do things this month because I am taking a break in between two jobs though)

[dourouc05]

Good to hear! I wish you luck with your new job :)!