Upper bounds and exact algorithms for \(p\)-dispersion problems. (English) Zbl 1092.90027
Summary: The \(p\)-dispersion-sum problem is the problem of locating \(p\) facilities at some of \(n\) predefined locations, such that the distance sum between the \(p\) facilities is maximized. The problem has applications in telecommunication (where it is desirable to disperse the transceivers in order to minimize interference problems), and in location of shops and service-stations (where the mutual competition should be minimized).
A number of fast upper bounds are presented based on Lagrangian relaxation, semidefinite programming and reformulation techniques. A branch-and-bound algorithm is then derived, which at each branching node is able to compute the reformulation-based upper bound in \(O(n)\) time. Computational experiments show that the algorithm may solve geometric problems of size up to \(n=90\), and weighted geometric problems of size \(n=250\).
The related \(p\)-dispersion problem is the problem of locating \(p\) facilities such that the minimum distance between two facilities is as large as possible. New formulations and fast upper bounds are presented, and it is discussed whether a similar framework as for the \(p\)-dispersion sum problem can be used to tighten the upper bounds. A solution algorithm based on transformation of the \(p\)-dispersion problem to the \(p\)-dispersion-sum problem is finally presented, and its performance is evaluated through several computational experiments.
A number of fast upper bounds are presented based on Lagrangian relaxation, semidefinite programming and reformulation techniques. A branch-and-bound algorithm is then derived, which at each branching node is able to compute the reformulation-based upper bound in \(O(n)\) time. Computational experiments show that the algorithm may solve geometric problems of size up to \(n=90\), and weighted geometric problems of size \(n=250\).
The related \(p\)-dispersion problem is the problem of locating \(p\) facilities such that the minimum distance between two facilities is as large as possible. New formulations and fast upper bounds are presented, and it is discussed whether a similar framework as for the \(p\)-dispersion sum problem can be used to tighten the upper bounds. A solution algorithm based on transformation of the \(p\)-dispersion problem to the \(p\)-dispersion-sum problem is finally presented, and its performance is evaluated through several computational experiments.
References:
| [1] | Asahiro Y, Iwama K, Tamaki H, Tokuyama T. Greedily finding a dense subgraph. In: Karlsson RG, Lingas A, editors. Algorithm theory—SWAT ’96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavik, Iceland, July, vol. 1097. Berlin: Springer; 1996. p. 136-48.; Asahiro Y, Iwama K, Tamaki H, Tokuyama T. Greedily finding a dense subgraph. In: Karlsson RG, Lingas A, editors. Algorithm theory—SWAT ’96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavik, Iceland, July, vol. 1097. Berlin: Springer; 1996. p. 136-48. · Zbl 0958.68132 |
| [2] | Hansen P, Moon ID. Dispersing facilities on a network. Presentation at the TIMS/ORSA Joint National Meeting, Washington, D.C.; 1988.; Hansen P, Moon ID. Dispersing facilities on a network. Presentation at the TIMS/ORSA Joint National Meeting, Washington, D.C.; 1988. · Zbl 0840.90097 |
| [3] | Erkut, E., The discrete \(p\)-dispersion problem, European Journal of Operational Research, 46, 48-60 (1990) · Zbl 0702.90050 |
| [4] | Ravi, S. S.; Rosenkrantz, D. J.; Tayi, G. K., Heuristic and special case algorithms for dispersion problems, Operations Research, 42, 299-310 (1994) · Zbl 0805.90074 |
| [5] | Kortsarz G, Peleg D. On choosing a dense subgraph. In: Proceedings of the 34th Annual IEEE Symposium on Foundation of Computer Science. New York: Institute of Electrical and Electronics Engineers; 1993. p. 692-701.; Kortsarz G, Peleg D. On choosing a dense subgraph. In: Proceedings of the 34th Annual IEEE Symposium on Foundation of Computer Science. New York: Institute of Electrical and Electronics Engineers; 1993. p. 692-701. |
| [6] | Srivastav A, Wolf K. Finding dense subgraphs with semidefinite programming. In: Jansen K, Rolim J, editors. Approximation algorithms for combinatorial optimization. Lecture Notes in Computer Science, vol. 1444. Berlin: Springer; 1998. p. 181-91.; Srivastav A, Wolf K. Finding dense subgraphs with semidefinite programming. In: Jansen K, Rolim J, editors. Approximation algorithms for combinatorial optimization. Lecture Notes in Computer Science, vol. 1444. Berlin: Springer; 1998. p. 181-91. · Zbl 0911.90340 |
| [7] | Hassin, R.; Rubinstein, S.; Tamir, A., Approximation algorithms for maximum dispersion, Operations Research Letters, 21, 133-137 (1997) · Zbl 0888.90144 |
| [8] | Corneil, D. G.; Perl, Y., Clustering and domination in perfect graphs, Discrete Applied Mathematics, 9, 27-40 (1984) · Zbl 0581.05053 |
| [9] | Kincaid, R. K., Good solutions to discrete noxious location problems via metaheuristics, Annals of Operations Research, 40, 265-281 (1992) · Zbl 0782.90061 |
| [10] | Billionnet, A.; Faye, A., A lower bound for a constrained quadratic 0-1 minimization problem, Discrete Applied Mathematics, 74, 135-146 (1997) · Zbl 0879.90147 |
| [11] | Hammer, P. L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming, 28, 121-155 (1984) · Zbl 0574.90066 |
| [12] | Asahiro, Y.; Hassin, R.; Iwama, K., Complexity of finding dense subgraphs, Discrete Applied Mathematics, 121, 1-3, 15-26 (2002) · Zbl 1002.68108 |
| [13] | Michelon, P.; Veilleux, L., Lagrangean methods for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92, 326-341 (1996) · Zbl 0912.90222 |
| [14] | Hammer, P. L.; Rader, D. J., Efficient methods for solving quadratic 0-1 knapsack problems, INFOR, 35, 170-182 (1997) · Zbl 0888.90121 |
| [15] | Billionnet, A.; Faye, A.; Soutif, E., A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 112, 664-672 (1999) · Zbl 0933.90049 |
| [16] | Pisinger D, Rasmussen AB, Sandvik R. Solution of large-sized quadratic knapsack problems through aggressive reduction. INFORMS Journal on Computing, 2005, to appear.; Pisinger D, Rasmussen AB, Sandvik R. Solution of large-sized quadratic knapsack problems through aggressive reduction. INFORMS Journal on Computing, 2005, to appear. · Zbl 1241.90119 |
| [17] | Caprara, A.; Pisinger, D.; Toth, P., Exact solution of the quadratic knapsack problem, INFORMS Journal on Computing, 11, 125-137 (1999) · Zbl 1034.90521 |
| [18] | Krarup, J.; Pisinger, D.; Plastria, F., Discrete location problems with push-pull objectives, Discrete Applied Mathematics, 123, 363-378 (2002) · Zbl 1012.90028 |
| [19] | Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problems, Mathematical Programming, 12, 132-149 (1980) · Zbl 0462.90068 |
| [20] | Carraresi, P.; Malucelli, F., A reformulation scheme and new lower bounds for the qap, (Pardalos, P. M.; Wolkowicz, H., Quadratic assignment and related problems (1994), American Mathematical Society Press: American Mathematical Society Press Providence, RI), 147-160 · Zbl 0817.90054 |
| [21] | Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning treesPart ii, Mathematical Programming, 1, 6-25 (1971) · Zbl 0232.90038 |
| [22] | Chaillou P, Hansen P, Mahieu Y. Best network flow bound for the quadratic knapsack problem. In: Simeone B, editor. Combinatorial optimization. Lecture Notes in Mathematics, vol. 1403. Berlin: Springer; 1986. p. 225-35.; Chaillou P, Hansen P, Mahieu Y. Best network flow bound for the quadratic knapsack problem. In: Simeone B, editor. Combinatorial optimization. Lecture Notes in Mathematics, vol. 1403. Berlin: Springer; 1986. p. 225-35. · Zbl 0678.90061 |
| [23] | Geoffrion, A. M., Lagrangian relaxation for integer programming, Mathematical Programming Study, 2, 82-114 (1974) · Zbl 0395.90056 |
| [24] | Karzanov, A. V., Determining the maximal flow in a network by the method of preflow, Soviet Mathematics Doklady, 15, 434-437 (1974) · Zbl 0303.90014 |
| [25] | Helmberg, C.; Rendl, F.; Weismantel, R., Quadratic knapsack relaxations using cutting planes and semidefinite programming, (Lecture Notes in Computer Science, vol. 1084 (1996)), 175-189 · Zbl 1415.90073 |
| [26] | Helmberg, C.; Rendl, F.; Weismantel, R., A semidefinite programming approach to the quadratic knapsack problem, Journal of Combinatorial Optimization, 4, 197-215 (2000) · Zbl 0970.90075 |
| [27] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsck problems (2004), Springer: Springer Berlin · Zbl 1103.90003 |
| [28] | Billionnet, A.; Calmels, F., Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92, 310-325 (1996) · Zbl 0912.90221 |
| [29] | Johnson DS, Trick MA, editors. Cliques, coloring and satisfiability: 2nd DIMACS implementation challenge. DIMACS Series in: Discrete Mathematics and Theoretical Computer Science. Providence, RI: American Mathematical Society Press; 1996.; Johnson DS, Trick MA, editors. Cliques, coloring and satisfiability: 2nd DIMACS implementation challenge. DIMACS Series in: Discrete Mathematics and Theoretical Computer Science. Providence, RI: American Mathematical Society Press; 1996. |
| [30] | Pisinger D. Exact Solution of p-dispersion problems, Technical Report 99/14, DIKU, University of Copenhagen, Denmark; 1999.; Pisinger D. Exact Solution of p-dispersion problems, Technical Report 99/14, DIKU, University of Copenhagen, Denmark; 1999. · Zbl 0948.90110 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
