Dynamic Programming Tree Solver

Dynamic Programming Tree Solver

Merge the event queues within the tree by sorting arrays.

Compared to previous versions, all weighting (λ and μ) is templated; thus we only need one implementation and the compiler will do the rest.

tree_dp(y, t::Tree, λ [, μ = 1.0])

Perform the dynamic programming algorithm on y and return the optimized x.

The edge weighting λ should be either a constant (e.g. Float64) or a callable such that λ(i) returns the weight of the edge (i, t.parent[i]); for λ(t.root) it might return anything but not causean error.

tree_dp!(x, y, t, λ, μ [,mem])

Like tree_dp but do not allocate an output buffer for x.

If mem::TreeDPMem is provided, no additional allocations will be needed.

Contains all memory needed for tree_dp!.

reset!(mem::TreeDPMem, t::Tree)

Re-initialize the memory given the new tree, i.e.

1. Assert that mem has the required size for t.
2. Compute processing order.
3. Initialize queues to fit t.

dual!(α, [, x, y], post_order, parent)

Compute the tree dual and store it in α.

gap_vec!(γ, dif, x, y, D, Dt, α, c)

Compute the gap vector (modifies dif and x) and stores it in γ.

gap_vec!(γ, x, α, g [, c = 1.0])

Compute the duality gap: for each edge e we set γ[e] to the difference of the edge cost $\lambda_{ij} |x_i - x_j|$ and the linear approximation via the dual $α_{ij}(x_i - x_j)$.

The graph g needs to implement a method enumerate_edges(::Function, g).

If provided, the result is multiplied by c.

primal_from_dual!(y, α, graph)

Similar to primal_from_dual but store the result in y.

primal_from_dual(y, α, graph)

If $D$ is the oriented incidence matrix of graph, return $y + D'*α$.

wolfe_gap_step(x0, α0, x1, α1)

Optimal gap step width according to Wolfe's condition, i.e. compute the optimal step width $θ ∈ [0, 1]$ to walk from (x0, α0) to (x1, α1) such that the sum(gap_vec) will be minimized.

Set of double ended queues (DeQue) in a tree. Initially all leaf nodes have its own queue. Children's queues will be merged into the parent node.

Range(start, stop)

A range in a Vector. In our algorithm is is used for the nodes of Queues of Events.