GitHub

Reference

Values

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.

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

source

Linear and affine values

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

source

Quadratic values

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

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

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

source

Constraints

Bounds

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

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

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

Constrained values

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.

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

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

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

source

Labeled trees

ConstraintTrees.Tree — Type
struct Tree{X}

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

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

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

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

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

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

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

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

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

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

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

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

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

source

Constraint trees

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.

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

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

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

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

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

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

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

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

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

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

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

source

Trees for storing solved values