Exact procedures for solving the discrete ordered median problem

被引:44
作者
Boland, N
Domínguez-Marín, P
Nickel, S [1 ]
Puerto, J
机构
[1] Univ Saarland, Chair Operat Res & Logist, D-66041 Saarbrucken, Germany
[2] Univ Melbourne, Dept Math & Stat, Parkville, Vic 3010, Australia
[3] Univ Seville, Dept Estadist & IO, Fac Matemat, Seville 41012, Spain
关键词
discrete location; integer programming;
D O I
10.1016/j.cor.2005.03.025
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71-76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems. (c) 2005 Elsevier Ltd. All rights reserved.
引用
收藏
页码:3270 / 3300
页数:31
相关论文
共 21 条
[1]   Capacitated facility location: Separation algorithms and computational experience [J].
Aardal, K .
MATHEMATICAL PROGRAMMING, 1998, 81 (02) :149-175
[2]  
[Anonymous], FACILITY LOCATION AP
[3]  
Daskin M. S., 1995, NETWORK DISCRETE LOC
[4]   Heuristic procedures for solving the Discrete Ordered Median Problem [J].
Domínguez-Marín, P ;
Nickel, S ;
Hansen, P ;
Mladenovic, N .
ANNALS OF OPERATIONS RESEARCH, 2005, 136 (01) :145-173
[5]  
DOMINGUEZMARIN P, 2003, THESIS
[6]   The capacitated multiple allocation hub location problem: Formulations and algorithms [J].
Ebery, J ;
Krishnamoorthy, M ;
Ernst, A ;
Boland, N .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 120 (03) :614-631
[7]   Solution algorithms for the capacitated single allocation hub location problem [J].
Ernst, AT ;
Krishnamoorthy, M .
ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) :141-159
[8]   Aggregation error bounds for a class of location models [J].
Francis, RL ;
Lowe, TJ ;
Tamir, A .
OPERATIONS RESEARCH, 2000, 48 (02) :294-307
[9]  
Kalcsics J, 2000, OPERATIONS RESEARCH PROCEEDINGS 1999, P467
[10]   ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .2. P-MEDIANS [J].
KARIV, O ;
HAKIMI, SL .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (03) :539-560