Solving the p-median problem with a semi-Lagrangian relaxation

被引：64

作者：

Beltran, C. ^{[1
]}

Tadonki, C.

Vial, J. -Ph.

机构：

[1] Univ Geneva, HEC, Logilab, Geneva, Switzerland

[2] Univ Geneva, Ctr Informat, Geneva, Switzerland

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2006年 / 35卷 / 02期

关键词：

Lagrangian relaxation; combinatorial optimization; p-median problem;

D O I：

10.1007/s10589-006-6513-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];

摘要：

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem.

引用

页码：239 / 260

页数：22

共 27 条

[1]

[Anonymous], 1996, CONVEX ANAL MINIMIZA

[2]

[Anonymous], TSPLIB

[3]

On the p-Median polytope [J].