Reference

abstract type Value

Abstract type of all values usable in constraints, including LinearValue and QuadraticValue.

All Values are broadcastable as scalars by default.

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.

substitute_values(x::Value, y::AbstractVector) -> Any
substitute_values(x::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 Constraints and Values.

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 LinearValues and QuadraticValues.

value(x::Union{Value, Real}) -> Union{Value, Real}

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

struct LinearValueT{Float64} <: Value

A shortcut for a LinearValueT over Float64s.

LinearValue(x::Real) -> LinearValueT

Construct a constant-valued LinearValue with a single affine element.

LinearValue(
    x::SparseArrays.SparseVector{Float64}
) -> LinearValue

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

struct LinearValueT{T} <: Value

A representation of a "value" in a linear constrained optimization problem. The value is an affine linear combination of several variables, weighted by coefficients of the parameter type T.

LinearValueTs can be combined additively and multiplied by real-number constants. Multiplying two LinearValueTs yields a quadratic form (in a QuadraticValueT).

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: Coefficients of the variables selected by idxs.

LinearValueT(x::Real) -> LinearValueT{R} where R<:Real

Construct a constant-valued LinearValueT with a single affine element.

LinearValueT(
    x::SparseArrays.SparseVector{T}
) -> LinearValueT

Generalized constructor for LinearValueTs from sparse vectors.

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}, Any}

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.

substitute(x::LinearValueT, y) -> Any

Substitute anything vector-like as variable values into a LinearValueT and return the result.

struct QuadraticValueT{Float64} <: Value

A shortcut for a QuadraticValueT over Float64s.

QuadraticValue(x::LinearValue) -> QuadraticValue

Construct a QuadraticValue that is equivalent to a given LinearValue.

QuadraticValue(x::Real) -> QuadraticValueT

Construct a constant-valued QuadraticValue with a single affine element.

QuadraticValue(
    x::SparseArrays.SparseMatrixCSC{Float64}
) -> QuadraticValue

Shortcut for making a QuadraticValue out of a square sparse matrix.

struct QuadraticValueT{T} <: 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, weighted by coefficients of the parameter type T.

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 LinearValueT, index 0 represents the affine element.

• weights::Vector: Coefficient of the variable pairs selected by idxs.

QuadraticValueT(x::LinearValueT) -> QuadraticValueT

Construct a QuadraticValueT that is equivalent to a given LinearValueT.

QuadraticValueT(x::Real) -> QuadraticValueT{R} where R<:Real

Construct a constant-valued QuadraticValueT with a single affine element.

QuadraticValueT(
    x::SparseArrays.SparseMatrixCSC{T}
) -> QuadraticValue

Generalized constructor for QuadraticValueT from square sparse matrices.

The matrix is force-symmetrized by calculating x' + x.

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}}, Any}

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.

colex_le(, ) -> Any

Internal helper for co-lex ordering of indexes.

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}}, Any}

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.

squared(a::LinearValueT) -> QuadraticValueT

Broadcastable shortcut for multiplying a LinearValueT with itself. Produces a QuadraticValueT.

substitute(x::QuadraticValueT, y) -> Any

Substitute anything vector-like as variable values into the QuadraticValueT and return the result.

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

mutable struct BetweenT{Float64} <: Bound

Shortcut for a Float64-typed interval bound implemented by BetweenT.

Between(x::Real, y::Real) -> BetweenT

Construct a Between bound. Additionally, this checks the order of the values and puts them into a correct order.

mutable struct BetweenT{T} <: Bound

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

Fields

• lower::Any: Lower bound

• upper::Any: Upper bound

abstract type Bound

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

All Bounds are broadcastable as scalars by default.

mutable struct EqualToT{Float64} <: Bound

Shortcut for a Float64-typed equality bound implemented by EqualToT.

EqualTo(x::Real) -> EqualToT

Construct an EqualTo bound.

mutable struct EqualToT{T} <: Bound

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

Fields

• equal_to::Any: Equality bound value

length(x::Bound) -> Int64

Deprecation warning: This is kept for backwards compatibility only, and will be removed in a future release.

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::Value: A value (typically a LinearValue or a QuadraticValue) that describes what the constraint constraints.

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

bound(x::Constraint) -> Union{Nothing, Bound}

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

substitute(x::Constraint, y) -> Constraint

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

substitute_values(x::Constraint, y::AbstractVector) -> Any
substitute_values(
    x::Constraint,
    y::AbstractVector,
    _
) -> Any

Overload of substitute_values for a single constraint.

value(x::Constraint) -> Value

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

Helper type for implementation of merge-related functions.

struct Tree{X}

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

