Decision programming for mixed-integer multi-stage optimization under uncertainty. (English) Zbl 1490.91077
Summary: Influence diagrams are widely employed to represent multi-stage decision problems in which each decision is a choice from a discrete set of alternative courses of action, uncertain chance events have discrete outcomes, and prior decisions may influence the probability distributions of uncertain chance events endogenously. In this paper, we develop the Decision Programming framework which extends the applicability of influence diagrams by developing mixed-integer linear programming formulations for such problems. In particular, Decision Programming makes it possible to (i) solve problems in which earlier decisions cannot necessarily be recalled later, for instance, when decisions are taken by agents who cannot communicate with each other; (ii) accommodate a broad range of deterministic and chance constraints, including those based on resource consumption, logical dependencies or risk measures such as Conditional Value-at-Risk; and (iii) determine all non-dominated decision strategies in problems which multiple value objectives. In project portfolio selection problems, Decision Programming allows scenario probabilities to depend endogenously on project decisions and can thus be viewed as a generalization of J. Gustafsson and A. Salo [Oper. Res. 53, No. 6, 946–956 (2005; Zbl 1165.91400)]. We present several illustrative examples, evidence on the computational performance of Decision Programming formulations, and directions for further development.
MSC:
| 91B06 | Decision theory |
| 90B50 | Management decision making, including multiple objectives |
| 90C15 | Stochastic programming |
| 90C11 | Mixed integer programming |
Keywords:
decision analysis; influence diagrams; decision trees; contingent portfolio programming; stochastic programmingCitations:
Zbl 1165.91400References:
| [1] | Antonucci, A.; de Campos, C. P.; Huber, D.; Zaffalon, M., Approximating credal network inferences by linear programming, (van der Gaag, L. C., Symbolic and quantitative approaches to reasoning with uncertainty (2013), Springer: Springer Berlin, Heidelberg), 13-24 · Zbl 1390.68629 |
| [2] | Antonucci, A.; de Campos, C. P.; Huber, D.; Zaffalon, M., Approximate credal network updating by linear programming with applications to decision making, International Journal of Approximate Reasoning, 58, 25-38 (2015) · Zbl 1328.68225 |
| [3] | Antunes, C. H.; Alves, M. J.a.; Clímaco, J.a., Multiobjective linear and integer programming, EURO Advanced Tutorials on Operational Research (2016), Springer · Zbl 1358.90123 |
| [4] | Apap, R. M.; Grossmann, I. E., Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties, Computers & Chemical Engineering, 103, 233-274 (2017) |
| [5] | Artzner, P.; Delbaen, F.; Eber, J.-M.; Heath, D., Coherent measures of risk, Mathematical Finance, 9, 203-228 (1999) · Zbl 0980.91042 |
| [6] | Bertsekas, D., Dynamic programming and optimal control, vol. 2 (2012), Athena Scientific · Zbl 1298.90001 |
| [7] | Bielza, C.; Gómez, M.; Shenoy, P. P., A review of representation issues and modelling challenges with influence diagrams, Omega, 39, 227-241 (2011) |
| [8] | Bielza, C.; Müller, P.; Rios Insua, D., Decision analysis by augmented probability simulation, Management Science, 45, 7, 995-1007 (1999) · Zbl 1231.91061 |
| [9] | Birge, J. R.; Louveaux, F., Introduction to stochastic programming (2011), Springer Science & Business Media · Zbl 1223.90001 |
| [10] | Borgonovo, E.; Tonoli, F., Decision-network polynomials and the sensitivity of decision-support models, European Journal of Operational Research, 239, 2, 490-503 (2014) · Zbl 1339.91031 |
| [11] | https://www.auai.org/uai2008/UAI_camera_ready/decampos.pdf |
| [12] | Colvin, M.; Maravelias, C. T., A stochastic programming approach for clinical trial planning in new drug development, Computers & Chemical Engineering, 32, 11, 2626-2642 (2008) |
| [13] | Colvin, M.; Maravelias, C. T., Scheduling of testing tasks and resource planning in new product development using stochastic programming, Computers & Chemical Engineering, 33, 5, 964-976 (2009) |
| [14] | Colvin, M.; Maravelias, C. T., Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming, European Journal of Operational Research, 203, 1, 205-215 (2010) · Zbl 1176.90204 |
| [15] | Diehl, M.; Haimes, Y., Influence diagrams with multiple objectives and tradeoff analysis, IEEE Transactions on Systems, Man, and Cybernetics-Part A, 34, 3, 293-304 (2004) |
| [16] | Díez, F. J.; Luque, M.; Bermejo, I.n., Decision analysis networks, International Journal of Approximate Reasoning, 96, 1-17 (2018) · Zbl 1451.62064 |
| [17] | Dupačová, J., Optimization under exogenous and endogenous uncertainty, University of West Bohemia in Pilsen (2006) |
| [18] | Dupačová, J.; Gröwe-Kuska, N.; Römisch, W., Scenario reduction in stochastic programming, Mathematical Programming, 95, 3, 493-511 (2003) · Zbl 1023.90043 |
| [19] | Ekin, T.; Polson, N. G.; Soyer, R., Augmented nested sampling for stochastic programs with recourse and endogenous uncertainties, Naval Research Logistics, 64, 613-627 (2017) · Zbl 1411.90236 |
| [20] | Ekin, T.; Walker, S.; Damien, P., Augmented simulation methods for discrete stochastic optimization with recourse, Annals of Operations Research (2020) |
| [21] | Fourer, R., Linear programming, ORMS Today, 44, 3 (2017) |
| [22] | Goel, V.; Grossmann, I. E., A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves, Computers & Chemical Engineering, 28, 8, 1409-1429 (2004) |
| [23] | Goel, V.; Grossmann, I. E., A class of stochastic programs with decision dependent uncertainty, Mathematical Programming, 108, 2-3, 355-394 (2006) · Zbl 1130.90375 |
| [24] | Gupta, V.; Grossmann, I. E., Solution strategies for multistage stochastic programming with endogenous uncertainties, Computers & Chemical Engineering, 35, 11, 2235-2247 (2011) |
| [25] | Gupta, V.; Grossmann, I. E., A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties, Computers & Chemical Engineering, 62, 62-79 (2014) |
| [26] | Gustafsson, J.; Salo, A., Contingent portfolio programming for the management of risky projects, Operations Research, 53, 6, 946-956 (2005) · Zbl 1165.91400 |
| [27] | Hammond, R. K.; Bickel, J. E., Reexamining discrete approximations to continuous distributions, Decision Analysis, 10, 1, 6-25 (2013) · Zbl 1357.62079 |
| [28] | Hellemo, L.; Barton, P. I.; Tomasgard, A., Decision-dependent probabilities in stochastic programs with recourse, Computational Management Science, 15, 3-4, 369-395 (2018) · Zbl 1483.90095 |
| [29] | Holzmann, T.; Smith, J. C., Solving discrete multi-objective optimization problems using modified augmented weighted tchebychev scalarizations, European Journal of Operational Research, 271, 2, 436-449 (2018) · Zbl 1403.90607 |
| [30] | Howard, R. A.; Matheson, J. E., Influence diagrams, (Howard, R. A.; Matheson, J. E., The principles and applications of decision analysis, vol. II (1984), Strategic Decisions Group: Strategic Decisions Group Menlo Park, California), 719-763 |
| [31] | Howard, R. A.; Matheson, J. E., Influence diagrams, Decision Analysis, 2, 3, 127-143 (2005) |
| [32] | Howard, R. A.; Matheson, J. E., Influence diagrams retrospective, Decision Analysis, 2, 3, 144-147 (2006) |
| [33] | Howard, R. A.; Matheson, J. E.; Merkhofer, M. W.L.; Miller, A. C.; North, D. W., Comment on influence diagram retrospective, Decision Analysis, 3, 2, 117-119 (2006) |
| [34] | Hynninen, Y.; Vilkkumaa, E.; Salo, A., Operationalization of utilitarian and egalitarian objectives for optimal allocation of healthcare resources, Decision Sciences (2020) |
| [35] | Jorgensen, E.; Kristensen, A. R.; Nilsson, D., Markov LIMID processes for representing and solving renewal problems, Annals of Operations Research, 219, 63-84 (2014) · Zbl 1301.90096 |
| [36] | Koller, D.; Friedman, N., Probabilistic graphical models: Principles and techniques (2009), The MIT Press: The MIT Press Cambridge, MA · Zbl 1183.68483 |
| [37] | Koller, D.; Milch, B., Multi-agent influence diagrams for representing and solving games, Games and Economic Behavior, 45, 1, 181-221 (2003) · Zbl 1054.91007 |
| [38] | Lauritzen, S. L.; Nilsson, D., Representing and solving decision problems with limited information, Management Science, 47, 9, 1235-1251 (2001) · Zbl 1232.90343 |
| [39] | Li, Y.; Shenoy, P. P., A framework for solving hybrid influence diagrams containing deterministic conditional distributions, Decision Analysis, 9, 1, 55-75 (2012) · Zbl 1398.91187 |
| [40] | Liesiö, J.; Mild, P.; Salo, A., Preference programming for robust portfolio modeling and project selection, European Journal of Operational Research, 181, 3, 1488-1505 (2007) · Zbl 1123.90327 |
| [41] | Liesiö, J.; Mild, P.; Salo, A., Robust portfolio modeling with incomplete cost information and project interdependencies, European Journal of Operational Research, 190, 3, 679-695 (2008) · Zbl 1161.91398 |
| [42] | Liesiö, J.; Salo, A., Scenario-based portfolio selection of investment projects with incomplete probability and utility information, European Journal of Operational Research, 217, 1, 162-172 (2012) · Zbl 1244.91111 |
| [43] | Liesiö, J.; Salo, A.; Keisler, J. M.; Morton, A., Portfolio decision analysis: Recent developments and future prospects, European Journal of Operational Research, 293, 3, 811-825 (2021) · Zbl 1487.91122 |
| [44] | Mancuso, A.; Compare, M.; Salo, A.; Zio, E., Portfolio optimization of safety measures for the prevention of time-dependent accident scenarios, Reliability Engineering & System Safety, 190, 106500 (2019) |
| [45] | Mancuso, A.; Compare, M.; Salo, A.; Zio, E., Optimal prognostics and health management-driven inspection and maintenance strategies for industrial systems, Reliability Engineering & System Safety, 210, 107536 (2021) |
| [46] | Manne, A. S., Linear programming and sequential decisions, Management Science, 6, 3, 259-267 (1960) · Zbl 0995.90599 |
| [47] | Mauá, D. D.; Cozman, F. G., Fast local search methods for solving limited memory influence diagrams, International Journal of Approximate Reasoning, 68, 1235-1251 (2016) |
| [48] | Mauá, D. D.; Cozman, F. G., Thirty years of credal networks: Specification, algorithms and complexity, International Journal of Approximate Reasoning, 126, 133-157 (2020) · Zbl 1490.68229 |
| [49] | McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I convex underestimating problems, Mathematical Programming, 10, 1, 147-175 (1976) · Zbl 0349.90100 |
| [50] | Müller, P.; Berry, D. A.; Grieve, A. P.; Smith, M.; Krams, M., Simulation-based sequential Bayesian design, Journal of Statistical Planning and Inference, 137, 10, 3140-3150 (2007) · Zbl 1114.62076 |
| [51] | Neil, M.; Tailor, M.; Marquez, D., Inference in hybrid Bayesian networks using dynamic discretization, Statistics and Computing, 17, 219-233 (2007) |
| [52] | Olmsted, M., On representing and solving decision problems (PhD dissertation) (1983), Stanford University, Stanford. CA |
| [53] | Parmentier, A.; Cohen, V.; Leclère, V.; Obozinski, G.; Salmon, J., Integer programming on the junction tree polytope for influence diagrams, INFORMS Journal on Optimization, 2, 3, 209-228 (2020) |
| [54] | Pflug, G. C., Optimization of stochastic models: The interface between simulation and optimization, vol. 373 (2012), Springer Science & Business Media |
| [55] | Powell, W. B., A unified framework for stochastic optimization, European Journal of Operational Research, 275, 3, 795-821 (2019) · Zbl 1430.90445 |
| [56] | Rios Insua, D.; Rios, J.; Banks, D., Adversarial risk analysis, Journal of the American Statistical Association, 104, 486, 841-854 (2009) · Zbl 1390.91117 |
| [57] | Rockafellar, R. T.; Uryasev, S., Conditional value-at-Risk for general loss distributions, Journal of Banking & Finance, 26, 1443-1471 (2002) |
| [58] | Roponen, J.; Ríos Insua, D.; Salo, A., Adversarial risk analysis under partial information, European Journal of Operational Research, 287, 1, 306-316 (2020) · Zbl 1443.91117 |
| [59] | Rubinstein, R. Y.; Shapiro, A., Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method (1993), John Wiley & Sons Inc · Zbl 0805.93002 |
| [60] | Salo, A.; Hämäläinen, R. P.; Lahtinen, T. J., Multicriteria methods for group decision processes: an overview, (Kilgour, D. M.; Eden, C., Handbook of Group Decision and Negotiation (2021), Springer International Publishing: Springer International Publishing Cham), 863-891) |
| [61] | Salo, A.; Keisler, J.; Morton, A., Portfolio decision analysis: Methods for improved resource allocation, vol. 162 (2011), Springer International Series in Operations Research & Management Science · Zbl 1222.90004 |
| [62] | Shachter, R. D., Evaluating influence diagrams, Operations Research, 34, 6, 871-882 (1986) |
| [63] | Shachter, R. D., Probabilistic inference and influence diagrams, Operations Research, 36, 4, 589-604 (1988) · Zbl 0651.90043 |
| [64] | Smith, J. E.; Holtzman, S.; Matheson, J. E., Structuring conditional relationships in influence diagrams, Operations Research, 41, 2, 280-297 (1993) |
| [65] | Solak, S.; Clarke, J.-P. B.; Johnson, E. L.; Barnes, E. R., Optimization of R&D project portfolios under endogenous uncertainty, European Journal of Operational Research, 207, 1, 420-433 (2010) · Zbl 1205.91099 |
| [66] | Tatman, J. A.; Shachter, R. D., Dynamic programming and influence diagrams, IEEE Transactions on Systems, Man, and Cybernetics, 30, 2, 365-379 (1990) · Zbl 0715.90094 |
| [67] | Vilkkumaa, E.; Liesiö, J.; Salo, A., Scenario-based portfolio model for building robust and proactive strategies, European Journal of Operational Research, 266, 1, 205-220 (2018) · Zbl 1403.90437 |
| [68] | Yet, B.; Neil, M.; Fenton, N.; Constantinou, A.; Dementiev, E., An improved method for solving hybrid influence diagrams, International Journal of Approximate Reasoning, 95, 93-112 (2018) · Zbl 1451.62016 |
| [69] | Yuan, C.; Wu, X.; Hansen, E. A., Solving multistage influence diagrams using branch-and-bound search, Proceedings of the twenty-sixth conference on uncertainty in artificial intelligence. Proceedings of the twenty-sixth conference on uncertainty in artificial intelligence, UAI-10, 670-691 (2010), AUAI Press: AUAI Press Arlington, VA |
| [70] | Zhang, N. L., A computational theory of decision networks (1994), PhD Thesis, Department of Computer Science, University of British Columbia, Vancouver, Canada · Zbl 0816.90005 |
| [71] | Zhang, N. L.; Qi, R.; Poole, D., A computational theory of decision networks, International Journal of Approximate Reasoning, 11, 83-158 (1994) · Zbl 0816.90005 |
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.
