Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0967.90068
Galvão, Roberto D.; Acosta Espejo, Luis Gonzalo; Boffey, Brian
A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. (English)
[J] Eur. J. Oper. Res. 124, No.2, 377-389 (2000). ISSN 0377-2217

Summary: 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 computing times did not differ significantly between the Lagrangean and surrogate heuristics.

MSC 2000:: *90B80 Discrete location and assignment

Keywords: location; heuristics; Lagrangean relaxation; surrogate relaxation; covering problems

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]