Shortest path based decision making using probabilistic inference

• Main Author: Akshat KUMAR
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Artificial intelligence; Bayesian networks; Budget control; Decision making; Graph theory; Integer programming; Maximum principle; Message passing; Mixtures; Optimization; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/3396; https://ink.library.smu.edu.sg/context/sis_research/article/4397/viewcontent/ShortestPathBasedDecisionMaking.pdf
• Institution: Singapore Management University

We present a new perspective on the classical shortest path routing (SPR) problem in graphs. We show that the SPR problem can be recast to that of probabilistic inference in a mixture of simple Bayesian networks. Maximizing the likelihood in this mixture becomes equivalent to solving the SPR problem. We develop the well known Expectation-Maximization (EM) algorithm for the SPR problem that maximizes the likelihood, and show that it does not get stuck in a locally optimal solution. Using the same probabilistic framework, we then address an NP-Hard network design problem where the goal is to repair a network of roads post some disaster within a fixed budget such that the connectivity between a set of nodes is optimized. We show that our likelihood maximization approach using the EM algorithm scales well for this problem taking the form of message-passing among nodes of the graph, and provides significantly better quality solutions than a standard mixed-integer programming solver.