Dynamic programming by polymorphic semiring algebraic shortcut fusion

A very wide class of DP problems can be specified as a combinatorial problem over a semiring $\mathcal{S}=\left(\mathbb{S},\bigoplus,\bigotimes,i_{\oplus},i_{\otimes}\right)$,

$$\text{$s^{*}$=$\bigoplus_{l\in\mathbb{L}}$$\bigotimes_{x\in l}w\left(x\right)$},$$

(1)

where $\mathbb{L}$ is the set of all combinatorial configurations and $w:\mathbb{X}\to\mathbb{S}$ embeds values in the DP problem into values in the semiring $\mathcal{S}$. As an example, consider the rod-cutting problem which maximizes the sum of values of segments of a list partition. A partition of a list is a decomposition of a list of values, into a list of non-empty contiguous segments. For instance, for the list $\left[1,2,3\right]$, the set of configurations is

$$\mathbb{L}=\left\{\left[\left[1\right],\left[2\right],\left[3\right]\right],\left[\left[1,2\right],\left[3\right]\right],\left[\left[1\right],\left[2,3\right]\right],\left[\left[1,2,3\right]\right]\right\}.$$

(2)

In this example, the combinatorial configurations are list partitions of segments, so variable $l$ represents a partition such as $\left[\left[1\right],\left[2,3\right]\right]$ and variable $x$ a segment of that partition such as $\left[2,3\right]$, with $w\left(x\right)$ being the value of that segment. We can specify the rod-cutting problem as

$$s_{\text{rodcut}}^{*}=\max_{l\in\mathbb{L}}\underset{x\in l}{\sum}w\left(x\right).$$

(3)

which is an instance of (1) with the max-plus semiring $\left(\mathbb{R},\max,+,-\infty,0\right)$.

We will next demonstrate how to solve (1) through brute-force (exhaustive) generate-evaluate computation. There is a special semiring which can be used to exhaustively generate the set of all possible combinatorial configurations $\mathbb{L}$. We call this special semiring the generator semiring $\mathcal{G}=\left(\left\{\left[\mathbb{X}\right]\right\},\cup,\circ,\emptyset,\left\{\left[\,\right]\right\}\right)$. This well-known semiring (and variants) arise in several contexts; for example, to computational linguists it is called the formal language semiring over sets of lists with elements of type $\mathbb{X}$, which we denote by $\left\{\left[\mathbb{X}\right]\right\}$. The operator $\cup$ is set union, and $l_{1}\circ l_{2}$ is the cross-join of two sets of lists $l_{1},l_{2}:\left\{\left[\mathbb{X}\right]\right\}$ obtained by concatenating each element in configuration $l_{1}$ with each element in $l_{2}$. To illustrate, for elements set $\mathbb{X}=\left\{a,b,c,d,e\right\}$,

$$\left\{\left[a,b\right],\left[c\right]\right\}\circ\left\{\left[d\right],\left[e\right]\right\}=\left\{\left[a,b,d\right],\left[a,b,e\right],\left[c,d\right],\left[c,e\right]\right\}.$$

(4)

Define a semiring generator $f^{\mathcal{S},w}:\mathbb{S}$ which is a function $f$ fully applied to the arbitrary semiring $\mathcal{S}$’s binary operators and operator identities and value mapping function $w:\mathbb{X}\to\mathbb{S}$, which maps some data into semiring values. Apply this function $f$ to the generator semiring $\mathcal{G}$ and value mapping function $w\left(x\right)=w^{\prime}\left(x\right)=\left\{\left[x\right]\right\}$ which embeds an element $x\in\mathbb{X}$ into a singleton configuration, $\left\{\left[x\right]\right\}$. In this way, we will generate (enumerate) all combinatorial configurations by computing $\mathbb{L}=f^{\mathcal{G},w^{\prime}}$. Also, assume we have an evaluation function $g^{\mathcal{S},w}:\left\{\left[\mathbb{X}\right]\right\}\to\mathbb{S}$ which is a semiring homomorphism preserving the semiring structure for all $l_{1},l_{2}:\left\{\left[\mathbb{X}\right]\right\}$,

	$\displaystyle g\left(l_{1}\cup l_{2}\right)$	$\displaystyle=g\left(l_{1}\right)\oplus g\left(l_{2}\right)$		(5)
	$\displaystyle g\left(l_{1}\circ l_{2}\right)$	$\displaystyle=g\left(l_{1}\right)\otimes g\left(l_{2}\right)$
	$\displaystyle g\left(\emptyset\right)$	$\displaystyle=i_{\oplus}$
	$\displaystyle g\left(\left\{\left[\,\right]\right\}\right)$	$\displaystyle=i_{\otimes}$

along with the requirement that $g\left(\left\{\left[x\right]\right\}\right)=w\left(x\right)$ for all $x\in\mathbb{X}$. Here, we suppress the subscripted parameters from $g$ for clarity. Now, using this generator $f$ and evaluator $g$, problems defined by the semiring specification (1) can be solved exactly using the following exhaustive generate-evaluate algorithm,

$$s^{*}=g^{\mathcal{S},w}\left(f^{\mathcal{G},w^{\prime}}\right).$$

(6)

Self-evidently, this solves (1) because $f^{\mathcal{G},w^{\prime}}$ generates the set $\mathbb{L}$ and then $g^{\mathcal{S},w}$ evaluates each one of the configurations $l\in\mathbb{L}$ over $\otimes$ and aggregates them over the semiring $\oplus$.

While problem (1) is indeed correctly solved by this generate-evaluate algorithm, this computation is usually intractable because the configurations set $\mathbb{L}$ is typically exponential (or larger). However, it turns out there is no need to generate the set $\mathbb{L}$ in the first place. We have assumed that the generator $f$ is polymorphic in an arbitrary semiring $\mathcal{S}$ i.e. it is a function of type

