Dynamic programming

Subset dynamic programming searches combinations of tensor subsets; interval dynamic programming selects a parenthesization for a fixed leaf order.

On this page

Two forms of dynamic programming

Dynamic programming (DP) solves small subproblems first, then uses their results to solve larger ones. ArcTN defines states in two ways:

Method	What one state represents	Search space
`optimal_dp`	A connected tensor subset	Permitted binary splits of that subset
`order_dp`	A contiguous interval in a given leaf order	Binary parenthesizations preserving the leaf order

The methods use different states: optimal_dp is subset DP, while order_dp is interval DP.

Subset dynamic programming

Let $C(S)$ be the minimum cost of contracting tensor set $S$ . Let $\mathcal P(S)$ denote the permitted splits in the current search space: $A$ and $B$ are nonempty valid subproblems satisfying $A\cup B=S$ and $A\cap B=\varnothing$ . The total cost is the cost of contracting each side plus the cost of merging them:

C(S)=\min_{(A,B)\in\mathcal P(S)} \bigl[C(A)+C(B)+c(A,B)\bigr].

$c(A,B)$ is computed using the current optimization objective, not the local greedy score.

pseudocode

Initialize table entries for single tensors
Process connected subsets S in increasing tensor count:
    Enumerate valid left/right splits (A, B) of S
    C[S] = minimum(C[A] + C[B] + c(A, B))
    Save the split yielding this value
Backtrack each component contraction tree using the best split
Merge component roots using outer-product dynamic programming
return the complete path

The exactness of optimal_dp is limited to this search space: connected subsets are contracted first, then disconnected components are merged. It does not enumerate all trees that permit outer products at arbitrary intermediate steps. The number of states grows rapidly with network size, so this method suits small networks. max_n limits the tensor count of the entire input network.

Interval dynamic programming for a fixed leaf order

Given leaf order [A, B, C, D], the method can compare parenthesizations such as ((AB)C)D and (AB)(CD), but cannot change the leaf order to [A, C, B, D].

Each split divides a contiguous interval into left and right parts. The figure shows the three split points for the four-tensor interval; each part reuses its previously computed best result.

For interval $[i,j]$ , enumerate split points $k$ :

C(i,j)=\min_{i\le k<j} \left[C(i,k)+C(k+1,j)+c([i,k],[k+1,j])\right].

pseudocode

Initialize table entries for single-tensor intervals
Process intervals [i, j] in increasing length:
    Enumerate split points k = i, ..., j-1
    C[i,j] = minimum(left cost + right cost + merge cost)
    Save the best split point
return the path backtracked from the complete interval

order_dp chooses the best parenthesization for the given leaf order, with no guarantee over all leaf orders. It has $O(n^2)$ intervals and $O(n^3)$ candidate splits, plus the cost of processing index sets.

Interfaces and uses

Use optimal_dp for small networks and order_dp to adjust the parenthesization of an existing leaf order. leaf_order_of_path extracts a leaf order from a complete path. See the Rust API for signatures and objective parameters.

Relationship to hypergraph bisection

Hypergraph bisection recursively partitions the network and calls subset DP for sufficiently small subproblems.

Download source Markdown ↓