elems(
    x::Tree
) -> DataStructures.SortedDict{Symbol, Union{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.

filter(f, x::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.

filter_leaves(f, x::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).

ifilter(f, x::Tree{T}) -> Any

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

ifilter_leaves(f, x::Tree{T}) -> Any

Combination of ifilter and filter_leaves.

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

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

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

ireduce(op, x; init) -> Any

Indexed version of reduce (internally uses imapreduce).

itraverse(f, x) -> Any

itraverse is to traverse like imap is to map.

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

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.

optional_tree_get(_::Missing, _) -> Missing

Get a key from a tree that is possibly missing.

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

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

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.

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.

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.

A shortcut for the type of the values in ConstraintTree.

struct Tree{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.

collect_variables!(x::Constraint, out)

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

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

collect_variables!(out::Function, x) -> Any

Overload of collect_variables! that calls a given function with all variable indexes found in x.

drop_zeros(x::Tree{T}) -> ConstraintTree

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

Old name for increase_variable_indexes.

Deprecation warning: This will be removed in a future release.

increase_variable_indexes(x, incr::Int64) -> Any

Offset all variable indexes in a structure x by the given increment.

Internally, this uses renumber_variables.

Extensibility note

If you extend the functionality of ConstraintTrees by overloading increase_variable_indexes, consider instead providing the overload for renumber_variables which grants more functionality, mainly variable pruning.

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.

renumber_variables(mapping::Function, x) -> Any

An overload of renumber_variables that allows mapping to be a single-parameter Function.

renumber_variables(x::Tree{T}, mapping) -> ConstraintTree

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.

The mapping is assumed to be an array-like object (i.e., it must support getindex, which is used to retrieve the new index for each original variable index).

substitute(x::ConstraintTree, y::AbstractVector) -> Any

Substitute variable values from y into the constraint tree's constraint's values, getting a tree with modified constraints.

In a typical application, this can be used together with prune_variables to fix a subset of variables to known values and effectively remove them from the problem.

Cf. substitute_values, which creates a tree of "plain" values with no constraints.

substitute_values(x::Tree, y::AbstractVector) -> Any
substitute_values(
    x::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).

To preserve the constraints in the tree, use substitute.

Old name for variable_count.

Deprecation warning: This will be removed in a future release.

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

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

variable_count(x::ConstraintTree) -> Int64

Find the expected count of variables in a ConstraintTree.

variable_count(x::Constraint) -> Int64

Find the expected count of variables in a Constraint.

variable_count(x::LinearValueT) -> Int64

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

variable_count(x::QuadraticValueT) -> Int64

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

variables(; ...)
variables(weight; keys, bounds)

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

The individual bounds should be subtypes of Bound, or nothing (which is the default). The bounds are broadcasted; to pass a single bound for all variables, one can use e.g. bounds = EqualTo(0).

variables_for(makebound, ts::Tree) -> Any
variables_for(makebound, ts::Tree, weight) -> 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.

variables_ifor(makebound, ts::Tree) -> Any
variables_ifor(makebound, ts::Tree, weight) -> Any

Like variables_for but the makebound function also receives a path to the variable, as with imap.

default_pretty_var(i::Int64) -> String

Internal helper for prettyprinting variable contributions; default value of format_variable keyword argument in pretty.

If there should be multiplication operators, the implementation format_variable is supposed to prefix the variable contribution. This should not print anything for the zero "affine" variable.

pretty(x; kwargs...) -> Any

Pretty-print a given object via other overloads of pretty, defaulting the output stream to standard output.

pretty(io::IO, x; kwargs...) -> Union{Nothing, Bool}

Default implementation of pretty defaults to Base.show.

pretty(
    io::IO,
    x::BetweenT;
    in_interval_sign,
    format_bound_value,
    kwargs...
)

Pretty-print an interval bound into the io.

pretty(io::IO, x::Bound; default_bound_separator, kwargs...)

Default pretty-printing of a Bound. Overloads that print bounds should expect that they are ran right after printing of the Values, on the same line.

pretty(
    io::IO,
    x::Constraint;
    kwargs...
) -> Union{Nothing, Bool}

Pretty-print a constraint into the io.

pretty(
    io::IO,
    x::EqualToT;
    equal_to_sign,
    format_bound_value,
    kwargs...
)

Pretty-print an equality bound into the io.

pretty(
    io::IO,
    x::LinearValueT;
    format_coefficient,
    format_variable,
    plus_sign,
    zero_value,
    kwargs...
)

Pretty-print a linear value into the io.

pretty(
    io::IO,
    x::QuadraticValueT;
    format_coefficient,
    format_variable,
    plus_sign,
    zero_value,
    kwargs...
)

Pretty-print a quadratic value into the io.

pretty(io::IO, x::Tree; kwargs...)

Pretty-print a nested tree into the io. This is the only overload of pretty that is allowed to break lines.

The printing assumes a Unicode-capable stdout by default; the formatting can be customized via keyword arguments (see other overloads of pretty and pretty_tree).

pretty_tree(
    io::IO,
    x,
    ctxt0::Tuple,
    pfx0::String,
    pfx::String;
    leaf_separator,
    kwargs...
)

Overload of pretty_tree for anything except Trees – this utilizes pretty to finish a line with the "contents" of the tree leaf.

pretty_tree(
    io::IO,
    x::Tree,
    ctxt0::Tuple,
    pfx0::String,
    pfx::String;
    format_label,
    singleton_branch,
    first_branch,
    middle_branch,
    last_branch,
    child_first_indent,
    child_indent,
    lastchild_first_indent,
    lastchild_indent,
    kwargs...
)

Internal helper for recursive prettyprinting of tree structures. Adds a relatively legible Unicode scaffolding to highlight the tree structure. The scaffolding can be customized via keyword arguments (which are passed here from pretty).

Specifically, format_label argument can be used convert a tuple with the "path" in the tree (as with e.g. imap) into a suitable tree branch label.