Howard's multichain policy iteration algorithm
for max-plus linear maps
I wrote a C-program which
implements Howard's mulichain policy iteration
algorithm for max-plus linear maps. It solves the general
``maximal circuit mean'' problem, in directed graphs.
The basic version of the algorithm takes as input a weighted
directed graph (or sparse matrix)
and returns two vectors: the cycle time, and
the bias (which is an eigenvector when the matrix
is irreducible). An extended version
takes as input a digraph with two valuations,
in order to compute the generalized maximal ``weight to length'' circuit mean
(the lengths need not be 1).
Howard's algorithm runs in an almost linear time
(although no proof of this fact exists).
It is much faster than the classical
algorithms to compute the cycle time,
including Karp's. An implementation of Karp's algorithm
is included for comparison.
- The algorithm is documented in the following
paper: Numerical computation of spectral elements in max-plus algebra,
Jean Cochet-Terrasson, Guy Cohen, Stephane Gaubert, Michael Mc Gettrick,
Jean-Pierre Quadrat, published in the
Proceedings of the
IFAC Conference on System Structure and Control,
Nantes, France, July 8-10, 1998.
ifacssc98.pdf,
ifacssc98.ps,
ifacssc98.ps.gz
- A variant of this algorithm, which works
for the simpler single source shortest path
problem (which can be seen as a subproblem
of the cycle time problem), has been shown to have a strongly
polynomial execution time in J. Cochet-Terrasson
and S. Gaubert,
Policy Iteration Algorithm for Shortest Path Problems,
preprint.ps,
preprint.ps.gz
- A standalone distribution is available here
HOWARD0.27.tar.gz,
alternatively, the algorithm can be used in an user
friendly way from the Maxplus toolbox of Scilab.
- Older versions of the standalone distribution:
S. Gaubert Updated Jul 2008