Approche algorithmique de la recherche d'une stratégie RDU-optimale dans un arbre de décision

Gildas Jeantet (1) , Olivier Spanjaard (1)

1 DECISION

Le problème de la recherche d'une stratégie EU-optimale (i.e., optimale au sens de l'utilité espérée) dans un arbre décision hasard se résout en temps linéaire en fontion du nombre d'arcs par programmation dynamique. Nous nous intéressons ici à une variante plus difficile de ce problème, où l'on recherche une stratégie RDU-optimale (i.e., optimale au sens de l'utilité dépendant du rang). L'utilité dépendant du rang présente une plus grande richesse descriptive que l'utilité espérée car elle permet un traitement non linéaire des probabilités. Le problème algorithmique qui s'ensuit dans les arbres décision hasard est cependant plus difficile car la programmation dynamique ne s'applique plus. Nous établissons ici que le problème est NP-difficile. Nous proposons un algorithme de séparation et évaluation pour le résoudre, et présentons des résultats numériques montrant l'efficacité de notre approche.

Domaines: Informatique [cs]

Gildas Jeantet, Olivier Spanjaard. Approche algorithmique de la recherche d'une stratégie RDU-optimale dans un arbre de décision. 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008), Feb 2008, Clermont-Ferrand, France. pp.79-94. ⟨hal-01303913⟩