ConstraintTrees.ConstraintTrees — Module

Package ConstraintTrees.jl provides a simple data structure ConstraintTree for organizing the contents of linear and quadratic constrained optimization problems. As a main goal, it abstracts over the distinction between constraints and variables, allowing much tidier representation for many kinds of complex constraint systems.

The primary purpose of ConstraintTrees.jl is to work with COBREXA.jl; but the package is otherwise completely independent, lightweight, dependency-free and usecase-agnostic. Generally, it is intended to be used with JuMP and the documentation uses JuMP for demonstrations, but any other solver framework will do just as well.

The package is structured as follows:

  • There is no representation for variables in the model; instead, values depend on anonymous numbered variables, and, if suitable, special named values may "implicitly" serve as representations for variables. This assumption erases the distinction between a "simple" variable and a complex derived linear combination, allowing more freedom in model construction.
  • Variables may be combined into LinearValues and QuadraticValues, which are affine combinations and quadratic-affine combinations (respecitively) of values of some selected variables.
  • Values may be bounded to an interval or exact value using a Constraint
  • A collection of named Constraints is called a ConstraintTree; it behaves mostly as a specialized Symbol-keyed dictionary.
  • ConstraintTrees can be very easily organized into subdirectories, combined and made independent on each other using operators ^, *, and + – this forms the basis of the "tidy" algebra of constraints.
  • A variable assignment, which is typically the "solution" for a given constraint tree, can be combined with a ConstraintTree to create a "value tree" via substitute_values, which enables browsing of the optimization results in the very same structure as the input ConstraintTree.

You can follow the examples in documentation and the docstrings of package contents for more details.

ConstraintTrees.MaybeBound — Type

Shortcut for all possible Bounds including the "empty" bound that does not constraint anything (represented by nothing).

ConstraintTrees.Between — Type
mutable struct Between <: ConstraintTrees.Bound

Representation of an "interval" bound; consisting of lower and upper bound value.

Fields

  • lower::Float64: Lower bound

  • upper::Float64: Upper bound

ConstraintTrees.Bound — Type
abstract type Bound

Abstract type of all bounds usable in constraints, including Between and EqualTo.

To make broadcasting work, length(::Bound) = 1 has been extended. This allows functions like variables to broadcast a single supplied bound across all constraints.

ConstraintTrees.Constraint — Type
mutable struct Constraint

A representation of a single constraint that may limit the given value by a specific Bound.

Constraints without a bound (nothing in the bound field) are possible; these have no impact on the optimization problem but the associated value becomes easily accessible for inspection and building other constraints.

Fields

  • value::ConstraintTrees.Value: A value (typically a LinearValue or a QuadraticValue) that describes what the constraint constraints.

  • bound::Union{Nothing, ConstraintTrees.Bound}: A bound that the value must satisfy. Should be a subtype of MaybeBound: Either nothing if there's no bound, or e.g. EqualTo, Between or similar structs.

ConstraintTrees.ConstraintTree — Type
struct Tree{ConstraintTrees.Constraint}

A hierarchical tree of many constraints that together describe a constrained system. The tree may recursively contain other trees in a directory-like structure, which contain Constraints as leaves.

Members of the constraint tree are accessible via the record dot syntax as properties; e.g. a constraint labeled with :abc in a constraint tree t may be accessed as t.abc and as t[:abc], and can be found while iterating through elems(t).

Constructing the constraint trees

Use operator ^ to put a name on a constraint to convert it into a single element ConstraintTree:

x = :my_constraint ^ Constraint(LinearValue(...), 1.0)
dir = :my_constraint_dir ^ x

dir.my_constraint_dir.my_constraint.bound   # returns 1.0

Use operator * to glue two constraint trees together while sharing the variable indexes specified by the contained LinearValues and QuadraticValues.

my_constraints = :some_constraints ^ Constraint(...) * :more_constraints ^ Constraint(...)

Use operator + to glue two constraint trees together without sharing of any variables. The operation will renumber the variables in the trees so that the sets of variable indexes used by either tree are completely disjunct, and then glue the trees together as with *:

two_independent_systems = my_system + other_system

Variable sharing limitations

Because of the renumbering, you can not easily use constraints and values from the values before the addition in the constraint tree that is the result of the addition. There is no check against that – the resulting ConstraintTree will be valid, but will probably describe a different optimization problem than you intended.

