"A parallel implementation of the subgradient algorithm for maximizing the Lagrangian dual function in the p-median problem"
Vasilyev I.L., Ushakov A.V.

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

Vasilyev I.L., e-mail: vil@icc.ru;   Ushakov A.V., e-mail: aushakov@icc.ru – Institute for System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences; ulitsa Lermontova 134, Irkutsk, 664033, Russia