Abstract
We solve the vertex p-centre problem optimally using an exact method that considers both upper and lower bounds as part of its search engine. Tight upper bounds are generated quickly via an efficient three-level heuristic, which are then used to derive potential ‘lower bounds’ accordingly. These two pieces of information when used together make our chosen exact method more efficient at obtaining optimal solutions relatively quickly. The proposed implementation produced excellent results when tested on the OR Library data set. This integrated approach can be adopted for those exact methods that consider both upper and lower bounds within their search engine and hence provide a wider spectrum of applicability in other hard combinatorial problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Al-Khedhairi A and Salhi S (2005). Enhancement to two exact algorithms for solving the vertex p-center problem . J Math Model Algorithms 4: 129–147.
Archetti C, Speranza MG and Savelsbergh MWP (2008). An optimization-based heuristic for the split delivery vehicle routing problem . Transport Sci 42: 22–31.
Beasley JE (1985). A note on solving large p-median problems . Eur J Opl Res 21: 270–273.
Beasley JE (1990). OR library: Distributing test problems by electronic mail . J Opl Res Soc 41: 1069–1072.
Boender CGE, Rinnooy Kan AHG, Timmer GT and Stougie L (1982). A stochastic method for global optimization . Math Program 22: 125–140.
Daskin MS (1995). Network and Discrete Locations: Models, Algorithms, and Applications . John Wiley & Sons: New York pp. 154–191.
Daskin M (2000). A new approach to solve the vertex p-center problem to optimality: Algorithm and computational results . Commun Opns Res Soc Japan 45: 428–436.
Derigs U (1985). Using confidence limits for the global optimum in combinatorial optimization . Opns Res 33: 1024–1049.
Elloumi S, Labbé M, Pochet Y (2001). New formulation and resolution method for the p-center problem, http://www.optimization-online.org/DB_HTML/2001/10/394.html.
Floyd RW (1962). Algorithm 97, shortest path . Commun ACM 5: 345.
Golden BL and Alt FB (1979). Interval estimation of a global optimum for large combinatorial problems . Nav Res Logist Q 26: 69–77.
Hakimi SL (1964). Optimum locations of switching centers and the absolute centers and medians of a graph . Opns Res 12: 450–459.
Hanafi S and Freville A (1998). An efficient tabu search approach for the 0–1 multidimensional knapsack problem . Eur J Opl Res 106: 659–675.
Hansen P and Mladenović N (2003). Variable neighborhood search . In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer Academic Publisher: Dordrecht, pp. 145–184.
Ilhan T, Pinar MC . (2001). An efficient exact algorithm for the vertex p-center problem. http://www.optimization-online.org/DB_HTML/2001/09/376.html.
Kariv O and Hakimi S (1979). An algorithmic approach to network location problems. Part I: The p-centers . SIAM J Appl Math 37: 513–538.
Melian B, Mladenović N (eds) (2007). Applications of variable neighborhood search. IMA J Mngt Math 18: 99–221.
Minieka E (1970). The m-center problem . SIAM Rev 12: 138–139.
Mladenović N and Hansen P (1997). Variable neighborhood search . Comput Opl Res 24: 1097–1100.
Mladenović N, Labbe M and Hansen P (2003). Solving the p-center problem with tabu search and variable neighbourhood search . Networks 42: 48–64.
Rardin RL and Uzsoy R (2001). Experimental evaluation of heuristic optimization algorithms: A tutorial . J Heuristics 7: 261–304.
Reinelt G (1991). TSPLIB–A traveling salesman problem library . ORSA J Comput 3: 376–384.
Robson D and Whitlock J (1964). Estimation of a truncation point . Biometrika 51: 33–39.
Rosing KE and ReVelle CS (1997). Heuristic concentration: Two stage solution construction . Eur J Opl Res 97: 75–86.
Salhi S (1997). A perturbation heuristic for a class of location problems . J Opl Res Soc 48: 1233–1240.
Salhi S (2006). Heuristic search: The science of tomorrow . In: Salhi S (ed). OR48 Keynote Papers. Operational Research Society: Birmingham, pp. 39–58.
Salhi S and Sari M (1997). A multi-level composite heuristic for the multi depot vehicle fleet mix problem . Eur J Opl Res 103: 78–95.
Wilbaut C, Salhi S and Hanafi S (2009). An iterative variable-based fixation heuristic for the 0–1 multidimensional knapsack problem . Eur J Opl Res 199: 339–348.
Acknowledgements
We are grateful to the referees for their constructive comments that improved both the quality and the content of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Salhi, S., Al-Khedhairi, A. Integrating heuristic information into exact methods: The case of the vertex p-centre problem. J Oper Res Soc 61, 1619–1631 (2010). https://doi.org/10.1057/jors.2009.91
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.91