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.


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

mutable struct Between <: ConstraintTrees.Bound

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


  • lower::Float64: Lower bound

  • upper::Float64: Upper bound

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.

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.


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

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

mutable struct EqualTo <: ConstraintTrees.Bound

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


  • equal_to::Float64: Equality bound value
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).


  • 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

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

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.


  • 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

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

struct Tree{X}

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

    a_weights::Array{T, 1},
    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.

    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.

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

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

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.

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

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

) -> ConstraintTrees.Tree{ConstraintTrees.Constraint}

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

izip(f, x, y) -> Any
izip(f, x, y, ::Type{T}) -> Any

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

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

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.

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.

    a_weights::Array{T, 1},
    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.

) -> DataStructures.SortedSet{Any, Base.Order.ForwardOrdering}

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

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.

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

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

) -> Any
) -> Any

Overload of substitute_values for a single constraint.

) -> Any
) -> 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).

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

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

    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.

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

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

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

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

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

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.

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