Julia Constraints

Appearance

ConstraintDomains.jl: Defining Variables and Exploring Domains ​

ConstraintDomains.jl is the standard way to define variables and explore domains in the Julia Constraints ecosystem. This package can be used to specify both discrete and continuous domains. Explorations features are primarily related to learning about constraints, aka constraint learning.

Most users should use it through JuMP/MOI interfaces.

Commons ​

ConstraintDomains.AbstractDomain Type
julia
AbstractDomain

An abstract super type for any domain type. A domain type D <: AbstractDomain must implement the following methods to properly interface AbstractDomain.

  • Base.∈(val, ::D)

  • Base.rand(::D)

  • Base.length(::D) that is the number of elements in a discrete domain, and the distance between bounds or similar for a continuous domain

Additionally, if the domain is used in a dynamic context, it can extend

  • add!(::D, args)

  • delete!(::D, args)

where args depends on D's structure

source

ConstraintDomains.EmptyDomain Type
julia
EmptyDomain

A struct to handle yet to be defined domains.

source

ConstraintDomains.domain Function
julia
domain()

Construct an EmptyDomain.

source

julia
domain(a::Tuple{T, Bool}, b::Tuple{T, Bool}) where {T <: Real}
domain(intervals::Vector{Tuple{Tuple{T, Bool},Tuple{T, Bool}}}) where {T <: Real}

Construct a domain of continuous interval(s).

source

julia
domain(values)
domain(range::R) where {T <: Real, R <: AbstractRange{T}}

Construct either a SetDomain or a RangeDomain.

