`ConstraintTrees.ConstraintTrees`

— ModulePackage `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
`LinearValue`

s and`QuadraticValue`

s, 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
`Constraint`

s is called a`ConstraintTree`

; it behaves mostly as a specialized`Symbol`

-keyed dictionary. `ConstraintTree`

s 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.ConstraintTreeElem`

— TypeA shortcut for the type of the values in `ConstraintTree`

.

`ConstraintTrees.MaybeBound`

— TypeShortcut for all possible `Bound`

s including the "empty" bound that does not constraint anything (represented by `nothing`

).

`ConstraintTrees.OptionalTree`

— TypeHelper type for implementation of `merge`

-related functions.

`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`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 `Constraint`

s 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 `LinearValue`

s and `QuadraticValue`

s.

`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.

`LinearValue`

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

Multiplying two `LinearValue`

s 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::Real) -> ConstraintTrees.LinearValue
```

Construct a constant `LinearValue`

with a single affine element.

`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.

`QuadraticValue`

s can be combined additively and multiplied by real-number constants. The cleanest way to construct a `QuadraticValue`

is to multiply two `LinearValue`

s.

**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::ConstraintTrees.LinearValue
) -> ConstraintTrees.QuadraticValue
```

Construct a `QuadraticValue`

that is equivalent to a given `LinearValue`

.

`ConstraintTrees.QuadraticValue`

— Method```
QuadraticValue(x::Real) -> ConstraintTrees.QuadraticValue
```

Construct a constant `QuadraticValue`

with a single affine element.

`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.Value`

— Type`abstract type Value`

Abstract type of all values usable in constraints, including `LinearValue`

and `QuadraticValue`

.

`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.colex_le`

— Method```
colex_le(, ) -> Any
```

Internal helper for co-lex ordering of indexes.

`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 `Value`

s 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.ifilter_leaves`

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

Combination of `ifilter`

and `filter_leaves`

.

`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`ConstraintTrees.imerge`

— Method`ConstraintTrees.incr_var_idx`

— Method```
incr_var_idx(x::Int64, incr::Int64) -> Int64
```

Internal helper for manipulating variable indices.

`ConstraintTrees.incr_var_idxs`

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

Offset all variable indexes in a `ConstraintTree`

by the given increment.

`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.QuadraticValue,
incr::Int64
) -> ConstraintTrees.QuadraticValue
```

Offset all variable indexes in a `QuadraticValue`

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.ireduce`

— Method```
ireduce(op, x; init) -> Any
```

Indexed version of `reduce`

(internally uses `imapreduce`

).

`ConstraintTrees.itraverse`

— Method`ConstraintTrees.izip`

— Method`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 `Tree`

s that behaves differently from `Base.map`

.

`ConstraintTrees.mapreduce`

— Method`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 `Tree`

s 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_get`

— Method```
optional_tree_get(_::Missing, _) -> Missing
```

Get a key from a tree that is possibly `missing`

.

`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 `LinearValue`

s 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 `LinearValue`

s and `QuadraticValue`

s together, this effectively squashes the reduction complexity from something around `O(n^2)`

to `O(n)`

(with a little larger constant factor.

`ConstraintTrees.prune_variables`

— Method```
prune_variables(x) -> Any
```

Prune the unused variable indexes from an object `x`

(such as a `ConstraintTree`

).

This first runs `collect_variables!`

to determine the actual used variables, then calls `renumber_variables`

to create a renumbered object.

`ConstraintTrees.reduce`

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

Like `mapreduce`

but the mapped function is identity.

To avoid much type suffering, the `op`

eration 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 `Tree`

s 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 `Value`

s will be produced.

`ConstraintTrees.squared`

— Method```
squared(
a::ConstraintTrees.LinearValue
) -> ConstraintTrees.QuadraticValue
```

Broadcastable shortcut for multiplying a `LinearValue`

with itself. Produces a `QuadraticValue`

.

`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`

— Method```
substitute(x::ConstraintTrees.LinearValue, y) -> Any
```

Substitute anything vector-like as variable values into a `LinearValue`

and return the result.

`ConstraintTrees.substitute`

— Method```
substitute(x::ConstraintTrees.QuadraticValue, y) -> Any
```

Substitute anything vector-like as variable values into the `QuadraticValue`

and return the result.

`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`

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

Substutite a value into a `Value`

-typed `x`

. This is a convenience overload for the purpose of having `substitute_values`

to run on both `Constraint`

s and `Value`

s.

`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.sum`

— Method```
sum(xs; init) -> Any
```

Alias for `preduce`

that uses `+`

as the operation.

Not as versatile as the `sum`

from Base, but much faster for growing values like `LinearValue`

s and `QuadraticValue`

s.

`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 `Constraint`

s.

`ConstraintTrees.var_count`

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

Find the expected count of variables in a `Constraint`

.

`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.var_count`

— Method```
var_count(
x::ConstraintTrees.Tree{ConstraintTrees.Constraint}
) -> Int64
```

Find the expected count of variables in a `ConstraintTree`

.

`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.variables_ifor`

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

Like `variables_for`

but the `makebound`

function also receives a path to the variable, as with `imap`

.

`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 `Tree`

s that behaves differently from `Base.zip`

.