|
 
|
[BD07] An exact algorithm for the p-dispersion problem
Rapport Scientifique : Date de dépot: 2007/01/01, (Tech. Rep.: CEDRIC-07-1127)
motcle:
Résumé:
The p-dispersion problem consists in locating p facilities at some n predefined locations, such that the minimum distance between two facilities is as large as possible. In this paper we propose an algorithm based on a combination of two approaches: the determination of cliques in a graph and the solution of mixed integer linear programs. Computational results are reported which prove the efficiency of the method. For example, randomly generated instances with 150 facilities and any values of p or with 300 facilities and p greater than 140 can be solved in less than half an hour of CPU time, on the average.
Keywords: Location; clique; integer linear programming; experiments
BibTeX
| @techreport { | |||
| BD07, | |||
| title | = | "{An exact algorithm for the p-dispersion problem}", | |
| author | = | "A. Billionnet and K. Djebali", | |
| number | = | "{CEDRIC-07-1127}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2007}, | |
| } | |||
