Brandon Malone (at 10:15): MaxSAT-based Cutting Planes for Learning Graphical Models

Abstract: A way of implementing domain-specific cutting planes in branch-and-cut based Mixed-Integer Programming (MIP) solvers is through solving so-called sub-IPs, solutions of which correspond to the actual cuts. We consider the suitability of using Maximum satisfiability solvers instead of MIP for solving sub-IPs. As a case study, we focus on the problem of learning optimal graphical models, namely, Bayesian and chordal Markov network structures.

About the presenter: Brandon Malone is a postdoctoral researcher at the Max Planck Institute for Biology of Ageing. Much of his research has addressed improving the scalability of exact Bayesian network structure learning using admissible heuristic search. He has also worked with interdisciplinary groups to investigate biological problems, such as processes related to ageing, using probabilistic models. He received his PhD from Mississippi State University in 2012.

James Cussens (roughly at 10:45): Integer programming for the MAP problem in Markov random fields

Abstract: It is well-known that the NP-hard problem of finding the most probable joint instantiation of variables in a Markov random field (MRF MAP) can be encoded as an integer program. By exploiting the structure of MRF MAP we can get better performance when solving MRF MAP using an IP solver such as CPLEX. In this talk I will show that MRF MAP is a special case of the "set partitioning problem (SPP)" and consider which known facts about SPP can help us with MRF MAP. In addition, I will examine how adding 'redundant' constraints expressing conditional independence relations in the MRF affect solver performance. Experimental results using CPLEX will be presented.

About the presenter: James Cussens gained his PhD in Philosophy (of probability) from King's College, London in 1991. He has been a lecturer at the University of York since 1997. He works on machine learning, probabilistic graphical models and the application of mathematical programming to those two areas.