Solving Large p-Median Problems with a Radius Formulation

被引：121

作者：

Garcia, Sergio ^{[1
]}

Labbe, Martine ^{[2
]}

Marin, Alfredo ^{[3
]}

机构：

[1] Univ Carlos III Madrid, Dept Estadist, Leganes 28911, Madrid, Spain

[2] Univ Libre Bruxelles, Dept Informat, B-1050 Brussels, Belgium

[3] Univ Murcia, Dept Estadist & Invest Operat, Espinardo 30100, Murcia, Spain

来源：

INFORMS JOURNAL ON COMPUTING | 2011年 / 23卷 / 04期

关键词：

discrete location; p-median; column-and-row generation; PLANT LOCATION PROBLEM; UNCAPACITATED FACILITY LOCATION; CANONICAL REPRESENTATION; GRAPH;

D O I：

10.1287/ijoc.1100.0418

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

By means of a model based on a set covering formulation, it is shown how the p-median problem can be solved with just a column generation approach that is embedded in a branch-and-bound framework based on dynamic reliability branching. This method is more than competitive in terms of computational times and size of the instances that have been optimally solved. In particular, problems of a size larger than the largest ones considered in the literature up to now are solved exactly in this paper.

引用

页码：546 / 556

页数：11

共 25 条

[1] Branching rules revisited [J].

Achterberg, T ;

Koch, T ;

Martin, A .

OPERATIONS RESEARCH LETTERS, 2005, 33 (01) :42-54

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

Avella, P ;

Sassano, A .

MATHEMATICAL PROGRAMMING, 2001, 89 (03) :395-411

[3] Computational study of large-scale p-Median problems [J].

Avella, Pasquale ;

Sassano, Antonio ;

Vasil'ev, Igor .

MATHEMATICAL PROGRAMMING, 2007, 109 (01) :89-114

[4] Solving the p-median problem with a semi-Lagrangian relaxation [J].

Beltran, C. ;

Tadonki, C. ;

Vial, J. -Ph. .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2006, 35 (02) :239-260

[5] The optimal diversity management problem [J].

Briant, O ;

Naddef, D .

OPERATIONS RESEARCH, 2004, 52 (04) :515-526

[6] A strengthened formulation for the simple plant location problem with order [J].

Canovas, Lazaro ;

Garcia, Sergio ;

Labbe, Martine ;

Marin, Alfredo .

OPERATIONS RESEARCH LETTERS, 2007, 35 (02) :141-150

[7] COBRA:: a new formulation of the classic p-median location problem [J].

Church, RL .

ANNALS OF OPERATIONS RESEARCH, 2003, 122 (1-4) :103-120

[8] A CANONICAL REPRESENTATION OF SIMPLE PLANT LOCATION-PROBLEMS AND ITS APPLICATIONS [J].

CORNUEJOLS, G ;

NEMHAUSER, GL ;

WOLSEY, LA .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (03) :261-272

[9]

Cornuejols G., 1990, Discrete Location Theory, P119

[10] BOOLEAN AND GRAPH THEORETIC FORMULATIONS OF THE SIMPLE PLANT LOCATION PROBLEM [J].

DEARING, PM ;

HAMMER, PL ;

SIMEONE, B .

TRANSPORTATION SCIENCE, 1992, 26 (02) :138-148

← 1 2 3 →