A parallel implementation of the subgradient algorithm for maximizing the Lagrangian dual function in the p-median problem

Authors

  • I.L. Vasilyev
  • A.V. Ushakov

Keywords:

p-median problem
parallel programming
Lagrangian relaxation
subgradient method
MPI

Abstract

An algorithm for searching lower bounds of the optimal value in the p-median problem is considered on the basis of constructing a Lagrangian relaxation and minimizing the resulting Lagrangian dual function with the subgradient algorithm. An efficient parallel scheme involving the procedure of hierarchical collection of data is proposed. The developed algorithm is tested using a wide range of large-scale model problems taken from the literature and synthetically generated. The numerical results obtained confirm the efficiency of the proposed parallel scheme.

New computational technologies

Downloads

Published

2013-01-14

Issue

Vol. 14 (2013): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

I.L. Vasilyev

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
• Associate Professor, Leading Researcher

A.V. Ushakov

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
• Programmer

References

  1. Васильев И.Л., Ушаков А.В. Релаксации Лагранжа для нелинейной задачи о p-медиане // Известия ИГУ. Серия «Математика». 2011. 4, № 2. 45-60.
  2. Avella P., Boccia M., Salerno S., Vasilyev I. An aggregation heuristic for large scale p-median problem // Computers &; Operations Research. 2012. 39, N 7. 1625-1632.
  3. Crainic T.G., Gendreau M., Hansen P., Mladenovi’c N. Cooperative parallel variable neighborhood search for the p-median // Journal of Heuristics. 2004. 10, N 3. 293-314.
  4. Garciá-L’opez F. Parallelization of the scatter search for the p-median problem // Parallel Computing. 2003. 29, N 3. 575-589.
  5. Garc’ia S., Labbé M., Mar’in A. Solving large p-median problems with a radius formulation // INFORMS Journal on Computing. 2011. 23, N 4. 546-556.
  6. Hakimi S.L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems // Operations Research. 1964. 13, N 3. 462-475.
  7. Hanafi S., Salerno S., Ushakov A., Vasilyev I. A parallel subgradient algorithm for Lagrangean dual function of the p-median problem // Studia Informatica Universalis. 2011. 9, N 3. 105-124.
  8. Hansen P., Brimberg J., Urosevi’c D., Mladenovi’c N. Solving large p-median clustering problems by primal-dual variable neighborhood search // Data Mining and Knowledge Discovery. 2009. 19, N 3. 351-375.
  9. Kariv O., Hakimi S.L. An algorithmic approach to network location problems; part 2. The p-medians // SIAM Journal on Applied Mathematics. 1979. 37, N 3. 539-560.
  10. Ma L., Lim G. GPU-based parallel computational algorithms for solving p-median problem // Proc. of the IIE Annual Conference. Reno (Nevada, USA), 2011. ID: 1110.
  11. Mladenovi’c N., Brimberg J., Hansen P., Moreno-Pérez J.A. The p-median problem: A survey of metaheuristic approaches // EJOR. 2007. 179, N 3. 927-939.
  12. Moreno-Vega J.M. The parallel variable neighborhood search for the p-median problem // Journal of Heuristics. 2002. 8, N 3. 375-388.
  13. Reese J. Solution methods for the p-median problem: An annotated bibliography // Networks. 2006. 28, N 3. 125-142.
  14. Zhang T., Ramakrishnan R., Livny M. BIRCH: an efficient data clustering method for very large databases // Journal of the American Statistical Association. 1996. 98, N 463. 103-114.
  15. Вычислительный кластер Blackford [Электронный ресурс] // Иркутский суперкомпьютерный центр СО РАНlinebreak (http://hpc.icc.ru/hardware/blackford.php).
  16. Gropp W., Thakur R., Lusk E. Using MPI-2: advanced features of the message passing interface. Cambridge: MIT Press, 1999.
  17. Васильев И.Л., Климентова К.Б., Орлов А.В. Параллельный глобальный поиск равновесных ситуаций в биматричных играх // Вычислительные методы и программирование. 2007. 8, № 1. 233-243.
  18. Lim G.J., Ma L. GPU-based parallel vertex substitution algorithm for the p-median problem // Computers &; Industrial Engineering. 2013. 64, № 1. 381-388.