|
 
|
[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
BibTeX
| @inproceedings { | |||
| EP10, | |||
| title | = | "{A computational study for the p-median Problem}", | |
| author | = | " S. Elloumi and A. Plateau ", | |
| booktitle | = | "{ISCO10, International Symposium on Combinatorial Optimization, Hammamet (Tunisie)}", | |
| year | = | 2010, | |
| month | = | "March", | |
| series | = | "Electronic Notes in Discrete Mathematics", | |
| volume | = | 36, | |
| pages | = | "455-462", | |
| doi | = | "10.1016/j.endm.2010.05.058", | |
| } | |||
