Minmax regret solutions for minimax optimization problems with uncertainty. (English) Zbl 0988.90026
Summary: We propose a general approach for finding minmax regret solutions for a class of combinatorial optimization problems with an objective function of minimax type and uncertain objective function coefficients. The approach is based on reducing a problem with uncertainty to a number of problems without uncertainty. The method is illustrated on bottleneck combinatorial optimization problems, minimax multifacility location problems and maximum weighted tardiness scheduling problems with uncertainty.
MSC:
| 90C27 | Combinatorial optimization |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Averbakh, I.; Berman, O., Bottleneck Steiner subnetwork problems with \(k\)-connectivity constraints, INFORMS J. Comput., 8, 4, pp 361, 366 (1996) · Zbl 0884.90142 |
| [2] | I. Averbakh, O. Berman, Minmax regret median location on a network under uncertainty, INFORMS J. Comput., to appear.; I. Averbakh, O. Berman, Minmax regret median location on a network under uncertainty, INFORMS J. Comput., to appear. · Zbl 1034.90007 |
| [3] | I. Averbakh, O. Berman, Minmax regret \(p\)-center location on a network with demand uncertainty, Working paper, University of Toronto, Faculty of Management, Toronto, 1996.; I. Averbakh, O. Berman, Minmax regret \(p\)-center location on a network with demand uncertainty, Working paper, University of Toronto, Faculty of Management, Toronto, 1996. |
| [4] | Berman, O.; Handler, G. Y., Optimal minimax path of a single service unit on a network to nonservice destinations, Transp. Sci., 21, 115-122 (1987) · Zbl 0631.90023 |
| [5] | Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0931.68015 |
| [6] | Camerini, P. M., The minimax spanning tree problem and some extensions, Inform. Process. Lett., 7, 10-14 (1978) · Zbl 0373.05028 |
| [7] | Cesa-Bianchi, N.; Freund, Y.; Helmbold, D.; Haussler, D.; Schapire, R.; Warmuth, M., How to use expert advice, J. Assoc. Comput. Mach., 44, 3, 427-485 (1997) · Zbl 0890.68066 |
| [8] | Chang, M. S.; Tang, C. Y.; Lee, R. C.T., Solving Euclidean bottleneck biconnected edge subgraph problem by 2-relative neighborhood graphs, Discrete Appl. Math., 39, 1-12 (1992) · Zbl 0768.68125 |
| [9] | Chen, B.; Lin, C., Robust one-median location problem, Networks, 31, 93-103 (1998) · Zbl 0930.90050 |
| [10] | Chhajed, D.; Lowe, T., \(m\)-median and \(m\)-center problems with mutual communication: solvable special cases, Oper. Res., 40, S56-S66 (1992) · Zbl 0761.90064 |
| [11] | Cover, T. M., Universal portfolios, Math. Finance, 1, 1, 1-29 (1991) · Zbl 0900.90052 |
| [12] | Erkut, E.; Francis, R. L.; Tamir, A., Distance constrained multifacility minimax location problems on tree networks, Networks, 22, 37-54 (1992) · Zbl 0751.90043 |
| [13] | Francis, R. L.; Lowe, T. J.; Ratliff, H. D., Distance constraints for tree network multifacility location problems, Oper. Res., 26, 571-596 (1978) · Zbl 0385.90112 |
| [14] | P. Hansen, Bicriterion Path Problems, Lecture Notes in Economics and Mathematical Systems, Vol. 177, Springer, Berlin, 1980, pp. 109-127.; P. Hansen, Bicriterion Path Problems, Lecture Notes in Economics and Mathematical Systems, Vol. 177, Springer, Berlin, 1980, pp. 109-127. · Zbl 0444.90098 |
| [15] | Kall, P.; Wallace, S., Stochastic Programming (1994), Wiley: Wiley New York · Zbl 0812.90122 |
| [16] | A. Kolen, Tree network and planar location theory, Center for Mathematics and Computer Science, P.O.Box 4079, 1009 AB Amsterdam, The Netherlands, 1986.; A. Kolen, Tree network and planar location theory, Center for Mathematics and Computer Science, P.O.Box 4079, 1009 AB Amsterdam, The Netherlands, 1986. |
| [17] | P. Kouvelis, G. Vairaktarakis, G. Yu, Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty, Working paper 93/94-3-4, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas at Austin.; P. Kouvelis, G. Vairaktarakis, G. Yu, Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty, Working paper 93/94-3-4, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas at Austin. |
| [18] | Kouvelis, P.; Yu, G., Robust Discrete Optimization and Its Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0873.90071 |
| [19] | Labbe, M.; Thisse, J.-F.; Wendell, R. E., Sensitivity analysis in minisum facility location problems, Oper. Res., 39, 6, 961-969 (1991) · Zbl 0748.90037 |
| [20] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059 |
| [21] | Meggido, N., Combinatorial optimization with rational objective functions, Math. Oper. Res., 4, 414-424 (1979) · Zbl 0425.90076 |
| [22] | Mirchandani, P. B.; Francis (Eds.), R. L., Discrete Location Theory (1990), Wiley: Wiley New York · Zbl 0718.00021 |
| [23] | Parker, R. G.; Rardin, R. L., Guaranteed performance heuristics for bottleneck traveling salesman problem, Oper. Res. Lett., 2, 269-272 (1984) · Zbl 0528.90084 |
| [24] | Pinedo, M., Scheduling (1995), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90393 |
| [25] | Punnen, A. P., A linear time algorithm for the maximum capacity path problem, Eur. J. Oper. Res., 53, 402-404 (1991) · Zbl 0732.90085 |
| [26] | Punnen, A. P.; Nair, K. P.K., A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, Inform. Process. Lett., 50, 283-286 (1994) · Zbl 0814.68099 |
| [27] | B. Tansel, G. Yesilkokcen, Polynomially solvable cases of multifacility distance constraints on cyclic networks, ISOLDE-6 Proceedings 1993, pp. 269-273.; B. Tansel, G. Yesilkokcen, Polynomially solvable cases of multifacility distance constraints on cyclic networks, ISOLDE-6 Proceedings 1993, pp. 269-273. |
| [28] | Vairaktarakis, G.; Kouvelis, P., Incorporation dynamic aspects and uncertainty in 1-median location problems, Naval Res. Logistics, 46, 147-168 (1999) · Zbl 0918.90101 |
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.
