Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

2-2016

Abstract

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.

Keywords

Artificial intelligence, Bayesian networks, Budget control, Decision making, Graph theory, Integer programming, Maximum principle, Message passing, Mixtures, Optimization

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 30th AAAI Conference on Artificial Intelligence AAAI 2016, Phoenix, AZ, February 12-17

First Page

3849

Last Page

3856

ISBN

9781577357605

Publisher

AAAI Press

City or Country

Palo Alto, CA

Additional URL

https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12226

Download

Share

COinS