École Nationale Supérieure de
Techniques Avancées

Résumé

Afin de résoudre le problème du P-centre, on peut appliquer une résolution dichotomique faisant appel au set-cover. Le set-cover consiste à effectuer le recouvrement d'un ensemble, en faisant appel à un nombre minimum de sous-ensembles prédéfinis. Ce problème d'optimisation peut donc être résolu via un programme linéaire en nombre entier. Cependant, afin d'accélérer la résolution de ce programme linéaire en nombre entier, on désire mettre en place des coupes {0,1/2}. La génération de coupes efficaces peut-être effectué par la résolution d'un PNLE, mais durant le stage nous étudions une approche heuristique afin d'améliorer le temps de calcul. Toutefois les coupes ainsi générées, bien que fonctionnelles, ne parviennent pas à accélérer la résolution du problème du P-centre, car qu'elles ne sont pas nécessairement les plus efficaces.