Interacting with Constraints in Julia

Constraints.jl is designed to facilitate the definition, manipulation, and application of constraints in constraint programming (CP).

Note

It also acts as a catalog of various information and features learned about constraints by the learning part of the ecosystem. Per design, we only store the practical information extracted by those tools (such as CompositionalNetworks or QUBOConstraints) and not the heavy machinery (ConstraintLearning).

Usual Constraints and Parameters

The usual constraints of Julia Constraints are heavily inspired by the core constraints of the XCSP3-core standard. The main difference lies in the name chosen to describe the different parameters those core constraints can have.

In XCSP3, the parameters are described based on their roles, which the user can find as keyword argument in the xcsp_ prefixed collection of constraints (for instance xcsp_all_different). In our the Julia Constraints API (JC-API), the keyword arguments correspond to the nature of each parameter.

ConstraintCommons.USUAL_CONSTRAINT_PARAMETERS Constant

const USUAL_CONSTRAINT_PARAMETERS

List of usual constraints parameters (based on XCSP3-core constraints). The list is based on the nature of each kind of parameter instead of the keywords used in the XCSP3-core format.

const USUAL_CONSTRAINT_PARAMETERS = [
    :bool, # boolean parameter
    :dim, # dimension, an integer parameter used along the pair_vars or vals parameters
    :id, # index to target one variable in the input vector
    :language, # describe a regular language such as an automaton or a MDD
    :op, # an operator such as comparison or arithmetic operator
    :pair_vars, # a list of parameters that are paired with each variable in the input vector
    :val, # one scalar value
    :vals, # a list of scalar values (independent of the input vector size)
]

source

We provide a couple of methods to navigate the usual constraints extracted from XCSP3-Core.

Constraints.USUAL_CONSTRAINTS Constant

USUAL_CONSTRAINTS::Dict

Dictionary that contains all the usual constraints defined in Constraint.jl. It is based on XCSP3-core specifications available at https://arxiv.org/abs/2009.00514

Adding a new constraint is as simple as defining a new function with the same name as the constraint and using the @usual macro to define it. The macro will take care of adding the new constraint to the USUAL_CONSTRAINTS dictionary.

Example

@usual concept_all_different(x; vals=nothing) = xcsp_all_different(list=x, except=vals)

source

Constraints.describe Function

describe(constraints::Dict{Symbol,Constraint}=USUAL_CONSTRAINTS; width=150)

Return a pretty table with the description of the constraints in constraints.

Arguments

• constraints::Dict{Symbol,Constraint}: dictionary of constraints to describe. Default is USUAL_CONSTRAINTS.

• width::Int: width of the table.

Example

describe()

source

Constraints.constraints_parameters Function

constraints_parameters(C=USUAL_CONSTRAINTS)

Return a pretty table with the parameters of the constraints in C.

Arguments

• C::Dict{Symbol,Constraint}: dictionary of constraints. Default is USUAL_CONSTRAINTS.

Example

constraints_parameters()

source

Constraints.constraints_descriptions Function

constraints_descriptions(C=USUAL_CONSTRAINTS)

Return a pretty table with the descriptions of the constraints in C.

Arguments

• C::Dict{Symbol,Constraint}: dictionary of constraints. Default is USUAL_CONSTRAINTS.

Example

constraints_descriptions()

source

Concepts, Error Functions, and QUBO matrices

One major use of this collection of usual constraint is to extract the concept or the error function (error_f) of a given constraint.

Constraints.concept Function

concept(c::Constraint)

Return the concept (function) of constraint c. concept(c::Constraint, x...; param = nothing) Apply the concept of c to values x and optionally param.

source

concept(s::Symbol, args...; kargs...)

Return the concept of the constraint s applied to args and kargs. This is a shortcut for concept(USUAL_CONSTRAINTS[s])(args...; kargs...).

Arguments

• s::Symbol: the constraint name.

• args...: the arguments to apply the concept to.

• kargs...: the keyword arguments to apply the concept to.

Example

concept(:all_different, [1, 2, 3])

source

Note that the error function is a finer estimation of how much a constraint is violated or not. By default, the error_f method simply return $0.$ if the constraint is satisfied or $1.$ otherwise.

Efficient versions of error_f are either hand-coded or generated through CompositionalNetworks.jl.

Constraints.error_f Function

error_f(c::Constraint)

Return the error function of constraint c. error_f(c::Constraint, x; param = nothing) Apply the error function of c to values x and optionally param.

source

Finally, another use is to provide QUBO matrices of those usual constraints through QUBOConstraints.jl. The syntax and interface for this feature are still a work in progress.