×

Computing upper and lower bounds in interval decision trees. (English) Zbl 1131.91016

Summary: This article presents algorithms for computing optima in decision trees with imprecise probabilities and utilities. In tree models involving uncertainty expressed as intervals and/or relations, it is necessary for the evaluation to compute the upper and lower bounds of the expected values. Already in its simplest form, computing a maximum of expectancies leads to quadratic programming (QP) problems. Unfortunately, standard optimization methods based on QP (and BLP–bilinear programming) are too slow for the evaluation of decision trees in computer tools with interactive response times. Needless to say, the problems with computational complexity are even more emphasized in multi-linear programming (MLP) problems arising from multi-level decision trees. Since standard techniques are not particularly useful for these purposes, other, non-standard algorithms must be used. The algorithms presented here enable user interaction in decision tools and are equally applicable to all multi-linear programming problems sharing the same structure as a decision tree.

MSC:

91B06 Decision theory
90C10 Integer programming

Software:

CG+
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arioli, M., The use of QR factorisation in sparse quadratic programming and backward error issues, SIAM Journal on Matrix Analysis and Applications, 21, 3, 825-839 (2000) · Zbl 0958.65067
[2] Beale, E. M.L., On minimizing a convex function subject to linear inequalities, Journal of the Royal Statistical Society, (Series B), 17, 173-184 (1955) · Zbl 0068.13701
[3] Benson, H. Y.; Shanno, D. F.; Vanderbei, R. J., A comparative study of large-scale non-linear optimization algorithms. A comparative study of large-scale non-linear optimization algorithms, Operations Research and Financial Engineering (2001), Princeton University
[4] Benveniste, R., A quadratic programming algorithm using conjugate search directions, Mathematical Programming, 16, 1, 63-80 (1979) · Zbl 0399.90063
[5] Berkelaar, A. B.; Jansen, B.; Roos, C.; Terlaky, T., Basis and partition identification for quadratic programming and linear complementarity problems, Mathematical Programming, 86, 2, 261-282 (1999) · Zbl 0946.90091
[6] Boland, N. L., A dual active set algorithm for positive semi-definite quadratic programming, Mathematical Programming, 78, 1, 1-27 (1997) · Zbl 0893.90139
[7] Brouwers, L.; Danielson, M.; Ekenberg, L.; Hansson, K., Simulation and decision analysis of flood management strategies, Journal of Risk, Decision, and Policy, 9, 1, 23-45 (2004)
[8] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press USA · Zbl 0757.90078
[9] Danielson, M., Handling imperfect user statements in real-life decision analysis, International Journal of Information Technology and Decision Making, 3, 3, 513-534 (2004)
[10] Danielson, M., Generalized evaluation in decision analysis, European Journal of Operational Research, 162, 2, 442-449 (2005) · Zbl 1071.90545
[11] Danielson, M.; Ekenberg, L., A framework for analysing decisions under risk, European Journal of Operational Research, 104, 474-484 (1998) · Zbl 0960.91505
[12] Danielson, M.; Ekenberg, L.; Johansson, J.; Larsson, A., The DecideIT decision tool, (Bernard, J.-M.; Seidenfeld, T.; Zaffalon, M., Proceedings of ISIPTA’03 (2003), Carleton Scientific), 204-217
[13] Danielson, M.; Ekenberg, L.; Grönlund, Å.; Larsson, A., Public decision support – using a DSS to increase democratic transparency, International Journal of Public Information Systems, 1, 3-25 (2005)
[14] Dantzig, G. B., Quadratic programming, (Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, USA), 490-498, (Chapter 12.4)
[15] Ding, X. S.; Danielson, M.; Ekenberg, L., Non-linear programming solvers for decision analysis support systems, (Ahr, D.; Fahrion, R.; Oswald, M.; Reinelt, G., Operations Research Proceedings 2003 - Selected Papers of the International Conference on Operations Research (OR 2003) (2003), Springer-Verlag), 475-482
[16] Ding, X. S.; Ekenberg, L.; Danielson, M., A fast bilinear optimization algorithm, (Proceedings of Nonlinear Analysis and Convex Analysis (NACA 2003) (2004), Tokyo Institute of Technology: Tokyo Institute of Technology Tokyo) · Zbl 1151.90548
[17] Ekenberg, L.; Boman, M.; Linneroth-Bayer, J., General risk constraints, Journal of Risk Research, 4, 1, 31-47 (2001)
[18] Ekenberg, L., Brouwers, L., Danielson, M., Hansson, K., Johansson, J., Riabacke, A., Vári, A., 2003. Flood Risk Management Policy in the Upper Tisza Basin: A System Analytical Approach - Simulation and Analysis of Three Flood Management Strategies, IIASA Report IR-03-003.; Ekenberg, L., Brouwers, L., Danielson, M., Hansson, K., Johansson, J., Riabacke, A., Vári, A., 2003. Flood Risk Management Policy in the Upper Tisza Basin: A System Analytical Approach - Simulation and Analysis of Three Flood Management Strategies, IIASA Report IR-03-003.
[19] Fernandes, L.; Fischer, A.; Júdice, J. J.; Requejo, C.; Soares, J., A block active set algorithm for large-scale quadratic programming with box constraints, Annals of Operations research, 81, 75-95 (1998) · Zbl 0906.90138
[20] Fischhoff, B.; Goitein, B.; Shapira, Z., Subjective expected utility: A model of decision making, (Scholz, R. W., Decision Making under Uncertainty (1983), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. North-Holland), 183-207
[21] Fletcher, R., Practical Methods of Optimization (1987), John Wiley · Zbl 0905.65002
[22] Fletcher, R., Stable reduced Hessian updates for indefinite quadratic programming, Mathematical Programming, 87, 2, 251-264 (2000) · Zbl 0964.65065
[23] Galligani, E.; Ruggiero, V.; Zanni, L., Splitting methods for quadratic optimization in data analysis, International Journal of Computer Mathematics, 63, 289-307 (1997) · Zbl 0893.90140
[24] Galligani, E.; Ruggiero, V.; Zanni, L., Parallel solution of large-scale quadratic programs, (Leone, R. D.; Murli, A.; Pardalos, P. M.; Toraldo, G., High Performance Algorithms and Software in Non-linear Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers The Netherlands), 189-205 · Zbl 0942.65062
[25] Hodges, J. L.; Lehmann, E. L., The use of previous experience in reaching statistical decisions, The Annals of Mathematical Statistics, 23, 396-407 (1952) · Zbl 0047.38306
[26] Hurwicz, L., 1951. Optimality criteria for decision making under ignorance, Cowles Commission Discussion Paper 370.; Hurwicz, L., 1951. Optimality criteria for decision making under ignorance, Cowles Commission Discussion Paper 370.
[27] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[28] Kyburg, H. E., Probability and the Logic of Rational Belief (1961), Wesleyan University Press: Wesleyan University Press Middletown, Connecticut
[29] Lemke, C. E., On complementary Pivot theory, (Dantzig, G. B.; Veinott, A. F., Mathematics of Decision Sciences, Part 1 (1968), AMS: AMS Providence, Rhode Island), 95-114 · Zbl 0208.45502
[30] Levi, I., On indeterminate probabilities, The Journal of Philosophy, 71, 391-418 (1974)
[31] Levi, I., The Enterprise of Knowledge (1980), MIT Press
[32] Li, W.; Swetits, J., A new algorithm for solving strictly convex quadratic programs, SIAM Journal on Optimization, 7, 3, 595-619 (1997) · Zbl 0891.90133
[33] Madsen, K.; Nielsen, H. B.; Pinar, M. C., A finite continuation algorithm for bound constrained quadratic programming, SIAM Journal on Optimization, 9, 1, 62-83 (1998) · Zbl 0997.90056
[34] Malmnäs, P. E., Towards a mechanization of real life decisions, (Prawitz, D.; Westerståhl, D., Logic and Philosophy of Science in Uppsala (1994), Kluwer Academic Publishers)
[35] Morales, J.L., Waltz, R., Liu, G., Goux, J.P., 2001. Assessing the potential of interior methods for non-linear optimization. Optimization Technology Centre, Report OTC.; Morales, J.L., Waltz, R., Liu, G., Goux, J.P., 2001. Assessing the potential of interior methods for non-linear optimization. Optimization Technology Centre, Report OTC.
[36] Raiffa, H., Decision Analysis (1968), Addison Wesley · Zbl 0181.21802
[37] Shafer, G.; Gillet, P. R.; Scherl, R. B., Subjective probability and lower and upper prevision: A new understanding, (Bernard, J.-M.; Seidenfeld, T.; Zaffalon, M., Proceedings of ISIPTA’03 (2003), Carleton Scientific) · Zbl 1092.68098
[38] Shapira, Z., Risk Taking: A Managerial Perspective (1995), Russel Sage Foundation
[39] Tam, N. N.; Yen, N. D., Continuity properties of the Karush-Kuhn-Tucker point set in quadratic programming problems, Journal of Mathematical Programming, 85, 192-206 (1999) · Zbl 0956.90023
[40] Wald, A., Statistical Reasoning with Imprecise Probabilities (1950), Chapman and Hall: Chapman and Hall London
[41] Walley, P., Statistical Decision Functions (1991), John Wiley and Sons
[42] Wei, Z. L., Subspace search method for quadratic programming with box constraints, Journal of Computational Mathematics, 17, 3, 307-314 (1999) · Zbl 0937.65067
[43] Weichselberger, K.; Pöhlman, S., A Methodology for Uncertainty in Knowledge-Based Systems (1990), Springer-Verlag
[44] Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 382-398 (1959) · Zbl 0103.37603
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.