A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem

A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem

0.00 Avg rating0 Votes
Article ID: iaor20011171
Country: Netherlands
Volume: 124
Issue: 2
Start Page Number: 377
End Page Number: 389
Publication Date: Jul 2000
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

We compare heuristics based on Lagrangean and surrogate relaxations of the Maximal Covering Location Problem (MCLP). The Lagrangean relaxation of MCLP used in this paper has the integrality property and the surrogate relaxed problem we solve is the LP relaxation of the original 0–1 knapsack problem. The heuristics were compared using 331 test problems available in the literature, corresponding to networks ranging from 55 to 900 vertices. The gaps obtained with both heuristics were very low and did not differ substantially among themselves for the several problem sets used, in accordance with theoretical results reviewed in the paper. When the initial set of multipliers was determined using a valid bound for MCLP the comptuing times did not differ significantly between the Lagrangean and surrogate heuristics.

Reviews

Required fields are marked *. Your email address will not be published.