A computational study for the p-median Problem
| Autor: | Agnès Plateau, Sourour Elloumi |
|---|---|
| Přispěvatelé: | Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Mathematical optimization Facility Location Linear programming 0211 other engineering and technologies Structure (category theory) 02 engineering and technology Row and column spaces Set (abstract data type) 03 medical and health sciences Software Programmation en nombres entiers Column and Row generation Discrete Mathematics and Combinatorics [INFO]Computer Science [cs] Integer programming Mathematics 021103 operations research 030505 public health business.industry Applied Mathematics Branch and price Distance matrix Génération de lignes et de colonnes Emplacement d'installation 0305 other medical science business Integer Programming |
| Zdroj: | ISCO 2010-International Symposium on Combinatorial Optimization ISCO10. International Symposium on Combinatorial Optimization ISCO10. International Symposium on Combinatorial Optimization, Mar 2010, Hammamet, Tunisia. pp.455-462, ⟨10.1016/j.endm.2010.05.058⟩ |
| DOI: | 10.1016/j.endm.2010.05.058⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|