As a rule of thumb, avoid necessary parentheses in expressions that work with the constraint trees: While t1 * t2 + t3 might work just as intended, t1 * (t2 + t3) is almost certainly wrong because the variables in t1 that are supposed to connect to variables in either of t2 and t3 will not connect properly because of renumbering of both t2 and t3. If you need to construct a tree like that, do the addition first, and construct the t1 after that, based on the result of the addition.

ConstraintTrees.EqualTo — Type
mutable struct EqualTo <: ConstraintTrees.Bound

Representation of an "equality" bound; contains the single "equal to this" value.

Fields

  • equal_to::Float64: Equality bound value
ConstraintTrees.LinearValue — Type
struct LinearValue <: ConstraintTrees.Value

A representation of a "value" in a linear constrained optimization problem. The value is an affine linear combination of several variables.

LinearValues can be combined additively and multiplied by real-number constants.

Multiplying two LinearValues yields a quadratic form (in a QuadraticValue).

Fields

  • idxs::Vector{Int64}: Indexes of the variables used by the value. The indexes must always be sorted in strictly increasing order. The affine element has index 0.
  • weights::Vector{Float64}: Coefficients of the variables selected by idxs.
ConstraintTrees.LinearValue — Method
LinearValue(
    x::SparseArrays.SparseVector{Float64}
) -> ConstraintTrees.LinearValue

Shortcut for making a LinearValue out of a linear combination defined by the SparseVector.

ConstraintTrees.QuadraticValue — Type
struct QuadraticValue <: ConstraintTrees.Value

A representation of a quadratic form in the constrained optimization problem. The QuadraticValue is an affine quadratic combination (i.e., a polynomial of maximum degree 2) over the variables.

QuadraticValues can be combined additively and multiplied by real-number constants. The cleanest way to construct a QuadraticValue is to multiply two LinearValues.

Fields

  • idxs::Vector{Tuple{Int64, Int64}}: Indexes of variable pairs used by the value. The indexes must always be sorted in strictly co-lexicographically increasing order, and the second index must always be greater than or equal to the first one. (Speaking in matrix terms, the indexing follows the indexes in an upper triangular matrix by columns.)

    As an outcome, the second index of the last index pair can be used as the upper bound of all variable indexes.

    As with LinearValue, index 0 represents the affine element.

  • weights::Vector{Float64}: Coefficient of the variable pairs selected by idxs.
ConstraintTrees.QuadraticValue — Method
QuadraticValue(
    x::SparseArrays.SparseMatrixCSC{Float64}
) -> ConstraintTrees.QuadraticValue

Shortcut for making a QuadraticValue out of a square sparse matrix. The matrix is force-symmetrized by calculating x' + x.

ConstraintTrees.Tree — Type
struct Tree{X}

A base "labeled tree" structure. Supports many interesting operations such as merging.

ConstraintTrees.add_sparse_linear_combination — Method
add_sparse_linear_combination(
    a_idxs::Vector{Int64},
    a_weights::Array{T, 1},
    b_idxs::Vector{Int64},
    b_weights::Array{T, 1}
) -> Tuple{Vector{Int64}, Vector}

Helper function for implementing LinearValue-like objects. Given "sparse" representations of linear combinations, it computes a "merged" linear combination of 2 values added together.

Zeroes are not filtered out.

ConstraintTrees.add_sparse_quadratic_combination — Method
add_sparse_quadratic_combination(
    a_idxs::Vector{Tuple{Int64, Int64}},
    a_weights::Array{T, 1},
    b_idxs::Vector{Tuple{Int64, Int64}},
    b_weights::Array{T, 1}
) -> Tuple{Vector{Tuple{Int64, Int64}}, Vector}

Helper function for implementing QuadraticValue-like objects. Given 2 sparse representations of quadratic combinations, it computes a "merged" one with the values of both added together.

Zeroes are not filtered out.

ConstraintTrees.bound — Method
bound(
    x::ConstraintTrees.Constraint
) -> Union{Nothing, ConstraintTrees.Bound}

Simple accessor for getting out the bound from the constraint that can be used for broadcasting (as opposed to the dot-field access).

ConstraintTrees.collect_variables! — Method
collect_variables!(x::ConstraintTrees.Constraint, out)

Push all variable indexes found in x to the out container.

(The container needs to support the standard push!.)

ConstraintTrees.drop_zeros — Method
drop_zeros(
    x::ConstraintTrees.Tree{T}
) -> ConstraintTrees.Tree{ConstraintTrees.Constraint}

Remove variable references from all Values in the given object (usually a ConstraintTree) where the variable weight is exactly zero.

