Вычислительные методы и приложения

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

I. L. Vasiliev, A. V. Ushakov

Institute of System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk

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.

Keywords: $p$-median problem, parallel programming, Lagrangian relaxation, subgradient method, MPI.

UDC: 519.854.2; 004.272.2

Received: 19.11.2012