École Nationale Supérieure de
Techniques Avancées

Abstract

The problem with combinatorial optimization of the p-center is to choose p locations of a set of sites whose distances between customers and centers are known, in order to install p centers for the purpose of minimizing the maximum distance from a customer to the nearest center. Different methods of exact resolution and approximation have been proposed. The most effective method considers solving a series of associated set covering problems. The objective of this work was to improve the performance of a method that calculates a lower bound to the p-centre problem. The research focused on a polyhedral study on these sub-problems. This report presents the theoretical study carried out and the results obtained during the implementation of the various cut generation algorithms. This research internship work was carried out in the laboratory of the Applied Mathematics Unit (UMA) of the École Nationale Supérieure de Techniques Avancées (ENSTA) to obtain the Master's degree in Operational Research (MPRO) from the Université Paris-Saclay.