ConstraintTrees.elems — Method
elems(
    x::ConstraintTrees.Tree
) -> DataStructures.SortedDict{Symbol, Union{ConstraintTrees.Tree{X}, X}} where X

Get the elements dictionary out of the Tree. This is useful for getting an iterable container for working with many items at once.

Also, because of the overload of getproperty for Tree, this serves as a simpler way to get the elements without an explicit use of getfield.

ConstraintTrees.filter — Method
filter(f, x::ConstraintTrees.Tree{T}) -> Any

Filter all branches and leaves in a tree, leaving only the ones where f returns true.

Note that the branches are passed to f as well. Use filter_leaves to only work with the leaf values.

ConstraintTrees.filter_leaves — Method
filter_leaves(f, x::ConstraintTrees.Tree{T}) -> Any

Like filter but the filtering predicate function f only receives the leaf values (i.e., no intermediate sub-trees).

In turn, the result will retain the whole subtree structure (even if empty).

ConstraintTrees.ifilter — Method
ifilter(f, x::ConstraintTrees.Tree{T}) -> Any

Like filter but the filtering predicate function also receives the "path" in the tree.

ConstraintTrees.imap — Method
imap(f, x) -> Any
imap(f, x, ::Type{T}) -> Any

Like map, but keeping the "index" path and giving it to the function as the first parameter. The "path" in the tree is reported as a tuple of symbols.

ConstraintTrees.imapreduce — Method
imapreduce(f, op, x; init) -> Any

Like mapreduce but reporting the "tree directory path" where the reduced elements occur, like with imap. (Single elements from different directory paths are not reduced together.)

ConstraintTrees.incr_var_idxs — Method
incr_var_idxs(
    x::ConstraintTrees.LinearValue,
    incr::Int64
) -> ConstraintTrees.LinearValue

Offset all variable indexes in a LinearValue by the given increment.

ConstraintTrees.incr_var_idxs — Method
incr_var_idxs(
    x::ConstraintTrees.Tree{ConstraintTrees.Constraint},
    incr::Int64
) -> ConstraintTrees.Tree{ConstraintTrees.Constraint}

Offset all variable indexes in a ConstraintTree by the given increment.

ConstraintTrees.izip — Method
izip(f, x, y) -> Any
izip(f, x, y, ::Type{T}) -> Any

Index-reporting variant of zip (see imap for reference).

ConstraintTrees.map — Method
map(f, x) -> Any
map(f, x, ::Type{T}) -> Any

Run a function over everything in the tree. The resulting tree will contain elements of type specified by the 3rd argument. (This needs to be specified explicitly, because the typesystem generally cannot guess the universal type correctly.)

Note this is a specialized function specific for Trees that behaves differently from Base.map.

ConstraintTrees.mapreduce — Method
mapreduce(f, op, x; init) -> Any

Reduce all items in a Tree. As with Base.reduce, the reduction order is not guaranteed, and the initial value may be used any number of times.

Note this is a specialized function specific for Trees that behaves differently from Base.mapreduce.

ConstraintTrees.merge — Method
merge(f, x, y) -> Any
merge(f, x, y, ::Type{T}) -> Any

Run a function over the values in the merge of all paths in the trees (currently there is support for 2 and 3 trees). This is an "outer join" equivalent of zip. Missing elements are replaced by missing in the function call parameters, and the function may return missing to omit elements.

Note this is a specialized function specific for Trees that behaves differently from Base.merge.

ConstraintTrees.multiply_sparse_linear_combination — Method
multiply_sparse_linear_combination(
    a_idxs::Vector{Int64},
    a_weights::Array{T, 1},
    b_idxs::Vector{Int64},
    b_weights::Array{T, 1}
) -> Tuple{Vector{Tuple{Int64, Int64}}, Vector}

Helper function for multiplying two LinearValue-like objects to make a QuadraticValue-like object. This computes and merges the product.

Zeroes are not filtered out.

ConstraintTrees.optional_tree_keys — Method
optional_tree_keys(
    _::Missing
) -> DataStructures.SortedSet{Any, Base.Order.ForwardOrdering}

Get a sorted set of keys from a tree that is possibly missing.

ConstraintTrees.preduce — Method
preduce(op, xs; init, stack_type) -> Any

An alternative of Base.reduce which does a "pairwise" reduction in the shape of a binary merge tree, like in mergesort. In general this is a little more complex, but if the reduced value "grows" with more elements added (such as when adding a lot of LinearValues together), this is able to prevent a complexity explosion by postponing "large" reducing operations as much as possible.