$$f:\left(\mathbb{S}\to\mathbb{S}\to\mathbb{S}\right)\to\left(\mathbb{S}\to\mathbb{S}\to\mathbb{S}\right)\to\mathbb{S}\to\mathbb{S}\to\left(\mathbb{X}\to\mathbb{S}\right)\to\mathbb{S}.$$

(7)

In words, this function takes as parameters two semiring operators of type $\mathbb{S}\to\mathbb{S}\to\mathbb{S}$, two semiring operator identities of type $\mathbb{S}$ and a mapping function $w:\mathbb{X\to\mathbb{S}}$, returning a value of type $\mathbb{S}$. Then, we can show the following equivalence holds,

$$s^{*}=g^{\mathcal{S},w}\left(f^{\mathcal{G},w^{\prime}}\right)=f^{\mathcal{S},w}.$$

(8)

provided only in addition that $g^{\mathcal{S},w}$ is a semiring homomorphism mapping $\mathcal{G}\to\mathcal{S}$. We call this theorem semiring fusion. If the semiring $\mathcal{S}$ has operators with $O\left(1\right)$ computational complexity, then computing $s^{*}=f^{\mathcal{S},w}$ will be much more computationally efficient than using (6). The proof of this theorem, given rigorously in Appendix A: Proof of DP semiring fusion is a straightforward application of Wadler’s free theorem (Wadler, 1989). This theorem is very widely applicable in the context of DP because semiring polymorphic generators $f^{\mathcal{S},w}$ are extremely common, for instance, all Bellman recursions are of this form (Bellman, 1957; Sniedovich, 2011).

Combinatorial problems in applications of DP, are often more complex than those which can be specified by the simple semiring formulation (1). For instance, let us suppose we want to constrain the semiring problem to restrict it to apply only to configurations which satisfy some constraint, $c:\left[\mathbb{X}\right]\to\mathbb{B}$. Such constrained combinatorial problems are specified as,

$$s_{\mathrm{cons}}^{*}=\bigoplus_{l\in\mathbb{L}:c\left(l\right)}\underset{x\in l}{\bigotimes}w\left(x\right).$$

(9)

As with exhaustive generate-evaluate above, a self-evidently correct (but not at all “smart”) way to solve (9) is to apply the following algorithm. Firstly, compute all configurations $\mathbb{L}$ using a semiring generator $f^{\mathcal{G},w^{\prime}}$. Then, remove (filter away) those configurations $l\in\mathbb{L}$ for which $c\left(l\right)=F$ using a filtering function $\phi^{c}:\left\{\left[\mathbb{X}\right]\right\}\to\left\{\left[\mathbb{X}\right]\right\}$ partially applied to the constraint function, $c$. Finally, evaluate the remaining configurations using a evaluation function $g^{\mathcal{S},w}$. This generate-filter-evaluate algorithm computes,

$$s_{\mathrm{cons}}^{*}=g^{\mathcal{S},w}\left(\phi^{c}\left(f^{\mathcal{G},w^{\prime}}\right)\right).$$

(10)

The difficulty with this approach is the same as faced above: the intractable size of the intermediate configurations $\mathbb{L}$. Above, this was solved by invoking semiring fusion (93), but unfortunately here the filtering $\phi^{c}$ prevents this theorem from being applicable. We will present a practical solution to this which makes use of semiring lifting (Jeuring, 1993; Emoto et al., 2012). This is based on the following idea: if we can find a new semiring which implicitly evaluates the constraints $c$, then we can fuse the constraint with the semiring homomorphism (5) so that semiring fusion (93) becomes applicable once more. This will effectively eliminate the need to compute $\phi^{c}\left(f^{\mathcal{G},w^{\prime}}\right)$, which is responsible for the intractability of the algorithm (10). The resulting theorem will be a generalization of theorem (8).

To apply this idea, we will need constraints $c$ expressed in a separable form, which we explain in detail next. Although not entirely general, many kinds of constraints typically encountered in combinatorial problems are in this form (Sniedovich, 2011). Such separable constraints are formalized using a constraint algebra which we denote by $\mathcal{M}=\left(\mathbb{M},\odot,i_{\odot}\right)$. The only restrictions on the constraint set $\mathbb{M}$ is that it is countable and (for practical implementation purposes) of finite cardinality. The binary operator $\odot$ is usually accompanied by an identity, $i_{\odot}$ (but this is not essential, we will illustrate this below). Then, a typical separable constraint can be defined in terms of a recurrence function $h^{\mathcal{M},v}:\mathbb{N}\to\mathbb{M}$ partially applied to monoid $\mathcal{M}$’s operator $\odot$ and identity $i_{\odot}$ over a set of configurations of length $L$,

	$\displaystyle h_{0}^{\mathcal{M},v}$	$\displaystyle=i_{\odot}$		(11)
	$\displaystyle h_{l}^{\mathcal{M},v}$	$\displaystyle=h_{l-1}^{\mathcal{M},v}\odot v\left(x_{l}\right)\quad\forall l\in\left\{1,2,\ldots,L\right\},$

where the constraint map $v:\mathbb{X}\to\mathbb{M}$ maps an element $x$ in a configuration $l\in\mathbb{L}$ into a constraint value $\mathbb{M}$. Widely encountered algebras include arbitrary finite monoids ($\odot$ is associative) and finite groups. To complete this separable specification of the constraint, we define a Boolean acceptance condition, $a:\mathbb{M}\to\mathbb{B}$, whereby a configuration is retained if $a\left(h_{L}^{\mathcal{M},v}\right)$ evaluates to true. Thus, for a configuration $l:\left\{\left[\mathbb{X}\right]\right\}$ the constraint in (9) is computed using $c\left(l\right)=a\left(h_{L}^{\mathcal{M},v}\right)$.

In this separable formulation, problem (10) is restated by

$$s_{\mathrm{cons}}^{*}=g^{\mathcal{S},w}\left(\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)\right),$$

(12)

