Reference
Values
ConstraintTrees.Value
— Typeabstract type Value
Abstract type of all values usable in constraints, including LinearValue
and QuadraticValue
.
ConstraintTrees.preduce
— Methodpreduce(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.substitute_values
— Functionsubstitute_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.sum
— Methodsum(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.value
— Methodvalue(
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.
Linear and affine values
ConstraintTrees.LinearValue
— Typestruct 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 byidxs
.
ConstraintTrees.LinearValue
— MethodLinearValue(x::Real) -> ConstraintTrees.LinearValue
Construct a constant LinearValue
with a single affine element.
ConstraintTrees.LinearValue
— MethodLinearValue(
x::SparseArrays.SparseVector{Float64}
) -> ConstraintTrees.LinearValue
Shortcut for making a LinearValue
out of a linear combination defined by the SparseVector
.
ConstraintTrees.add_sparse_linear_combination
— Methodadd_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.substitute
— Methodsubstitute(x::ConstraintTrees.LinearValue, y) -> Any
Substitute anything vector-like as variable values into a LinearValue
and return the result.
Quadratic values
ConstraintTrees.QuadraticValue
— Typestruct 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
, index0
represents the affine element.
weights::Vector{Float64}
: Coefficient of the variable pairs selected byidxs
.
ConstraintTrees.QuadraticValue
— MethodQuadraticValue(
x::ConstraintTrees.LinearValue
) -> ConstraintTrees.QuadraticValue
Construct a QuadraticValue
that is equivalent to a given LinearValue
.
ConstraintTrees.QuadraticValue
— MethodQuadraticValue(x::Real) -> ConstraintTrees.QuadraticValue
Construct a constant QuadraticValue
with a single affine element.
ConstraintTrees.QuadraticValue
— MethodQuadraticValue(
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.add_sparse_quadratic_combination
— Methodadd_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.colex_le
— Methodcolex_le(, ) -> Any
Internal helper for co-lex ordering of indexes.
ConstraintTrees.multiply_sparse_linear_combination
— Methodmultiply_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.squared
— Methodsquared(
a::ConstraintTrees.LinearValue
) -> ConstraintTrees.QuadraticValue
Broadcastable shortcut for multiplying a LinearValue
with itself. Produces a QuadraticValue
.
ConstraintTrees.substitute
— Methodsubstitute(x::ConstraintTrees.QuadraticValue, y) -> Any
Substitute anything vector-like as variable values into the QuadraticValue
and return the result.
Constraints
Bounds
ConstraintTrees.MaybeBound
— TypeShortcut for all possible Bound
s including the "empty" bound that does not constraint anything (represented by nothing
).
ConstraintTrees.Between
— Typemutable struct Between <: ConstraintTrees.Bound
Representation of an "interval" bound; consisting of lower and upper bound value.
Fields
lower::Float64
: Lower boundupper::Float64
: Upper bound
ConstraintTrees.Bound
— Typeabstract 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.EqualTo
— Typemutable struct EqualTo <: ConstraintTrees.Bound
Representation of an "equality" bound; contains the single "equal to this" value.
Fields
equal_to::Float64
: Equality bound value
Constrained values
ConstraintTrees.Constraint
— Typemutable 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 aLinearValue
or aQuadraticValue
) that describes what the constraint constraints.bound::Union{Nothing, ConstraintTrees.Bound}
: A bound that thevalue
must satisfy. Should be a subtype ofMaybeBound
: Eithernothing
if there's no bound, or e.g.EqualTo
,Between
or similar structs.
ConstraintTrees.bound
— Methodbound(
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.substitute
— Methodsubstitute(
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
— Functionsubstitute_values(
x::ConstraintTrees.Constraint,
y::AbstractVector
) -> Any
substitute_values(
x::ConstraintTrees.Constraint,
y::AbstractVector,
_
) -> Any
Overload of substitute_values
for a single constraint.
ConstraintTrees.value
— Methodvalue(
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).
Labeled trees
ConstraintTrees.OptionalTree
— TypeHelper type for implementation of merge
-related functions.
ConstraintTrees.Tree
— Typestruct Tree{X}
A base "labeled tree" structure. Supports many interesting operations such as merging.
ConstraintTrees.elems
— Methodelems(
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
— Methodfilter(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
— Methodfilter_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
— Methodifilter(f, x::ConstraintTrees.Tree{T}) -> Any
Like filter
but the filtering predicate function also receives the "path" in the tree.
ConstraintTrees.ifilter_leaves
— Methodifilter_leaves(f, x::ConstraintTrees.Tree{T}) -> Any
Combination of ifilter
and filter_leaves
.
ConstraintTrees.imap
— Methodimap(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
— Methodimapreduce(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.imerge
— Methodimerge(f, x, y) -> Any
imerge(f, x, y, ::Type{T}) -> Any
ConstraintTrees.ireduce
— Methodireduce(op, x; init) -> Any
Indexed version of reduce
(internally uses imapreduce
).
ConstraintTrees.itraverse
— MethodConstraintTrees.izip
— Methodizip(f, x, y) -> Any
izip(f, x, y, ::Type{T}) -> Any
ConstraintTrees.map
— Methodmap(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
— Methodmapreduce(f, op, x; init) -> Any
Reduce all items in a Tree
. As with Base.reduce
, the reduction order is not guaranteed, and the init
ial value may be used any number of times.
Note this is a specialized function specific for Tree
s that behaves differently from Base.mapreduce
.
ConstraintTrees.merge
— Methodmerge(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.optional_tree_get
— Methodoptional_tree_get(_::Missing, _) -> Missing
Get a key from a tree that is possibly missing
.
ConstraintTrees.optional_tree_keys
— Methodoptional_tree_keys(
_::Missing
) -> DataStructures.SortedSet{Any, Base.Order.ForwardOrdering}
Get a sorted set of keys from a tree that is possibly missing
.
ConstraintTrees.reduce
— Methodreduce(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.traverse
— Methodtraverse(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.zip
— Methodzip(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
.
Constraint trees
ConstraintTrees.ConstraintTreeElem
— TypeA shortcut for the type of the values in ConstraintTree
.
ConstraintTrees.ConstraintTree
— Typestruct 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.collect_variables!
— Methodcollect_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
— Methoddrop_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.incr_var_idx
— Methodincr_var_idx(x::Int64, incr::Int64) -> Int64
Internal helper for manipulating variable indices.
ConstraintTrees.incr_var_idxs
— Methodincr_var_idxs(
x::ConstraintTrees.Constraint,
incr::Int64
) -> ConstraintTrees.Constraint
Offset all variable indexes in a ConstraintTree
by the given increment.
ConstraintTrees.incr_var_idxs
— Methodincr_var_idxs(
x::ConstraintTrees.LinearValue,
incr::Int64
) -> ConstraintTrees.LinearValue
Offset all variable indexes in a LinearValue
by the given increment.
ConstraintTrees.incr_var_idxs
— Methodincr_var_idxs(
x::ConstraintTrees.QuadraticValue,
incr::Int64
) -> ConstraintTrees.QuadraticValue
Offset all variable indexes in a QuadraticValue
by the given increment.
ConstraintTrees.incr_var_idxs
— Methodincr_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.prune_variables
— Methodprune_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.renumber_variables
— Methodrenumber_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.substitute_values
— Methodsubstitute_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.var_count
— Methodvar_count(x::ConstraintTrees.Constraint) -> Int64
Find the expected count of variables in a Constraint
.
ConstraintTrees.var_count
— Methodvar_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
— Methodvar_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
— Methodvar_count(
x::ConstraintTrees.Tree{ConstraintTrees.Constraint}
) -> Int64
Find the expected count of variables in a ConstraintTree
.
ConstraintTrees.variable
— Methodvariable(; bound, idx) -> ConstraintTrees.Constraint
Allocate a single unnamed variable, returning a Constraint with an optionally specified bound
.
ConstraintTrees.variables
— Methodvariables(; 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
— Methodvariables_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
— Methodvariables_ifor(makebound, ts::ConstraintTrees.Tree) -> Any
Like variables_for
but the makebound
function also receives a path to the variable, as with imap
.