A Simple Stabilizing Method for Column Generation Heuristics: An Application to P -Median Location Problems

The Lagrangean/surrogate relaxation has been explored as a faster computational alternative to traditional Lagrangean heuristics. In this work the Lagrangean/surrogate relaxation and traditional column generation approaches are combined in order to accelerate and stabilize primal and dual bounds, through an improved reduced cost selection. The Lagrangean/surrogate multiplier modifies the reduced cost criterion, resulting in the selection of more productive columns for the p-median problem, which deals with the localization of p facilities (medians) on a network in order to minimize the sum of all the distances from each demand point to its nearest facility. Computational tests running p-median instances taken from the literature are presented.