search

Herb-AI / HerbConstraints.jl

Constraints for Herb.jl
https://herb-ai.github.io/
MIT License
0 stars 0 forks source link

Split up `LocalOrdered` with an order of n symbols into n-1 pairwise `LocalOrdered` constraints #42

Open Whebon opened 1 month ago

Whebon commented 1 month ago

A LocalOrdered constraint with an order of n symbols is responsible for enforcing an "<=" operation on n-1 pairs of nodes. This could be split up into n-1 smaller constraints instead. For example:

path = Vector{Int}()
tree = RuleNode(4, [VarNode(:x), VarNode(:y), VarNode(:z), VarNode(:w)])

#Current implementation: Ordered posts 1 LocalOrdered constraint:
constraint = LocalOrdered(path, tree, [:x, :y, :z, :w])

#Target implementation: Ordered posts n-1 LocalOrdered constraints:
small_constraint1 = LocalOrdered(path, tree, [:x, :y])
small_constraint2 = LocalOrdered(path, tree, [:y, :z])
small_constraint3 = LocalOrdered(path, tree, [:z, :w])

Why is this helpful?

Suppose LocalOrdered(path, tree, [:x, :y]) is already satisfied. Then we don't have to check it when propagating LocalOrdered(path, tree, [:y, :z]).

But in the current implementation, LocalOrdered(path, tree, [:x, :y, :z]) will always first check if VarNode(:x) <= VarNode(:y), which is known to be true after the first check, and then actually propagate VarNode(:y) <= VarNode(:z)

Why is this not helpful?

This doubles the amount of local constraints produced, which arguably causes more overhead than the potential upside