Conference Proceeding Article
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.
Theory and Algorithms
Intelligent Systems and Decision Analytics
AAAI'16 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence
City or Country
Phoenix, Arizona USA
Shortest Path Based Decision Making Using Probabilistic Inference. (2016). AAAI'16 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. 3849-3856. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3396
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.