Integer Programming on the Junction Tree Polytope for Influence Diagrams

References

• Adelman D, Mersereau AJ (2008) Relaxations of weakly coupled stochastic dynamic programs. Oper. Res. 56(3):712–727.Link, Google Scholar
• Antonucci A, Zaffalon M (2008) Decision-theoretic specification of credal networks: A unified language for uncertain modeling with sets of Bayesian networks. Internat. J. Approximate Reasoning 49(2):345–361.Google Scholar
• Aras R, Dutech A (2010) An investigation into mathematical programming for finite horizon decentralized POMDPs. J. Artificial Intelligence Res. 37(1):329–396.Google Scholar
• Bertsimas D, Mišić VV (2016) Decomposable Markov decision processes: A fluid optimization approach. Oper. Res. 64(6):1537–1555.Link, Google Scholar
• Bertsimas D, Niño-Mora J (2000) Restless bandits, linear programming relaxations, and a primal-dual index heuristic. Oper. Res. 48(1):80–90.Link, Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Google Scholar
• Cano A, Cano JE, Moral S (1994) Convex sets of probabilities propagation by simulated annealing. Globerson A, Silva R, eds. Proc. 5th Internat. Conf. IPMU’94 (AUAI Press, Arlington, VA), 4–8.Google Scholar
• Chandrasekaran V, Srebro N, Harsha P (2008) Complexity of inference in graphical models. Proc. 24th Conf. Uncertainty Artificial Intelligence, 70–78.Google Scholar
• Cohen V, Parmentier A (2019) Two generalizations of Markov blankets. Preprint, submitted March 8, https://arxiv.org/abs/1903.03538.Google Scholar
• de Campos CP, Cozman FG (2007) Inference in credal networks through integer programming. Proc. 5th Internat. Sympos. Imprecise Probab. Theories Appl., 145–154.Google Scholar
• de Campos CP, Ji Q (2012) Strategy selection in influence diagrams using imprecise probabilities. Preprint, submitted June 13, https://arxiv.org/abs/1206.3246.Google Scholar
• De Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• Dechter R (2013) Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms (Morgan & Claypool Publishers, San Rafael, CA).Google Scholar
• d’Epenoux F (1963) A probabilistic production and inventory problem. Management Sci. 10(1):98–108.Link, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Google Scholar
• Eckles JE (1968) Optimum maintenance with incomplete information. Oper. Res. 16(5):1058–1067.Link, Google Scholar
• Hawkins JT (2003) A Lagrangian decomposition approach to weakly coupled dynamic optimization problems and its applications. Unpublished doctoral dissertation, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Howard RA, Matheson JE (1984) Influence diagrams. Howard RA, Matheson JE, eds. Readings in the Principles and Practice of Decision Analysis (Strategic Decision Systems, Menlo Park, CA), 719–762.Google Scholar
• Howard RA, Matheson JE (2005) Influence diagrams. Decision Anal. 2(3):127–143.Link, Google Scholar
• Hurley B, O’Sullivan B, Allouche D, Katsirelos G, Schiex T, Zytnicki M, De Givry S (2016) Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3):413–434.Google Scholar
• Jensen F, Jensen FV, Dittmer SL (1994) From influence diagrams to junction trees. Proc. 10th Internat. Conf. Uncertainty Artificial Intelligence, 367–373.Google Scholar
• Kask K, Dechter R, Larrosa J, Dechter A (2005) Unifying tree decompositions for reasoning in graphical models. Artificial Intelligence 166(1):165–193.Google Scholar
• Khaled A, Hansen EA, Yuan C (2013) Solving limited-memory influence diagrams using branch-and-bound search. Preprint, submitted September 26, https://arxiv.org/abs/1309.6839.Google Scholar
• Koller D, Friedman N (2009) Probabilistic Graphical Models: Principles and Techniques (MIT Press, Cambridge, MA).Google Scholar
• Koller D, Milch B (2003) Multi-agent influence diagrams for representing and solving games. Games Econom. Behav. 45(1):181–221.Google Scholar
• Lauritzen SL, Nilsson D (2001) Representing and solving decision problems with limited information. Management Sci. 47(9):1235–1251.Link, Google Scholar
• Lee J, Ihler AT, Dechter R (2018) Join graph decomposition bounds for influence diagrams. Globerson A, Silva R, eds. Proc. 34th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 1053–1062.Google Scholar
• Li Y, Yin B, Xi H (2011) Finding optimal memoryless policies of POMDPs under the expected average reward criterion. Eur. J. Oper. Res. 211(3):556–567.Google Scholar
• Littman ML (1994a) Memoryless policies: Theoretical limitations and practical results. Cliff D, Husbands P, Meyer J-A, Wilson SW, eds. Conf. Simulation Adaptive Behav.: From Animals to Animats 3 (MIT Press, Cambridge, MA), 238–245.Google Scholar
• Littman ML (1994b) The witness algorithm: Solving partially observable Markov decision processes. Technical report.Google Scholar
• Liu Q (2014) Reasoning and decisions in probabilistic graphical models–a unified framework. Unpublished doctoral dissertation, University of California, Irvine.Google Scholar
• Maua DD (2016) Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams. Internat. J. Approximate Reasoning 68:211–229.Google Scholar
• Mauá DD, Cozman FG (2016) Fast local search methods for solving limited memory influence diagrams. Internat. J. Approx. Reason. 68:230–245.Google Scholar
• Mauá DD, de Campos C (2011) Solving decision problems with limited information. Adv. Neural Inform. Processing Systems 24:603–611.Google Scholar
• Mauá DD, de Campos CP, Zaffalon M (2012a) The complexity of approximately solving influence diagrams. Globerson A, Silva R, eds. Proc. 28th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 604–613.Google Scholar
• Mauá DD, de Campos CP, Zaffalon M (2012b) Solving limited memory influence diagrams. J. Artificial Intelligence Res. 44:97–140.Google Scholar
• Mauá DD, De Campos CP, Zaffalon M (2013) On the complexity of solving polytree-shaped limited memory influence diagrams with binary variables. Artificial Intelligence 205:30–38.Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I – convex underestimating problems. Math. Programming 10(1):147–175.Google Scholar
• Nilsson D, Höhle M (2001) Computing bounds on expected utilities for optimal policies based on limited information. Technical report, Danish Informatics Network in the Agriculture Sciences.Google Scholar
• Papadimitriou CH, Tsitsiklis JN (1987) The complexity of Markov decision processes. Math. Oper. Res. 12(3):441–450.Link, Google Scholar
• Peters J, Janzing D, Schölkopf B (2017) Elements of Causal Inference: Foundations and Learning Algorithms (MIT Press, Cambridge, MA).Google Scholar
• Poh KL, Horvitz E (1996) A Graph-Theoretic Analysis of Information Value (UAI) (Morgan Kaufman Publishers, San Francisco).Google Scholar
• Powell WB (2014) Clearing the jungle of stochastic optimization. Newman A, Leung J, eds. Bridging Data and Decisions (NFORMS, Catonsville, MD), 109–137.Google Scholar
• Robertson N, Seymour PD (1983) Graph minors. I. Excluding a forest. J. Combin. Theory Ser. B 35(1):39–61.Google Scholar
• Ross S, Pineau J, Paquet S, Chaib-draa B (2008) Online planning algorithms for POMDPs. J. Artificial Intelligence Res. 32(1):663–704.Google Scholar
• Scheffler P (1990) A linear algorithm for the pathwidth of trees. Topics in Combinatorics and Graph Theory (Springer), 613–620.Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Shachter RD (1986) Evaluating influence diagrams. Oper. Res. 34(6):871–882.Link, Google Scholar
• Shani G, Pineau J, Kaplow R (2013) A survey of point-based POMDP solvers. Autonomous Agents Multi-Agent Systems 27(1):1–51.Google Scholar
• Shenoy PP (1992) Valuation-based systems for Bayesian decision analysis. Oper. Res. 40(3):463–484.Link, Google Scholar
• Smallwood RD, Sondik EJ (1973) The optimal control of partially observable Markov processes over a finite horizon. Oper. Res. 21(5):1071–1088.Link, Google Scholar
• Sontag D, Globerson A, Jaakkola T (2011) Introduction to dual decomposition for inference. Optimization for Machine Learning, 219–254.Google Scholar
• Wainwright MJ, Jordan MI (2008) Graphical models, exponential families, and variational inference. Foundations Trends Machine Learn. 1(1–2):1–305.Google Scholar
• Yuan C, Wu X, Hansen E (2010) Solving multistage influence diagrams using branch-and-bound search. Globerson A, Silva R, eds. Proc. 26th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 691–700.Google Scholar