Abordagens complementares para problemas de p-medianas

The search for p-median vertices on a network is a classical combinatorial optimization problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand vertex to its nearest facility is minimized. This work presents the lagrangean/surrogate relaxation as a technique for solving such combinatorial problems. The paper discusses the use of this relaxation combined with subgradient optimization methods and with column generation methods. Computational tests which demonstrate the eficiency of the proposed approaches for solving p-median instances taken from the literature and obtained