julia
d1 = domain(1:5)
d2 = domain([53.69, 89.2, 0.12])
d3 = domain([2//3, 89//123])
d4 = domain(4.3)
d5 = domain(1,42,86.9)

source

ConstraintDomains.domain_size Function
julia
domain_size(d <: AbstractDomain)

Fallback method for domain_size(d) that return length(d).

source

julia
domain_size(itv::Intervals)

Return the difference between the highest and lowest values in itv.

source

julia
domain_size(d::D) where D <: DiscreteDomain

Return the maximum distance between two points in d.

source

ConstraintDomains.get_domain Function
julia
get_domain(::AbstractDomain)

Access the internal structure of any domain type.

source

ConstraintDomains.to_domains Function
julia
to_domains(args...)

Convert various arguments into valid domains format.

source

Extension to Base module ​

Base.in Function
julia
x::Variable ∈ constraint
value ∈ x::Variable

Check if a variable x is restricted by a constraint::Int, or if a value belongs to the domain of x.

source

julia
var::Int ∈ c::Constraint

source

julia
Base.in(value, d <: AbstractDomain)

Fallback method for value ∈ d that returns false.

source

julia
Base.in(x, itv::Intervals)

Return true if x ∈ I for any 'I ∈ itv, false otherwise.x ∈ I` is equivalent to

  • a < x < b if I = (a, b)

  • a < x ≤ b if I = (a, b]

  • a ≤ x < b if I = [a, b)

  • a ≤ x ≤ b if I = [a, b]

source

julia
Base.in(value, d::D) where D <: DiscreteDomain

Return true if value is a point of d.

source

Base.rand Function
julia
Base.rand(::Vector{IntervalsFold})

Extend the Base.rand function to Vector{IntervalsFold}.

source

julia
rand(pf<:PatternFold)

Returns a random value of pf as if it was unfolded.

source

julia
Base.rand(::Vector{AbstractVectorFold})
Extend the `Base.rand` function to `Vector{AbstractVectorFold}`.

source

julia
Base.rand(d::Union{Vector{D},Set{D}, D}) where {D<:AbstractDomain}

Extends Base.rand to (a collection of) domains.

source

julia
Base.rand(itv::Intervals)
Base.rand(itv::Intervals, i)

Return a random value from itv, specifically from the ith interval if i is specified.

source

julia
Base.rand(d::D) where D <: DiscreteDomain

Draw randomly a point in d.

source

julia
Base.rand(fa::FakeAutomaton)

Extends Base.rand. Currently simply returns fa.

source

Base.isempty Function
julia
Base.isempty(d <: AbstractDomain)

Fallback method for isempty(d) that return length(d) == 0 which default to 0.

source

Base.rand Function
julia
Base.rand(::Vector{IntervalsFold})

Extend the Base.rand function to Vector{IntervalsFold}.

source

julia
rand(pf<:PatternFold)

Returns a random value of pf as if it was unfolded.

source

julia
Base.rand(::Vector{AbstractVectorFold})
Extend the `Base.rand` function to `Vector{AbstractVectorFold}`.

source

julia
Base.rand(d::Union{Vector{D},Set{D}, D}) where {D<:AbstractDomain}

Extends Base.rand to (a collection of) domains.

source

julia
Base.rand(itv::Intervals)
Base.rand(itv::Intervals, i)

Return a random value from itv, specifically from the ith interval if i is specified.

source

julia
Base.rand(d::D) where D <: DiscreteDomain

Draw randomly a point in d.

source

julia
Base.rand(fa::FakeAutomaton)

Extends Base.rand. Currently simply returns fa.

source

Base.string Function
julia
Base.string(D::Vector{<:AbstractDomain})
Base.string(d<:AbstractDomain)

Extends the string method to (a vector of) domains.

source

Performances ​

Bench Evolution CommonChair Evolution Common

Continuous ​

ConstraintDomains.ContinuousDomain Type
julia
ContinuousDomain{T <: Real} <: AbstractDomain

An abstract supertype for all continuous domains.

source

ConstraintDomains.Intervals Type
julia
Intervals{T <: Real} <: ContinuousDomain{T}

An encapsuler to store a vector of PatternFolds.Interval. Dynamic changes to Intervals are not handled yet.

source

ConstraintDomains.domain Function
julia
domain()

Construct an EmptyDomain.

source

julia
domain(a::Tuple{T, Bool}, b::Tuple{T, Bool}) where {T <: Real}
domain(intervals::Vector{Tuple{Tuple{T, Bool},Tuple{T, Bool}}}) where {T <: Real}

Construct a domain of continuous interval(s).

source

julia
domain(values)
domain(range::R) where {T <: Real, R <: AbstractRange{T}}

Construct either a SetDomain or a RangeDomain.

julia
d1 = domain(1:5)
d2 = domain([53.69, 89.2, 0.12])
d3 = domain([2//3, 89//123])
d4 = domain(4.3)
d5 = domain(1,42,86.9)

source

ConstraintDomains.domain_size Function
julia
domain_size(d <: AbstractDomain)

Fallback method for domain_size(d) that return length(d).

source

julia
domain_size(itv::Intervals)

Return the difference between the highest and lowest values in itv.

source

julia
domain_size(d::D) where D <: DiscreteDomain

Return the maximum distance between two points in d.

source

ConstraintDomains.merge_domains Function
julia
merge_domains(d₁::AbstractDomain, d₂::AbstractDomain)

Merge two domains of same nature (discrete/contiuous).

source

ConstraintDomains.intersect_domains Function
julia
intersect_domains(d₁, d₂)

Compute the intersections of two domains.

source

ConstraintDomains.intersect_domains! Function
julia
intersect_domains!(is, i, new_itvls)

Compute the intersections of a domain with an interval and store the results in new_itvls.

Arguments

  • is::IS: a collection of intervals.

  • i::I: an interval.

  • new_itvls::Vector{I}: a vector to store the results.

source

ConstraintDomains.size Function
julia
Base.size(i::I) where {I <: Interval}

Defines the size of an interval as its span.

source

Extension to Base module ​

Base.length Function
julia
length(layer)

Return the number of operations in a layer.

source

julia
Base.length(icn)

Return the total number of operations of an ICN.

source

julia
length(pf<:PatternFold)

Return the length of pf if unfolded.

source

julia
Base.rand(d <: AbstractDomain)

Fallback method for length(d) that return 0.

source

julia
Base.length(itv::Intervals)

Return the sum of the length of each interval in itv.

source

julia
Base.length(d::D) where D <: DiscreteDomain

Return the number of points in d.

source

Base.rand Function
julia
Base.rand(::Vector{IntervalsFold})

Extend the Base.rand function to Vector{IntervalsFold}.

source

julia
rand(pf<:PatternFold)

Returns a random value of pf as if it was unfolded.

source

julia
Base.rand(::Vector{AbstractVectorFold})
Extend the `Base.rand` function to `Vector{AbstractVectorFold}`.

source

julia
Base.rand(d::Union{Vector{D},Set{D}, D}) where {D<:AbstractDomain}

Extends Base.rand to (a collection of) domains.

source

julia
Base.rand(itv::Intervals)
Base.rand(itv::Intervals, i)

Return a random value from itv, specifically from the ith interval if i is specified.

source

julia
Base.rand(d::D) where D <: DiscreteDomain

Draw randomly a point in d.

source

julia
Base.rand(fa::FakeAutomaton)

Extends Base.rand. Currently simply returns fa.

source

Base.in Function
julia
x::Variable ∈ constraint
value ∈ x::Variable

Check if a variable x is restricted by a constraint::Int, or if a value belongs to the domain of x.

source

julia
var::Int ∈ c::Constraint

source

julia
Base.in(value, d <: AbstractDomain)

Fallback method for value ∈ d that returns false.

source

julia
Base.in(x, itv::Intervals)

Return true if x ∈ I for any 'I ∈ itv, false otherwise.x ∈ I` is equivalent to

  • a < x < b if I = (a, b)

  • a < x ≤ b if I = (a, b]

  • a ≤ x < b if I = [a, b)

  • a ≤ x ≤ b if I = [a, b]

source

julia
Base.in(value, d::D) where D <: DiscreteDomain

Return true if value is a point of d.

source

Base.string Function
julia
Base.string(D::Vector{<:AbstractDomain})
Base.string(d<:AbstractDomain)

Extends the string method to (a vector of) domains.

source

Performances ​

Bench Evolution ContinuousChair Evolution Continuous

Discrete ​

ConstraintDomains.DiscreteDomain Type
julia
DiscreteDomain{T <: Number} <: AbstractDomain

An abstract supertype for discrete domains (set, range).

source

ConstraintDomains.SetDomain Type
julia
SetDomain{T <: Number} <: DiscreteDomain{T}

Domain that stores discrete values as a set of (unordered) points.

source

ConstraintDomains.RangeDomain Type
julia
RangeDomain

A discrete domain defined by a range <: AbstractRange{Real}. As ranges are immutable in Julia, changes in RangeDomain must use set_domain!.

source

ConstraintDomains.ArbitraryDomain Function
julia
ArbitraryDomain{T} <: DiscreteDomain{T}

A domain type that stores arbitrary values, possibly non numeric, of type T.

source

ConstraintDomains.domain Function
julia
domain()

Construct an EmptyDomain.

source

julia
domain(a::Tuple{T, Bool}, b::Tuple{T, Bool}) where {T <: Real}
domain(intervals::Vector{Tuple{Tuple{T, Bool},Tuple{T, Bool}}}) where {T <: Real}

Construct a domain of continuous interval(s).

source

julia
domain(values)
domain(range::R) where {T <: Real, R <: AbstractRange{T}}

Construct either a SetDomain or a RangeDomain.

julia
d1 = domain(1:5)
d2 = domain([53.69, 89.2, 0.12])
d3 = domain([2//3, 89//123])
d4 = domain(4.3)
d5 = domain(1,42,86.9)

source

ConstraintDomains.domain_size Function
julia
domain_size(d <: AbstractDomain)

Fallback method for domain_size(d) that return length(d).

source

julia
domain_size(itv::Intervals)

Return the difference between the highest and lowest values in itv.

source

julia
domain_size(d::D) where D <: DiscreteDomain

Return the maximum distance between two points in d.

source

ConstraintDomains.add! Function
julia
add!(d::SetDomain, value)

Add value to the list of points in d.

source

ConstraintDomains.merge_domains Function
julia
merge_domains(d₁::AbstractDomain, d₂::AbstractDomain)

Merge two domains of same nature (discrete/contiuous).

source

ConstraintDomains.intersect_domains Function
julia
intersect_domains(d₁, d₂)

Compute the intersections of two domains.

source

ConstraintDomains.size Function
julia
Base.size(i::I) where {I <: Interval}

Defines the size of an interval as its span.

source

Extension to Base module ​

Base.delete! Function
julia
Base.delete!(d::SetDomain, value)(d::SetDomain, value)

Delete value from the list of points in d.

source

Base.length Function
julia
length(layer)

Return the number of operations in a layer.

source

julia
Base.length(icn)

Return the total number of operations of an ICN.

source

julia
length(pf<:PatternFold)

Return the length of pf if unfolded.

source

julia
Base.rand(d <: AbstractDomain)

Fallback method for length(d) that return 0.

source

julia
Base.length(itv::Intervals)

Return the sum of the length of each interval in itv.

source

julia
Base.length(d::D) where D <: DiscreteDomain

Return the number of points in d.

source

Base.rand Function
julia
Base.rand(::Vector{IntervalsFold})

Extend the Base.rand function to Vector{IntervalsFold}.

source

julia
rand(pf<:PatternFold)

Returns a random value of pf as if it was unfolded.

source

julia
Base.rand(::Vector{AbstractVectorFold})
Extend the `Base.rand` function to `Vector{AbstractVectorFold}`.

source

julia
Base.rand(d::Union{Vector{D},Set{D}, D}) where {D<:AbstractDomain}

Extends Base.rand to (a collection of) domains.

source

julia
Base.rand(itv::Intervals)
Base.rand(itv::Intervals, i)

Return a random value from itv, specifically from the ith interval if i is specified.

source

julia
Base.rand(d::D) where D <: DiscreteDomain

Draw randomly a point in d.

source

julia
Base.rand(fa::FakeAutomaton)

Extends Base.rand. Currently simply returns fa.

source

Base.in Function
julia
x::Variable ∈ constraint
value ∈ x::Variable

Check if a variable x is restricted by a constraint::Int, or if a value belongs to the domain of x.

source

julia
var::Int ∈ c::Constraint

source

julia
Base.in(value, d <: AbstractDomain)

Fallback method for value ∈ d that returns false.

source

julia
Base.in(x, itv::Intervals)

Return true if x ∈ I for any 'I ∈ itv, false otherwise.x ∈ I` is equivalent to

  • a < x < b if I = (a, b)

  • a < x ≤ b if I = (a, b]

  • a ≤ x < b if I = [a, b)

  • a ≤ x ≤ b if I = [a, b]

source

julia
Base.in(value, d::D) where D <: DiscreteDomain

Return true if value is a point of d.

source

Base.string Function
julia
Base.string(D::Vector{<:AbstractDomain})
Base.string(d<:AbstractDomain)

Extends the string method to (a vector of) domains.

source

Performances ​

Bench Evolution DiscreteChair Evolution Discrete

General ​

Base.eltype Function
julia
Base.eltype(::AbstractDomain)

Extend eltype for domains.

source

Base.convert Function
julia
Base.convert(::Type{Union{Intervals, RangeDomain}}, d::Union{Intervals, RangeDomain})

Extends Base.convert for domains.

source

Exploration ​

ConstraintDomains.Explorer Type

Explorer(concepts, domains, objective = nothing; settings = ExploreSettings(domains))

Create an Explorer object for searching a constraint satisfaction problem space.

Arguments

  • concepts: A collection of tuples, each containing a concept function and its associated variable indices.

  • domains: A collection of domains representing the search space.

  • objective: An optional objective function for optimization problems.

  • settings: An ExploreSettings object to configure the exploration process.

Returns

An Explorer object ready for exploration.

Example

julia
domains = [domain([1, 2, 3]), domain([4, 5, 6])]
concepts = [(sum, [1, 2])]
objective = x -> x[1] + x[2]
explorer = Explorer(concepts, domains, objective)

source

ConstraintDomains.ExploreSettings Type
julia
ExploreSettings(
    domains;
    complete_search_limit = 10^6,
    max_samplings = sum(domain_size, domains),
    search = :flexible,
    solutions_limit = floor(Int, sqrt(max_samplings)),
)

Create settings for the exploration of a search space composed by a collection of domains.

Arguments

  • domains: A collection of domains representing the search space.

  • complete_search_limit: Maximum size of the search space for complete search.

  • max_samplings: Maximum number of samples to take during partial search.

  • search: Search strategy (:flexible, :complete, or :partial).

  • solutions_limit: Maximum number of solutions to store.

Returns

An ExploreSettings object.

Example

julia
domains = [domain([1, 2, 3]), domain([4, 5, 6])]
settings = ExploreSettings(domains, search = :complete)

source

ConstraintDomains.explore! Function
julia
explore!(explorer::Explorer)

Perform exploration on the search space defined by the Explorer object.

This function explores the search space according to the settings specified in the Explorer object. It updates the Explorer's state with found solutions and non-solutions.

Arguments

  • explorer: An Explorer object containing the problem definition and exploration settings.

Returns

Nothing. The Explorer's state is updated in-place.

Example

julia
explorer = Explorer(concepts, domains)
explore!(explorer)
println("Solutions found: ", length(explorer.state.solutions))

source

ConstraintDomains.explore Function
julia
explore(domains, concept; settings = ExploreSettings(domains), parameters...)

Explore a search space defined by domains and a concept.

Arguments

  • domains: A collection of domains representing the search space.

  • concept: The concept function defining the constraint.

  • settings: An ExploreSettings object to configure the exploration process.

  • parameters: Additional parameters to pass to the concept function.

Returns

A tuple containing two sets: (solutions, non_solutions).

Example

julia
domains = [domain([1, 2, 3]), domain([4, 5, 6])]
solutions, non_solutions = explore(domains, allunique)

source

Performances ​

Bench Evolution ExplorationChair Evolution Exploration

Parameters ​

ConstraintDomains.BoolParameterDomain Type
julia
BoolParameterDomain <: AbstractDomain

A domain to store boolean values. It is used to generate random parameters.

source

ConstraintDomains.DimParameterDomain Type
julia
DimParameterDomain <: AbstractDomain

A domain to store dimensions. It is used to generate random parameters.

source

ConstraintDomains.IdParameterDomain Type
julia
IdParameterDomain <: AbstractDomain

A domain to store ids. It is used to generate random parameters.

source

ConstraintDomains.FakeAutomaton Type
julia
FakeAutomaton{T} <: ConstraintCommons.AbstractAutomaton

A structure to generate pseudo automaton enough for parameter exploration.

source

ConstraintCommons.accept Function
julia
accept(a::Union{Automaton, MDD}, w)

Return true if a accepts the word w and false otherwise.

source

julia
ConstraintCommons.accept(fa::FakeAutomaton, word)

Implement the accept methods for FakeAutomaton.

source

ConstraintDomains.fake_automaton Function
julia
fake_automaton(d)

Construct a FakeAutomaton.

source

ConstraintDomains.LanguageParameterDomain Type
julia
LanguageParameterDomain <: AbstractDomain

A domain to store languages. It is used to generate random parameters.

source

ConstraintDomains.OpParameterDomain Type
julia
OpParameterDomain{T} <: AbstractDomain

A domain to store operators. It is used to generate random parameters.

source

ConstraintDomains.PairVarsParameterDomain Type
julia
PairVarsParameterDomain{T} <: AbstractDomain

A domain to store values paired with variables. It is used to generate random parameters.

source

ConstraintDomains.ValParameterDomain Type
julia
ValParameterDomain{T} <: AbstractDomain

A domain to store one value. It is used to generate random parameters.

source

ConstraintDomains.ValsParameterDomain Type
julia
ValsParameterDomain{T} <: AbstractDomain

A domain to store values. It is used to generate random parameters.

source

Base.rand Function
julia
Base.rand(::Vector{IntervalsFold})

Extend the Base.rand function to Vector{IntervalsFold}.

source

julia
rand(pf<:PatternFold)

Returns a random value of pf as if it was unfolded.

source

julia
Base.rand(::Vector{AbstractVectorFold})
Extend the `Base.rand` function to `Vector{AbstractVectorFold}`.

source

julia
Base.rand(d::Union{Vector{D},Set{D}, D}) where {D<:AbstractDomain}

Extends Base.rand to (a collection of) domains.

source

julia
Base.rand(itv::Intervals)
Base.rand(itv::Intervals, i)

Return a random value from itv, specifically from the ith interval if i is specified.

source

julia
Base.rand(d::D) where D <: DiscreteDomain

Draw randomly a point in d.

source

julia
Base.rand(fa::FakeAutomaton)

Extends Base.rand. Currently simply returns fa.

source

ConstraintDomains.generate_parameters Function
julia
generate_parameters(d<:AbstractDomain, param)

Generates random parameters based on the domain d and the kind of parameters param.

source