You are here

Home

Message Passing and Combinatorial Optimization

Siamak (Mohsen)
Ravanbakhsh
Doctoral dissertation
2015
University of Alberta
Keywords: 
probabilistic graphical models, message passing, combinatorial optimization, belief propagation, satisfiability, clustering, traveling salesman problem
Summary:

Summary of Message Passing and Combinatorial Optimization

Graphical Models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying only local factors. This thesis studies inference in such models from a broad algebraic view and the ways it can be used to express and approximately solve NP-hard combinatorial problems.

The first part of this thesis categorizes these inference problems under a “hierarchy” with increasing levels of complexity. A subset of the problems can be approximately solved using a well-known message passing procedure called Belief Propagation (BP). In this procedure, messages are exchanged between the nodes in the graphical model until reaching convergence. The message update can be seen as a fixed point iteration that finds exact solutions for trees and approximations for graphical models with loops. We study several novel approaches to further improve the approximation obtained by BP in loopy graphs and propose variations on a generalization of BP, called survey propagation.

The second part reviews the existing message passing solutions and provides novel graphical model formulation and inference techniques for more than twenty important combinatorial optimization problems. These are studied under three broad classes: (I) “constraint satisfaction problems” such as satisfiability, coloring, packing; (II) “clustering problems” such as hierarchical clustering, K-median, K-clustering, K-center problem; and (III) “problems over permutations” including assignment problem, graph alignment, isomorphism, graph alignment, finding symmetries and traveling salesman problem. In many cases we show that our message passing procedures are able to find solutions that compare favourably to today’s state-of-the-art approaches, and are often near optimal.

Follow us on social media
twitter  twitter  LinkedIN

 


 

2013 AI Doctoral and MSC thesis awards

 

33rd Canadian Conference on Artificial Intelligence

12-15 May 2020, Online

 


 

The Caiac Herald

Nov. 2019 edition now available!

Member login