Markov Random Field MAP as Set Partitioning: The 9th International Conference on Probabilistic Graphical Models

Research output: Other contribution


The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint ofinteger programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). Thisallows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally stronglinear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRFMAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findableusing a zero-half cut generator. Experimental results using CPLEX show that for MRF MAPproblems, generating more zero-half cuts than normal typically brings performance improvements.Pre-processing methods to reduce the size of MRF MAP problems are also considered, and somepreliminary results on their usefulness presented.
Original languageEnglish
Number of pages12
Publication statusPublished - 2018

Cite this