[EP10] A computational study for the p-median Problem

Conférence Internationale avec comité de lecture : ISCO10, International Symposium on Combinatorial Optimization, Hammamet (Tunisie), March 2010, Vol. 36, pp.455-462, Series Electronic Notes in Discrete Mathematics, (DOI: 10.1016/j.endm.2010.05.058)

Mots clés: Facility Location, Integer Programming, Column and Row generation

Résumé: Given a set of clients and a set of potential sites for facilities, the p-median problem consists of opening a set of p sites and assigning each client to the closest open facility to it. In [Elloumi, S., A tighter formulation of the p-median problem, J. Comb. Optim., 19 (2004), 69–83], a new formulation of this problem was proposed that takes benefit from identical values in the distance matrix. This formulation, when directly used in a mixed integer linear programming software, was proved to perform better than other known formulations, on a large number of instances. Here, we propose to improve the performances of the new formulation by taking benefit from its structure in the solution of its LP-relaxation. Rows and columns are gradually added to the linear program until a condition on the optimal values of the variables is reached. A computational comparison is carried out on many classes of instances.

Equipe: oc


@inproceedings {
title="{A computational study for the p-median Problem}",
author=" S. Elloumi and A. Plateau ",
booktitle="{ISCO10, International Symposium on Combinatorial Optimization, Hammamet (Tunisie)}",
series="Electronic Notes in Discrete Mathematics",