Optimization Online


Solving large p-median problems using a Lagrangean heuristic

Andréa Cynthia Santos (andrea***at***isima.fr)

Abstract: The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean relaxation. Variable fixing tests are used to reduce the size of the problems and a local search procedure is also applied. Variable fixing strategies eliminate 90% of arcs on average. Computational results are reported for large graph instances with about 4000 nodes and 14 millions arcs.

Keywords: Lagrangean heuristics, primal-dual heuristics, p-median problem

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )

Citation: Technical report RR-09-03, 2009. Limos, Université Blaise Pascal. Complexe scientifique des Cézeaux, Aubière, France.

Download: [Postscript]

Entry Submitted: 06/03/2009
Entry Accepted: 06/08/2009
Entry Last Modified: 06/08/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society