×

zbMATH — the first resource for mathematics

Enhancements to two exact algorithms for solving the vertex \(P\)-center problem. (English) Zbl 1093.90004
Summary: Enhancements to two exact algorithms from the literature to solve the vertex \(P\)-center problem are proposed. In the first approach modifications of some steps are introduced to reduce the number of ILP iterations needed to find the optimal solution. In the second approach a simple enhancement which uses tighter initial lower and upper bounds, and a more appropriate binary search method are proposed to reduce the number of subproblems to be solved. These ideas are tested on two well known sets of problems from the literature (i.e., OR-Lib and TSP-Lib problems) with encouraging results.

MSC:
90B10 Deterministic network models in operations research
90B80 Discrete location and assignment
90C09 Boolean programming
90C47 Minimax problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beasley, J. E.: A note on solving large P-median problems, European J. Oper. Res. 21 (1985), 270–273. · Zbl 0569.90021
[2] Beasley, J. E.: OR library: Distributing test problems by electronic mail, J. Oper. Res. Soc. 41(11) (1990), 1069–1072.
[3] Daskin, M. S.: Network and Discrete Locations: Models, Algorithms, and Applications, Wiley, New York, 1995, pp. 154–191.
[4] Daskin, M.: A new approach to solve the vertex P-center problem to optimality: Algorithm and computational results, Comm. Oper. Res. Soc. Japan 45(9) (2000), 428–436.
[5] Elloumi, S., LabbĂ©, M. and Pochet, Y.: New formulation and resolution method for the P-center problem, http://www.optimization-online.org/DB.HTML/2001/10/394.html, 2001. · Zbl 1239.90103
[6] Floyd, R.W.: Algorithm 97, Shortest Path, Comm. Assoc. Comput. Mach. 5 (1962), 345.
[7] Hakimi, S. L.: Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964), 450–459. · Zbl 0123.00305
[8] Hakimi, S. L.: Optimum distribution of switching centers in a communications network and some related graph theoretic problems, Oper. Res. 13 (1965), 462–475. · Zbl 0135.20501
[9] Ilhan, T. and Pinar, M.C.: An efficient exact algorithm for the vertex P-center problem, http://www.optimization-online.org/DB.HTML/2001/09/376.html, 2001.
[10] Kariv, O. and Hakimi, S.: An algorithmic approach to network location problems. Part I: The P-centers, SIAM J. Appl. Math. 37 (1979), 513–538. · Zbl 0432.90074
[11] Minieka, E.: The m-center problem, SIAM Rev. 12 (1970), 138–139. · Zbl 0193.24204
[12] Reinelt, G.: TSPLIB – A traveling salesman problem library, ORSA J. Comput. 3 (1991), 376–384. · Zbl 0775.90293
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.