Computational study of large-scale p-Median problems

被引：127

作者：

Avella, Pasquale

Sassano, Antonio

Vasil'ev, Igor

机构：

[1] Univ Sannio, Res Ctr Software Technol, I-82100 Benevento, Italy

[2] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00185 Rome, Italy

[3] Univ Salerno, Ctr Ric Matemat Pura & Applicata, I-84084 Fisciano, SA, Italy

[4] Russian Acad Sci, Siberian Branch, Inst Syst Dynam & Control Theory, Irkutsk 664033, Russia

来源：

MATHEMATICAL PROGRAMMING | 2007年 / 109卷 / 01期

关键词：

p-Median; cutting plane; column generation; branch-and-cut-and-price algorithm;

D O I：

10.1007/s10107-005-0700-6

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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-and-Price algorithm yielding provably good solutions for instances with vertical bar V vertical bar <= 3795. Key ingredients of the algorithm are a delayed column-and-row generation technique, exploiting the special structure of the formulation, to solve the LP-relaxation, and cutting planes to strengthen the formulation and limit the size of the enumeration tree.

引用

页码：89 / 114

页数：26

共 41 条

[1]

[Anonymous], 1993, GEOMETRIC ALGORITHMS

[2] On the p-Median polytope [J].