Accélération de l’algorithme de séparation et évaluation pour les diagrammes de décision grâce à la mémoïsation

Coppé, Vianney [UCL] Gillard, Xavier [UCL] Schaus, Pierre [UCL]

L’optimisation discrète avec diagrammes de décision permet de résoudre des problèmes complexes sur base d’un modèle de programmation dynamique. L’approche consiste en un algorithme de séparation et évaluation dans l’espace des états du modèle, où les bornes dérivent de diagrammes de décision. Cet article explique comment accélérer l’algorithme en mémorisant certains résultats intermédiaires afin d’éviter au maximum l’exploration répétée de certaines parties de l’espace de recherche. Les résultats expérimentaux montrent que cette accélération est significative.