with the modified filtering function $\phi^{\mathcal{M},v,a}:\left\{\left[\mathbb{X}\right]\right\}\to\left\{\left[\mathbb{X}\right]\right\}$ which is partially applied to the algebra $\mathcal{M}$, constraint mapping $v$ and acceptance criteria $a$, implementing $c$. To illustrate, a specific, recursive implementation of $\phi$ can be given as (Bird and de Moor, 1996),

	$\displaystyle\phi\left(\emptyset\right)$	$\displaystyle=\emptyset$		(13)
	$\displaystyle\phi\left(\left\{l\right\}\right)$	$\displaystyle=\begin{cases}\left\{l\right\}&a\left(h_{l}\right)=T\\ \emptyset&\textrm{otherwise}\end{cases}$
	$\displaystyle\phi\left(l_{1}\cup l_{2}\right)$	$\displaystyle=\phi\left(l_{1}\right)\cup\phi\left(l_{2}\right)$

where $l_{1}$, $l_{2}$ are configurations in the configuration set $\mathbb{L}$ and we suppress the superscripted parameters of $\phi$ and $h$ only for clarity.

To give a concrete, practical example of this separable constraint formalism, with the additive constraint group $\mathcal{M}=\left(\mathbb{N},+,0\right)$, the constraint with the mapping $v\left(x\right)=1$ computes lengths of configurations $l\in\mathbb{L}$ . Indeed, this algebra is just the list length homomorphism defined by the recursion $h_{0}=0$, $h_{l}=h_{l-1}+1$ (Bird and de Moor, 1996). Thus, the recurrence (26) coupled with this constraint group and the acceptance criteria,

$$a\left(m\right)=\begin{cases}T&m=M\\ F&\textrm{otherwise}\end{cases}$$

(14)

restricts configurations to only those of length $M\in\mathbb{N}$.

With this separable formulation, we can construct a new semiring by lifting $\mathcal{S}$ over the algebra $\mathcal{M}$ (Jeuring, 1993; Emoto et al., 2012). This is the desired semiring with which we can fuse the constraint $c$ with the semiring homomorphism (5). Lifting creates vectors (which we can also consider as functions) of semiring values of type $\mathbb{M}\to\mathbb{S}$. The new, composite semiring $\mathcal{S}\mathcal{M}=\left(\mathbb{M}\text{$\to\mathbb{S}$},\oplus_{\mathcal{M}},\otimes_{\mathcal{M}},i_{\oplus_{\mathcal{M}}},i_{\otimes_{\mathcal{M}}}\right)$ has binary operators over values $x,y:\mathbb{M}\text{$\to\mathbb{S}$}$given explicitly by,

	$\displaystyle\left(x\oplus_{\mathcal{M}}y\right)_{m}$	$\displaystyle=x_{m}\oplus y_{m}$		(15)
	$\displaystyle\left(x\otimes_{\mathcal{M}}y\right)_{m}$	$\displaystyle=\bigoplus_{\begin{subarray}{c}m^{\prime}\odot m^{\prime\prime}=m\\ \forall m^{\prime},m^{\prime\prime}\in\mathbb{M}\end{subarray}}\left(x_{m^{\prime}}\otimes y_{m^{\prime\prime}}\right),$

where $x_{m}$ refers to indexing with values in $\mathbb{M}$. The associated operator identities are,

	$\displaystyle\left(i_{\oplus_{\mathcal{M}}}\right)_{m}$	$\displaystyle=i_{\oplus}\quad\forall m\in\mathbb{M}$		(16)
	$\displaystyle\left(i_{\otimes_{\mathcal{M}}}\right)_{m}$	$\displaystyle=\begin{cases}i_{\otimes}&m=i_{\odot}\\ i_{\oplus}&\textrm{otherwise}.\end{cases}$

The operator $\otimes_{\mathcal{M}}$ is an interesting and far-reaching generalization of discrete convolution operators found in contexts such as digital signal processing, machine learning and applied mathematics. We also need the lifted value mapping, $w_{\mathcal{M}}:\mathbb{X}\to\left(\mathbb{M}\to\mathbb{S}\right)$ given by,

$$\left(w_{\mathcal{M}}\left(x\right)\right)_{m}=\begin{cases}w\left(x\right)&v\left(x\right)=m\\ i_{\oplus}&\textrm{otherwise},\end{cases}$$

(17)

where the original semiring map is $w:\mathbb{X}\to\mathbb{S}$ and the constraint map is $v:\mathbb{X}\to\mathbb{M}$.

Finally, to obtain the solution to $s_{\mathrm{cons}}^{*}$ to (8), we need to project the vector lifted over $\mathbb{M}$, onto $\mathbb{B}$ using the projection function $\pi^{\mathcal{S},a}:\left(\mathbb{M}\to\mathbb{S}\right)\to\mathbb{S}$ partially applied to semiring $\mathcal{S}$ operators and identities and acceptance criteria $a$,

$$\pi^{\mathcal{S},a}\left(x\right)=\bigoplus_{m^{\prime}\in\mathbb{M}:a\left(m^{\prime}\right)}x_{m^{\prime}}.$$

(18)

This yields all the ingredients to define a theorem which we call semiring constrained fusion,

$$s_{\mathrm{cons}}^{*}=g^{\mathcal{S},w}\left(\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)\right)=\pi^{\mathcal{S},a}\left(f^{\mathcal{S}\mathcal{M},w_{\mathcal{M}}}\right).$$

(19)

