Markov Random Field MAP as Set Partitioning

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Markov Random Field (MRF) MAP inference problem is considered from the viewpoint of
integer programming (IP). The problem is shown to be a (pure) set partitioning problem (SPP). This
allows us to bring existing work on SPP to bear on the MAP problem. Facets (maximally strong
linear inequalities) of the closely related set packing (SP) problem are shown to be useful for MRF
MAP. These facets include odd hole and odd anti-hole inequalities which are shown to be findable
using a zero-half cut generator. Experimental results using CPLEX show that for MRF MAP
problems, 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 some
preliminary results on their usefulness presented.
Original languageEnglish
Title of host publicationProceedings of Machine Learning Research
Subtitle of host publicationPGM 2018
Pages85-96
Number of pages12
Volume72
Publication statusPublished - 2018
EventThe 9th International Conference on Probabilistic Graphical Models - Prague, Czech Republic
Duration: 11 Sept 201814 Sept 2018
http://pgm2018.utia.cz/

Conference

ConferenceThe 9th International Conference on Probabilistic Graphical Models
Abbreviated titlePGM'18
Country/TerritoryCzech Republic
CityPrague
Period11/09/1814/09/18
Internet address

Cite this