Abstract FR:

Parmi les problemes rencontres dans les domaines de l'intelligence artificielle et de la recherche operationnelle, un certain nombre consiste en la recherche d'une solution approchee dans un ensemble discret de solutions possibles. Une resolution approchee consiste a trouver une solution dont la distance a une solution optimale, par rapport a un critere particulier, est connue. Dans cette these, nous proposons une technique algorithmique, appelee separation-evaluation, de resolution de ces problemes d'optimisation, particulierement ceux dont la resolution approchee est difficile. Cette technique s'avere suffisamment generique pour inclure divers algorithmes de recherche arborescente, d'ou le titre de la these. Le theme est aborde en considerant divers aspects dans les domaines de la complexite algorithmique des problemes d'optimisation, algorithmique parallele et distribuee et applications en optimisation combinatoire. La separation-evaluation est une technique algoritmique d'exploration de l'espace de solutions d'un probleme, fondee sur la separation recursive d'une instance du probleme en sous-instances plus simples. Une sequence de bornes inferieures et superieures est obtenue en resolvant recursivement une liste de sous-instances, ou chacune represente une portion de l'espace de solutions. Des formulations sequentielle, parallele et distribuee sont proposees. Ces formulation sont independantes du probleme a resoudre et definissent un carctere cooperatif a la separation-evaluation, dans la perspective de faire cooperer differents algorithmes dans la resolution approchee des problemes d'optimisation. Nous realisons une etude de cas pour illustrer les resultats theoriques concernants la separation-evaluation. Le probleme d'optimisation utilise comme application est le probleme d'ordonnancement de taches.