To summarize (19), on the left hand side, $f^{\mathcal{G},w^{\prime}}$ exhaustively computes configurations in $\mathbb{L}$; $\phi^{\mathcal{M},v,a}$ filters away any configurations which do not satisfy the constraint $c$ implemented by $v$ and $a$ over the constraint algebra $\mathcal{M}$ and $g^{\mathcal{S},w}$ evaluates the remaining configurations in $\mathbb{L}$ with the semiring $\mathcal{S}$ using the mapping $w$. On the right hand side, $f^{S\mathcal{M},w_{\mathcal{M}}}:\left(\mathbb{M}\to\mathbb{S}\right)$ (fully) applied to lifted semiring’s $\mathcal{SM}$’s operators and identities and lifted mapping function $w_{\mathcal{M}}$, first maps the element $\mathbb{X}$ into lifted semiring values using $w$ and lifts them over the constraint set using $v$. It then evaluates all configurations in $\mathbb{L}$, for every value of the constraint set $\mathbb{M}$, using the lifted semiring $\mathcal{S}\mathcal{M}$. Finally, $\pi^{\mathcal{S},a}:\left(\mathbb{M}\to\mathbb{S}\right)\to\mathbb{S}$ projects this lifted computation back down onto the plain semiring $\mathcal{S}$.

The proof of (19) result is given in Appendix B: Constraint lifting proofs. To give some informal intuition into the steps in this proof, we show that (15) is a semiring and then using a change of variables argument, show how the projection is obtained. We then demonstrate that the composition of the filtering with the semiring homomorphism, can be fused into a new homomorphism over the constraint-lifted semiring. This allows us to use our already established result (19) to show that the composition of the exhaustive configuration generator followed by the filtering, is equivalent to evaluation of these configurations in the lifted semiring, followed by a projection.

We raise a couple of important comments about this theorem here:

1. 1.

   The effect on the computational and memory complexity of the corresponding unconstrained algorithm (8), is quite predictable. For most practical computational semirings (e.g. max-plus or sum-product) the operators $\oplus,\otimes$ will be $O\left(1\right)$. In this setting, for each value of $m\in\mathbb{M}$, the binary operator $\oplus_{\mathcal{M}}$ is $O\left(1\right)$, and the operator $\otimes_{\mathcal{M}}$ is $O\left(M^{2}\right)$. Thus, in general, applying a constraint increases the worst-case computational complexity of an existing polymorphic semiring generator function $f^{\mathcal{S},w}$ by a multiplicative factor $O\left(M^{3}\right)$. In terms of memory, lifting requires storing $M$ values per configuration, therefore the memory complexity increases multiplicatively by a factor $O\left(M\right)$.

2. 2.

   Lifting is intimately related to the design of DP algorithms found in textbooks, in the following way. A widely stated, but intuitive observation, is that designing practical DP algorithms boils down to identifying a structural decomposition which makes frequent re-use of sub-problems (Kleinberg and Tardos, 2005). This design principle is easy to state, but often quite tricky to apply in practice, as it can depend upon a serendipitous discovery of the right way to parameterize the problem. However, implicit to the definition of the constraint operator $\odot$ for constraints $c\left(l\right)$ which can be implemented in separable algebraic form, is the relationship that solutions for different values of the constraint algebra have with each other. The lifted product in (15) combines all solutions at every value of the constraint. However, for each $m\in\mathbb{M}$, the condition $m^{\prime}\odot m^{\prime\prime}=m$ in the product partitions the solutions in a way which determines how the DP sub-problems should be combined. In other words, this partitioning, coupled with the pairwise summation, determines the dependency structure of configurations $l\in\mathbb{L}$. For example, in the case of the simple natural number addition, $m^{\prime}+m^{\prime\prime}=m$, to find the sub-problem for the case $m=5$ requires us to combine all sub-problems $\left(m^{\prime},m^{\prime\prime}\right)=\left(1,4\right)$, $\left(2,3\right)$, $\left(3,2\right)$ and $\left(4,1\right)$, together. Interestingly, this also demonstrates that DP decompositions can be performed in ways that are much more general than the fairly limited descriptions of combining “smaller”, self-similar problems. Indeed, it is useful to think of DP decomposition as arising from a partitioning of the space of the constraint value under the constraint operator $\odot$, into subsets of pairs of sub-problems for a given value of $m\in\mathbb{M}$.

The main problem with the construction (19) is that the direct computation of $x\otimes_{\mathcal{M}}y$ is quadratic in the size of $\mathbb{M}$. This is not a problem for small lifting sets, but for many practical problems we want to apply constraints which can take on a potentially large set of values, which makes the naive application of constraint lifting computationally inefficient. We also know that it is often possible to come up with hand-crafted DP algorithms which are more efficient than this. We can, however, substantially improve on this quadratic dependence by noting that for many semiring polymorphic configuration generators $f^{\mathcal{S},w}:\mathbb{N}\to\mathbb{S}$ given as DP (Bellman) recursions, we need to compute terms of the form $u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)$ for some general $u:\mathbb{M}\text{$\to\mathbb{S}$}$. Since the lifted mapping function $w_{\mathcal{M}}\left(x\right)_{m}\neq i_{\oplus}$ only for one value, $m^{\prime\prime}=v\left(x\right)$, we can simplify the double summation to a single one,

	$\displaystyle\left(u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)\right)_{m}$	$\displaystyle=\bigoplus_{\begin{subarray}{c}m^{\prime}\odot m^{\prime\prime}=m\\ \forall m^{\prime},m^{\prime\prime}\in\mathbb{M}\end{subarray}}\left(u_{m^{\prime}}\otimes w_{\mathcal{M}}\left(x\right)_{m^{\prime\prime}}\right)$		(20)
		$\displaystyle=\left(\bigoplus_{\begin{subarray}{c}m^{\prime}\in\mathbb{M}:m^{\prime}\odot v\left(x\right)=m\end{subarray}}u_{m^{\prime}}\right)\otimes w\left(x\right).$

Because the operator $\odot$ does not necessarily have inverses, solutions $m^{\prime}\in\mathbb{M}$ to the equation $m^{\prime}\odot v\left(x\right)=m$ are not necessarily unique. However, we can flip this around and instead explicitly compute $m=m^{\prime}\odot v\left(x\right)$ for each $m^{\prime}\in\mathbb{M}$. This leads to an obvious iterative algorithm,

	$\displaystyle z$	$\displaystyle\mapsfrom i_{\oplus_{\mathcal{M}}}$		(21)
	$\displaystyle z_{m\odot v\left(x\right)}$	$\displaystyle\mapsfrom z_{m\odot v\left(x\right)}\oplus\left(u_{m}\otimes w\left(x\right)\right)\quad\forall m\in\mathbb{M},$

