Computational study of large-scale p-Median problems

Pasquale Avella (avellaunisannio.it)
Antonio Sassano (sassanodis.uniroma1.it)
Igor Vasil'ev (igordiima.unisa.it)

Abstract: Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure to choose

Keywords: p-Median, column-and-row generation, Branch-and-Cut

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Math. Program., Ser. A (2006) Digital Object Identifier (DOI) 10.1007/s10107-005-0700-6

Download:

Entry Submitted: 03/27/2003
Entry Accepted: 03/27/2003
Entry Last Modified: 04/24/2007

Modify/Update this entry