In the specific case with adding lots of LinearValues and QuadraticValues together, this effectively squashes the reduction complexity from something around O(n^2) to O(n) (with a little larger constant factor.

ConstraintTrees.reduce — Method
reduce(op, x; init) -> Any

Like mapreduce but the mapped function is identity.

To avoid much type suffering, the operation should ideally preserve the type of its arguments. If you need to change the type, you likely want to use mapreduce.

Note this is a specialized function specific for Trees that behaves differently from Base.reduce.

ConstraintTrees.renumber_variables — Method
renumber_variables(
    x::ConstraintTrees.Tree{T},
    mapping
) -> ConstraintTrees.Tree{ConstraintTrees.Constraint}

Renumber all variables in an object (such as ConstraintTree). The new variable indexes are taken from the mapping parameter at the index of the old variable's index.

This does not run any consistency checks on the result; the mapping must therefore be monotonically increasing, and the zero index must map to itself, otherwise invalid Values will be produced.

ConstraintTrees.substitute — Method
substitute(
    x::ConstraintTrees.Constraint,
    y
) -> ConstraintTrees.Constraint

Substitute anything vector-like as variables into the constraint's value, producing a constraint with the new value.

ConstraintTrees.substitute_values — Function
substitute_values(
    x::ConstraintTrees.Constraint,
    y::AbstractVector
) -> Any
substitute_values(
    x::ConstraintTrees.Constraint,
    y::AbstractVector,
    _
) -> Any

Overload of substitute_values for a single constraint.

ConstraintTrees.substitute_values — Method
substitute_values(
    x::ConstraintTrees.Tree,
    y::AbstractVector
) -> Any
substitute_values(
    x::ConstraintTrees.Tree,
    y::AbstractVector,
    ::Type{T}
) -> Any

Substitute variable values from y into the constraint tree's constraint's values, getting a tree of "solved" constraint values for the given variable assignment.

The third argument forces the output type (it is forwarded to map). The type gets defaulted from eltype(y).

ConstraintTrees.traverse — Method
traverse(f, x) -> Any

Like map, but discards the results, thus relying only on the side effects of f.

Technically the name should be for, but that's a Julia keyword.

ConstraintTrees.value — Method
value(
    x::ConstraintTrees.Constraint
) -> ConstraintTrees.Value

Simple accessor for getting out the value from the constraint that can be used for broadcasting (as opposed to the dot-field access).

ConstraintTrees.value — Method
value(
    x::Union{ConstraintTrees.Value, Real}
) -> Union{ConstraintTrees.Value, Real}

Returns any Real- or Value-typed x. This is a convenience overload; typically one enjoys this more when extracting values from Constraints.

ConstraintTrees.var_count — Method
var_count(x::ConstraintTrees.LinearValue) -> Int64

Find the expected count of variables in a LinearValue. (This is a O(1) operation, relying on the ordering of the indexes.)

ConstraintTrees.var_count — Method
var_count(x::ConstraintTrees.QuadraticValue) -> Int64

Find the expected count of variables in a QuadraticValue. (This is a O(1) operation, relying on the co-lexicographical ordering of indexes.)

ConstraintTrees.variable — Method
variable(; bound, idx) -> ConstraintTrees.Constraint

Allocate a single unnamed variable, returning a Constraint with an optionally specified bound.

ConstraintTrees.variables — Method
variables(; keys, bounds)

Make a trivial constraint system that creates variables with indexes in range 1:length(keys) named in order as given by keys.

Parameter bounds is either nothing for creating variables without bounds assigned to them, a single bound for creating variables with the same constraint assigned to them all, or an iterable object of same length as keys with individual bounds for each variable in the same order as keys.

The individual bounds should be subtypes of Bound, or nothing. To pass a single bound for all variables, use e.g. bounds = EqualTo(0).

ConstraintTrees.variables_for — Method
variables_for(makebound, ts::ConstraintTrees.Tree) -> Any

Allocate a variable for each item in a constraint tree (or any other kind of tree) and return a ConstraintTree with variables bounded by the makebound function, which converts a given tree element's value into a bound for the corresponding variable.

ConstraintTrees.zip — Method
zip(f, x, y) -> Any
zip(f, x, y, ::Type{T}) -> Any

Run a function over the values in the intersection of paths in several trees (currently there is support for 2 and 3 trees). This is an "inner join" – all extra elements are ignored. "Outer join" can be done via merge.

As with map, the inner type of the resulting tree must be specified by the last parameter..

Note this is a specialized function specific for Trees that behaves differently from Base.zip.