Inverse median problems. (English) Zbl 1087.90038
Summary: The inverse \(p\)-median problem consists in changing the weights of the customers of a \(p\)-median location problem at minimum cost such that a set of \(p\) prespecified suppliers becomes the \(p\)-median. The cost is proportional to the increase or decrease of the corresponding weight. We show that the discrete version of an inverse \(p\)-median problem can be formulated as a linear program. Therefore, it is polynomially solvable for fixed \(p\) even in the case of mixed positive and negative customer weights. In the case of trees with nonnegative vertex weights, the inverse 1-median problem is solvable in a greedy-like fashion. In the plane, the inverse 1-median problem can be solved in \(O(n \log n)\) time, provided the distances are measured in \(l_1\)- or \(l_{\infty}\)-norm, but this is not any more true in \(\mathbb R^3\) endowed with the Manhattan metric.
MSC:
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 49N45 | Inverse problems in optimal control |
References:
| [1] | Berman, O.; Ingco, D. I.; Odoni, A. R., Improving the location of minisum facilities through network modification, Ann. Oper. Res., 40, 1-16 (1992) · Zbl 0787.90035 |
| [2] | Berman, O.; Ingco, D. I.; Odoni, A. R., Improving the location of minimax facilities through network modification, Networks, 24, 31-41 (1994) · Zbl 0799.90074 |
| [3] | Burton, D.; Toint, Ph. L., On an instance of the inverse shortest path problem, Math. Programming, 53, 45-61 (1992) · Zbl 0756.90089 |
| [4] | Cai, M. C.; Yang, X. G.; Zhang, J. Z., The complexity analysis of the inverse center location problem, J. Global Optim., 15, 213-218 (1999) · Zbl 0978.90065 |
| [5] | P. Cappanera, A survey on obnoxious facility location problems, Report TR-99-11, Dip. di Informatica, Univ. di Pisa, 1999.; P. Cappanera, A survey on obnoxious facility location problems, Report TR-99-11, Dip. di Informatica, Univ. di Pisa, 1999. |
| [6] | Dantzig, G. B., Linear Programming and Extensions (1998), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0997.90504 |
| [7] | Goldman, A. J., Optimal center location in simple networks, Transportation Sci., 2, 77-91 (1962) |
| [8] | Hamacher, H. W., Mathematische Lösungsverfahren für planare Standortprobleme (1995), Vieweg: Vieweg Braunschweig/Wiesbaden |
| [9] | C. Heuberger, Inverse optimization: a survey on problems, methods, and results, SFB Report No. 219, Institute of Mathematics B, Graz University of Technology, Graz (Austria), May 2001; J. Combin. Optim. (2004), to appear.; C. Heuberger, Inverse optimization: a survey on problems, methods, and results, SFB Report No. 219, Institute of Mathematics B, Graz University of Technology, Graz (Austria), May 2001; J. Combin. Optim. (2004), to appear. |
| [10] | Hua, et al., Applications of mathematical models to wheat harvesting, Acta Mathematica Sinica 11 (1961) 63-75 (in Chinese) (English translation in Chinese Math. 2, 1962, 77-91).; Hua, et al., Applications of mathematical models to wheat harvesting, Acta Mathematica Sinica 11 (1961) 63-75 (in Chinese) (English translation in Chinese Math. 2, 1962, 77-91). |
| [11] | Plastria, F., Optimal location of undesirable facilitiesa selective overview, Belg. J. Oper. Res. Statist. Comput. Sci., 36, 109-127 (1996) · Zbl 0883.90079 |
| [12] | Zhang, J.; Liu, Z.; Ma, Z., Some reverse location problems, European J. Oper. Res., 124, 77-88 (2000) · Zbl 0960.90056 |
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.