to obtain $u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)=z$ at the end of the iteration; here the arrow $\mapsfrom$ denotes setting the variable on the left, to the value on the right, possibly overwriting the previous value of the variable. Thus the product (20) is an inherently $O\left(M\right)$ operation. As a result, semiring polymorphic generators modified to produce constrained configurations will have worst-case multiplicative increase in time complexity of $O\left(M^{2}\right)$, if the semiring product $\otimes$ appears in the generator only in terms of the form $u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)$. This is true, for instance of all algebraic path problems (Huang, 2008) and we will encounter several other examples below.

If, additionally, the algebra $\mathcal{M}$ has inverses (for example, if the algebra is a group), on fixing $m$ and $m^{\prime}$, there is a unique (and often analytical) solution to $m^{\prime}\odot m^{\prime\prime}=m$ which we can write as $m^{\prime\prime}=\left(m^{\prime}\right)^{-1}\odot m$. This also allows us to simplify the lifted semiring product to the $O\left(M\right)$ computation,

$$\left(x\otimes_{\mathcal{M}}y\right)_{m}=\bigoplus_{m^{\prime}\in\mathbb{M}}\left(x_{m^{\prime}}\otimes y_{\left(m^{\prime}\right)^{-1}\odot m}\right).$$

(22)

Note that we often have finite groups where we are not interested in defining inverses for all elements, for example where we need $y_{\left(m^{\prime}\right)^{-1}\odot m}$ but $\left(m^{\prime}\right)^{-1}\odot m\notin\mathbb{M}$. In that case, setting $y_{\left(m^{\prime}\right)^{-1}\odot m}=i_{\oplus}$ suffices to appropriately truncate the above product.

For such group lifting algebras, terms of the form $u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)$ simplify even further. We can solve $m^{\prime}\odot v\left(x\right)=m$ uniquely to find $m^{\prime}=v\left(x\right)^{-1}\odot m$, so that the product (20) can, in this situation, now be computed as,

$\displaystyle\left(u\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(x\right)\right)_{m}$

$\displaystyle=\begin{cases}i_{\oplus}&m\odot v\left(x\right)^{-1}\notin\mathbb{M}\\ u_{m\odot v\left(x\right)^{-1}}\otimes w\left(x\right)&\textrm{otherwise},\end{cases}$

(23)

which is an $O\left(1\right)$ time operation. Thus, semiring polymorphic configuration generators can be modified to produce constrained configurations with multiplicative time complexity increase of only $O\left(M\right)$, if constraints are expressible in terms of a group algebra. Some examples of useful, simplified constraint algebras are listed in Appendix D: Some useful constraint algebras.

Let us pause to examine how to apply the preceding theory. Consider the problem of finding the value of the minimum sum subsequence of a list (a subsequence being a sublist of generally non-consecutive elements of a list). We can specify this simple, unconstrained combinatorial optimization problem as,

$$s_{\text{subs}}^{*}=\min_{l\in\mathbb{L}}\underset{x\in l}{\sum}x,$$

(24)

where the configuration set $\mathbb{L}$ contains all possible subsequences of a list, of which there are $2^{N}$ for lists of length $N$. For instance, the subsequences of the list $\left[-2,1,8\right]$ are

$$\mathbb{L}=\left\{\left[\,\right],\left[-2\right],\left[1\right],\left[8\right],\left[-2,1\right],\left[-2,8\right],\left[1,8\right],\left[-2,1,8\right]\right\}.$$

(25)

This is a specification (1) over the min-plus semiring $\mathcal{R}=\left(\mathbb{R},\min,+,\infty,0\right)$. For a given a length $N$ list $l:\mathbb{N}\to\mathbb{X}$ indexed as $l_{n}$, a simple, semiring polymorphic generator is given by the following DP Bellman recursion,

	$\displaystyle f_{0}^{\mathcal{S},w}$	$\displaystyle=i_{\otimes}$		(26)
	$\displaystyle f_{n}^{\mathcal{S},w}$	$\displaystyle=f_{n-1}^{\mathcal{S},w}\otimes\left(i_{\otimes}\oplus w\left(l_{n}\right)\right)\quad\forall n\in\left\{1,2,\ldots,N\right\},$

where $w:\mathbb{X}\to\mathbb{S}$ embeds elements of some given list $l$ to $\mathcal{S}$-semiring values. Semiring fusion (8) tells us that $s_{\text{subs}}^{*}=f_{N}^{\mathcal{R},id}$ given by

	$\displaystyle f_{0}^{\mathcal{R},id}$	$\displaystyle=0$		(27)
	$\displaystyle f_{n}^{\mathcal{R},id}$	$\displaystyle=f_{n-1}^{\mathcal{R},id}+\min\left(0,l_{n}\right)\quad\forall n\in\left\{1,2,\ldots,N\right\},$

is a correct algorithm for solving problem (24) exactly in $O\left(N\right)$ time complexity, even though the exhaustive solution would require generating and evaluating $2^{N}$ subsequences requiring exponential time.

Now, assume that, rather than subsequences, we are interested in combinations of elements of a list (that is, fixed-size subsequences). We can define a constrained subsequence problem as

