Malgré les nombreux travaux sur la résolution numérique des chaînes de Markov, (voir par exemple Stewart : Introduction to the Numerical Solution of Markov Chains, ou les actes de la conférence Numerical Solution of Markov chain publiés dans Linear Algebra and its Applications, V 386 (2004)) ce problème reste toujours très difficile dans le cas d'un espace d'états relativement grand.
La théorie des bornes stochastiques (voir Stoyan : Comparison Methods for Queues and Other Stochastic Models) peut être utilisée pour construire une nouvelle chaîne ayant une structure plus facile à résoudre et garantissant une borne inférieure ou supérieure sur les indices de performance.
L'ordre le plus souvent utilisé est l'ordre stochastique fort (noté "st"), permettant d'obtenir des bornes pour toutes les fonctions de récompense croissantes. L'autre avantage de l'ordre "st" est la possibilité de trouver, pour chaque matrice de transition, une borne optimale (voir les travaux de J-M. Vincent). Malheureusement, cet algorithme, assurant l'optimalité de la borne, ne facilite pas la résolution numérique dans l'état actuel de nos connaissances. Bien au contraire, la nouvelle chaîne peut s'avérer plus complexe à résoudre.
Aussi avons nous développé deux familles d'algorithmes qui permettent de calculer une borne plus simplement. La première famille d'algorithme emploie la lumpabilité alors que la seconde famille repose sur des patrons de matrice permettant une résolution adaptée (plutôt que les méthodes générales).
Toutes ces méthodes reposent sur l'idée suivante : les propriétés de monotonie et de comparabilité, conditions nécéssaires de la comparaison des trajectoires des chaines de Markov, imposent des inégalités sur les lignes et colonnes des matrices.
L'algorithme de Vincent remplace ces inégalités par des égalités. Les autres algorithmes respectent les inégalités mais ajoutent des contraintes supplémentaires d'ordre structurels (pour les patrons) ou numériques (pour la lumpabilité).
La lumpabilité ordinaire ou agrégation forte est associé à une
partition des états. On dit que la chaîne est agrégeable au sens fort si
et seulement si le processus obtenu en agrégeant les états selon la
partition (tous les états d'un même ensemble sont regroupés en un seul
point) reste Markovien. La condition d'agrégation impose que les
blocs décrivant la transition d'un ensemble 
vers un ensemble 
sont de somme en ligne constante.
On a précédemment démontré que les contraintes de monotonie et de comparaison sont compatibles avec la lumpabilité ordinaire. En ajoutant un shéma garantissant l'irréductibilité de la chaîne, on obtient l'algorithme LIMSUB.
Cet algorithme suppose que la matrice de la chaîne soit stockée sur disque dans un format adapté (en colonne, en débutant par la dernière colonne et les états étant regroupés par appartenance aux ensembles de la partition). Ce stockage n'est bien sûr pas celui de la génération des états lors de la construction d'un modèle, ce qui oblige à de fastidieuses renumérotations des états, parfois plus longues que l'algorithme de borne. Il est donc naturel de coupler l'algorithme LIMSUB aux Réseaux d'automates stochastiques, ce que nous avons fait dans cette première année du projet. Le formalisme des RAS a plusieurs avantages que nous allons employer :
Les algorithmes classiques de résolution sur les RAS tiennent compte des propriétés 1,3 et 4. Nous allons plutôt ici utiliser les propriétés 1,2 et 4 de manière à générer les états dans l'ordre de la partition associée à la lumpabilité. La propriété d'uniformisation est indispensable puisque les RAS utilisés modélisent des systèmes en temp continu alors que les algorithmes de bornes s'appliquent aux chaînes en temps discret. On peut donc générer une borne en ayant très peu d'objets en mémoire : 2 vecteurs de la taille de l'espace des états, quelques vecteurs de la taille de la partition et la description su RAS par un produit tensoriel. L'algorithme est implanté dans PEPS.