Programming Research Group Technical Monograph PRG-98

Oege de Moor

DPhil thesis April 1992, 176 pages, ISBN 0-902928-76-7

Dynamic programming is a strategy for solving optimisation problems. In this thesis, it is shown how many problems that may be solved by dynamic programming are instances of the same abstract specification. This specification is phrased using the calculus of relations offered by topos theory. The main theorem that underlies dynamic programming can then be proved by straightforward equational reasoning. This is the first contribution of this thesis: to provide an elegant formulation of dynamic programming in a categorical setting.

The generic specification of dynamic programming makes use of higher-order operators on relations, akin to the fold operators found in functional programming languages. In the present context, a data type is modelled as an initial F-algebra, where F is an endofunctor on the topos under consideration. The mediating arrows from this initial F-algebra to other F-algebras are instances of fold -- but only for total functions. Can we generalise to relations? For a regular category Ecat, it is possible to construct a category of relations Rel{Ecat}. When a functor between regular categories is a so-called relator, it can be extended (in some canonical way) to a functor between the corresponding categories of relations. Applied to an endofunctor on a topos, this process of extending functors preserves initial algebras, and hence fold can be generalised from functions to relations. This is the second contribution of this thesis: to show how category theory facilitates a smooth generalisation of functional concepts to relations.

It is well-known that the use of dynamic programming is governed by the principle of optimality. Roughly, the principle of optimality says that an optimal solution is composed of optimal solutions to subproblems. In a first attempt, we formalise the principle of optimality as a distributivity condition. This distributivity condition is elegant, but difficult to check in practice. The difficulty arises because we consider minimum elements with respect to a preorder, and therefore minimum elements are not unique. Assuming that we are working in a Boolean topos, it can be proved that monotonicity implies distributivity, and this monotonicity condition is easy to verify in practice. This is the third contribution of this thesis: to develop practical results about minimisation in preorders.