$$s_{\text{combs}}^{*}=\min_{l\in\mathbb{L}:\#\left(l\right)=M}\underset{x\in l}{\sum}x,$$

(28)

where the constraint condition $c\left(l\right)=\left(\#\left(l\right)=M\right)$ receives a subsequence, and evaluates to true if that subsequence has the given length $M$. For instance, if $M=2$, the configurations $\mathbb{L}$ constrained by sublist length for list $\left[-2,1,8\right]$ is the set

$$\mathbb{L}^{\prime}=\left\{l\in\mathbb{L}:\#\left(l\right)=2\right\}=\left\{\left[-2,1\right],\left[-2,8\right],\left[1,8\right]\right\}.$$

(29)

This sequence length constraint can be formulated using the lifting algebra $\mathcal{M}=\left(\left\{1,\ldots,M\right\},+,0\right)$, constraint mapping function $v\left(n\right)=1$ and acceptance criteria $a\left(m\right)=T$ if $m=M$ and $F$ otherwise. Inserting the semiring $\mathcal{SM}$’s operators and lifted mapping $w_{\mathcal{M}}$ into the semiring polymorphic generator recursion (26), we obtain,

	$\displaystyle f_{0,m}$	$\displaystyle=\left(i_{\otimes_{\mathcal{M}}}\right)_{m}$		(30)
	$\displaystyle f_{n,m}$	$\displaystyle=\left(f_{n-1}\otimes_{\mathcal{M}}\left(i_{\otimes_{\mathcal{M}}}\oplus_{\mathcal{M}}w_{\mathcal{M}}\left(n\right)\right)\right)_{m},$

where we suppress $f_{n,m}$ ’s superscripts for clarity. The first line above simplifies to,

$$f_{0,m}=\begin{cases}i_{\otimes}&m=0\\ i_{\oplus}&\textrm{otherwise,}\end{cases}$$

(31)

and the second line can be simplified as follows,

	$\displaystyle f_{n,m}$	$\displaystyle=\left(f_{n-1}\oplus_{\mathcal{M}}f_{n-1}\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(n\right)\right)_{m}$		(32)
		$\displaystyle=f_{n-1,m}\oplus\left(f_{n-1}\otimes_{\mathcal{M}}w_{\mathcal{M}}\left(n\right)\right)_{m}$
		$\displaystyle=f_{n-1,m}\oplus\begin{cases}i_{\oplus}&m-1\notin\mathbb{M}\\ f_{n-1,m-1}\otimes w\left(n\right)&\textrm{otherwise}\end{cases}$
		$\displaystyle=\begin{cases}f_{n-1,0}&m=0\\ f_{n-1,m}\oplus\left(f_{n-1,m-1}\otimes w\left(n\right)\right)&\textrm{otherwise},\end{cases}$

for all $n\in\left\{1,2,\ldots,N\right\}$ and $m\in\left\{1,2,\ldots,M\right\}$. Explicitly, by invoking constrained semiring fusion (19), in the min-plus semiring $\mathcal{R}$ with $w=id$ this is,

	$\displaystyle f_{0,m}^{\mathcal{R},id}$	$\displaystyle=\begin{cases}0&m=0\\ \infty&\textrm{otherwise}\end{cases}$		(33)
	$\displaystyle f_{n,m}^{\mathcal{R},id}$	$\displaystyle=\begin{cases}f_{n-1,0}^{\mathcal{R},id}&m=0\\ \min\left(f_{n-1,m}^{\mathcal{R},id},f_{n-1,m-1}^{\mathcal{R},id}+l_{n}\right)&\textrm{otherwise}.\end{cases}$

which is a simple $O\left(N\,M\right)$, provably correct algorithm for solving 28 through computing $s_{\text{combs}}^{*}=\pi^{\mathcal{R},a}\left(f_{N}^{R,id}\right)=f_{N,M}^{\mathcal{R},id}$ using the recursion (33) above.

It is instructive to compare this systematically derived algorithm to the textbook presentation of similar DP algorithms such as the quasi-polynomial knapsack problem (Kleinberg and Tardos, 2005; Emoto et al., 2012). We have obtained this DP algorithm by starting from a specification and by provably correct derivation steps, arrived at the new, computationally efficient recurrence above which solves the constrained problem. Often, the solutions obtained this way resemble hand-coded DP algorithms which involve ad-hoc and specific reasoning where we have to resort to special case analysis to demonstrate correctness and computational complexity, after the algorithm is coded.

The above cases have demonstrated the use of arbitrary semirings where some scalar-valued, numerical solution is required. It is often the case for optimization problems (involving the use of selection semirings such min-plus, $\mathcal{R}$) that we also want to know which solutions lead to the optimal (semiring) value. The usual solution to this (given in most DP literature) is backtracing, which retains a list of decisions at each stage and a series of “back pointers” to the previous decision, and then recovers the unknown decisions by following the sequence of pointers backwards.

In fact, there is an alternative and conceptually simpler solution made possible with the use of appropriate semirings. In particular we will focus on the generator semiring $\mathcal{G}$. We can always exploit what is known as the tupling trick to compute two different semirings simultaneously (Bird and de Moor, 1996). If we map the semiring values used during the DP computations inside a pair $\left(\mathbb{S},\left\{\left[\mathbb{S}\right]\right\}\right)$, then we can simultaneously update a semiring total while retaining the values selected in that stage. For example, the arg-max-plus selection, also known as the Viterbi, semiring (Goodman, 1999; Emoto et al., 2012),

$$\mathcal{S}\times\mathcal{G}=\left(\mathbb{S}\times\left\{\left[\mathbb{S}\right]\right\},\oplus,\otimes,\left(-\infty,\emptyset\right),\left(0,\left\{\left[\,\right]\right\}\right)\right),$$

(34)

has operators given explicitly by,

	$\displaystyle\left(u,x\right)\oplus\left(v,y\right)$	$\displaystyle=\begin{cases}\left(u,x\right)&u>v\\ \left(v,y\right)&u<v\\ \left(u,x\cup y\right)&\textrm{otherwise}\end{cases}$		(35)
	$\displaystyle\left(u,x\right)\otimes\left(v,y\right)$	$\displaystyle=\left(u+v,x\circ y\right),$

with identities $i_{\oplus}=\left(-\infty,\emptyset\right)$ and $i_{\otimes}=\left(0,\left\{\left[\,\right]\right\}\right)$. Furthermore, it is straightforward to construct a semiring which extends the Viterbi semiring by maintaining a ranked list of optima, i.e. computing the top $k$ optimal solutions, not merely the single highest scoring one (Goodman, 1999).

In most practical situations, for instance, where the mapping function in the DP problem is real-valued $w:\mathbb{X}\to\mathbb{R}$ and thus have effectively zero probability of not being unique, there will only be a single, rather than potentially multiple, optimal solutions. In that case, we can remove the ambiguities in the selection with a simpler semiring,

$$\mathcal{S}\times\mathcal{G}=\left(\mathbb{S}\times\left[\mathbb{S}\right],\oplus,\otimes,\left(-\infty,\emptyset\right),\left(0,\left[\,\right]\right)\right),$$

(36)

with operators,

	$\displaystyle\left(u,x\right)\oplus\left(v,y\right)$	$\displaystyle=\begin{cases}\left(u,x\right)&u\geq v\\ \left(u,y\right)&u<v\end{cases}$		(37)
	$\displaystyle\left(u,x\right)\otimes\left(v,y\right)$	$\displaystyle=\left(u+v,x\cup y\right).$

Clearly, the semiring $\mathcal{S}\times\mathcal{G}$ is the tupling of max-plus with $\mathcal{G}$ in such a way as to compute both the value of the optimal solution alongside the values used to compute it.

Backtracing and the simple (Viterbi) tupled semiring will usually be similar in terms of computational complexity. Any particular, practical implementation may well require a more detailed investigation of the specifics of the particular data structures in the DP recurrence and the software and/or hardware platforms involved. For instance, while semiring tupling does require list concatenation and array structures could certainly pose a complexity issue, when implemented instead as linked lists this concatenation takes $O\left(1\right)$ time, and indeed in practice, DP algorithm recurrences derived using the methods described here reduce to a sequence of list append operations, $O\left(1\right)$ each for linked lists.

However, the specifics of lower-level implementation complexity are incidental: the overall argument is one of high-level conceptual clarity and systematic derivation, since the tupling construction requires no modification to the algebraic derivations given here. For instance, backtracing requires a way to traverse the DP decisions correctly in the reverse order, which will be special to each DP problem. With tupled semirings and semiring polymorphic generator functions, all that is required is to change the semiring of the DP generator algorithm function as described above, we do not need to know anything about how the generator algorithm works. Additionally, tupling semirings is trivially compatible with any set of multiple lifting constraints where hand-coding of special implementations of backtracking through the same set of multiple interacting constraints, would be error-prone.

The above sections have explained how to specify a combinatorial problem in an arbitrary semiring and how to derive an efficient algorithm to solve it. It has demonstrated how the use of semiring lifting allows us to modify an existing DP algorithm specification with a constraint, which can then be solved efficiently using constrained semiring fusion (19). Here, we show how this gives us a way of creating new, semiring polymorphic DP generators from existing ones such as $f^{\mathcal{S},w}$. To see this, note that the semiring homomorphism $g^{\mathcal{G},w^{\prime}}$ with $w^{\prime}\left(x\right)=\left\{\left[x\right]\right\}$ is the identity homomorphism $id^{\mathcal{G}}:\left\{\left[\mathbb{X}\right]\right\}\to\left\{\left[\mathbb{X}\right]\right\}$ for values in the semiring $\mathcal{G}$, i.e. it maps sets of lists, into the same sets of lists unchanged. Thus we obtain,

	$\displaystyle\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)$	$\displaystyle=id^{\mathcal{G}}\left(\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)\right)$		(38)
		$\displaystyle=g^{\mathcal{G},w^{\prime}}\left(\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)\right)$
		$\displaystyle=\pi^{\mathcal{G},a}\left(f^{\mathcal{G}\mathcal{M},w_{\mathcal{M}}^{\prime}}\right)$

where the last step invokes (19). We have shown that $\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)=\pi^{\mathcal{G},a}\left(f^{\mathcal{G}\mathcal{M},w_{\mathcal{M}}^{\prime}}\right)$, which we denote by $f^{\prime\mathcal{G},w^{\prime}}=\phi^{\mathcal{M},v,a}\left(f^{\mathcal{G},w^{\prime}}\right)$, this is the generator which computes a constrained configuration set. Now, fixing $\mathcal{M}$, acceptance criteria $a$ and constraint map $v$, we notice that $f^{\prime\mathcal{G},w^{\prime}}$ depends only upon the semiring $\mathcal{G}$ and map $w^{\prime}$. Thus it, too, is semiring polymorphic since we can replace the $\mathcal{G}$ and $w^{\prime}$ in $f^{\prime}$ with any arbitrary semiring $\mathcal{S}$ and mapping $w$ to obtain $f^{\prime\mathcal{S},w}$. It follows that we can consider $f^{\prime\mathcal{S},w}$ as a new semiring polymorphic generator function derived from the existing generator, $f^{\mathcal{S},w}$. This implies, in particular:

1. 1.

   If $f^{\mathcal{S},w}$ is the generator of $\mathbb{L}$ for the problem $s^{*}=\bigoplus_{l\in\mathbb{L}}\bigotimes_{x\in l}w\left(x\right)$ in (1), then the new, derived polymorphic generator $f^{\prime\mathcal{S},w}$ is the generator for the constraint augmented problem $s^{\prime*}=\bigoplus_{l\in\mathbb{L}^{\prime}}\bigotimes_{x\in l}w\left(x\right)$ where $\mathbb{L}^{\prime}=\left\{l\in\mathbb{L}:c\left(l\right)\right\}$ and $c$ is implemented by $\mathcal{M}$, $v$ and $a$ which are fixed in (implicit to) $f^{\prime\mathcal{S},w}$. This, of course, just a way of expressing an algorithm for efficiently computing $s_{\mathrm{cons}}^{*}$ in terms of an algorithm for efficiently computing $s^{*}$ which is implicit to the constrained semiring fusion theorem (19).

2. 2.

   Being semiring polymorphic, this new generator function $f^{\prime\mathcal{S},w}$ satisfies all the conditions of semiring fusion (8), i.e. with an arbitrary semiring homomorphism $g^{\mathcal{S},w}$, we have $g^{\mathcal{S},w}\left(f^{\prime\mathcal{G},w^{\prime}}\right)=f^{\prime\mathcal{S},w}$.

3. 3.

   We can repeat this process of augmenting an existing specification solved by use of a semiring polymorphic generator to derive novel, polymorphic DP algorithm with multiple, simultaneous constraints. This is possible, essentially, because lifting can always be “nested”, i.e. lifted semirings can themselves be lifted.

These implications have practical consequences in applications, which we now illustrate. Above, we demonstrated how to derive an algorithm for the min-plus problem over subsequence combinations (33) from the min-plus problem over subsequences, by semiring lifting applied to the polymorphic generator for subsequences, (26) which we repeat here for convenience,

	$\displaystyle f_{0}^{\mathcal{S},w}$	$\displaystyle=i_{\otimes}$		(39)
	$\displaystyle f_{n}^{\mathcal{S},w}$	$\displaystyle=f_{n-1}^{\mathcal{S},w}\otimes\left(i_{\otimes}\oplus w\left(n\right)\right)\quad\forall n\in\left\{1,2,\ldots,N\right\},$

which is known as an efficient DP algorithm for solving the specification $s_{\text{subspoly}}^{*}=\bigoplus_{l\in\mathbb{L}}\bigotimes_{x\in l}w\left(x\right)$ over an arbitrary semiring $\mathcal{S}$ and mapping $w$ by computing $s_{\text{subspoly}}^{*}=f_{N}^{\mathcal{S},w}$. The resulting polymorphic generator of combinations, (30), is a straightforward DP Bellman recursion for solving specifications over subsequence combinations of length $M$. For semirings wherein the operators can be evaluated in constant time, this has $O\left(N\,M\right)$ time complexity. It is interesting and useful in its own right so we provide a pseudocode implementation here, Algorithm 1.

As a somewhat more complex example, for some applications, there is a need to perform computations over non-empty subsequences, that is subsequences without the empty sub-sequence $\left\{\emptyset\right\}$. Analogous to the subsequence problem, we can define the non-empty subsequence problem in an arbitrary semiring as,

$$s_{\text{subsnepoly}}^{*}=\bigoplus_{l\in\mathbb{L}:l\neq\emptyset}\underset{x\in l}{\bigotimes}w\left(x\right),$$

(40)

where the constraint function $c\left(l\right)=\left(l\neq\emptyset\right)$ is true if the configuration is non-empty. For instance, for the sequence $\left[1,2,3\right]$, the set of non-empty subsequences consists of the set

$$\mathbb{L}^{\prime}=\left\{l\in\mathbb{L}:l\neq\emptyset\right\}=\left\{\left[1\right],\left[2\right],\left[3\right],\left[1,2\right],\left[1,3\right],\left[2,3\right],\left[1,2,3\right]\right\}$$

(41)

which has size $2^{N}-1$. To use semiring lifting we need a constraint algebra for $c\left(l\right)$, for which we define an existence constraint algebra $\mathcal{M}=\left(\mathbb{B},\vee,F\right)$ (see Appendix B: Constraint lifting proofs) with the constant constraint map $v\left(n\right)=T$ which partitions the set of subsequences generated by the recurrence (26), into empty $m=F$ and non-empty $m=T$ subsequences,

	$\displaystyle f_{0,m}$	$\displaystyle=\begin{cases}i_{\otimes}&m=F\\ i_{\oplus}&m=T\end{cases}$		(42)
	$\displaystyle f_{n,m}$	$\displaystyle=\left(f_{n-1}\oplus_{\mathcal{M}}f_{n-1}\otimes w_{\mathcal{M}}\left(n\right)\right)_{m}$
		$\displaystyle=f_{n-1}\oplus\begin{cases}w\left(n\right)\otimes\left(f_{n-1,F}\oplus f_{n-1,T}\right)&m=T\\ i_{\oplus}&m=F.\end{cases}$

suppressing the superscript dependence of $f$ here on $\mathcal{S},w$ for clarity. The last line can be rewritten,

	$\displaystyle f_{n,m}$	$\displaystyle=\begin{cases}f_{n-1,T}\oplus w\left(n\right)\otimes\left(f_{n-1,F}\oplus f_{n-1,T}\right)&m=T\\ f_{n-1,F}&m=F\end{cases}$		(43)
		$\displaystyle=\begin{cases}f_{n-1,T}\oplus\left(w\left(n\right)\otimes f_{n-1,F}\right)\oplus\left(w\left(n\right)\otimes f_{n-1,T}\right)&m=T\\ i_{\otimes}&m=F,\end{cases}$

so that $f_{N,F}=i_{\otimes}$ as expected in the empty subsequence case. Focusing on the case we want, $f_{N,T}$, we have,

$$\begin{aligned} f_{n,T}&=f_{n-1,T}\oplus\left(w\left(n\right)\otimes f_{n-1,T}\right)\oplus w\left(n\right)\end{aligned},$$

(44)

which, being expressed entirely in terms of the case $m=T$, allows us to ignore the lifting altogether to obtain the following semiring polymorphic generator for non-empty subsequences,

	$\displaystyle f_{0}$	$\displaystyle=i_{\oplus}$		(45)
	$\displaystyle f_{n}$	$\displaystyle=f_{n-1}\oplus\left(f_{n-1}\otimes w\left(n\right)\right)\oplus w\left(n\right)\quad\forall n\in\left\{1,2,\ldots,N\right\}.$

which solves $s_{\text{subsnepoly}}^{*}=f_{N}$ and requires only $O\left(N\right)$ steps.