## 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.

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 language | English |
---|---|

Title of host publication | Proceedings of Machine Learning Research |

Subtitle of host publication | PGM 2018 |

Pages | 85-96 |

Number of pages | 12 |

Volume | 72 |

Publication status | Published - 2018 |

Event | The 9th International Conference on Probabilistic Graphical Models - Prague, Czech Republic Duration: 11 Sep 2018 → 14 Sep 2018 http://pgm2018.utia.cz/ |

### Conference

Conference | The 9th International Conference on Probabilistic Graphical Models |
---|---|

Abbreviated title | PGM'18 |

Country/Territory | Czech Republic |

City | Prague |

Period | 11/09/18 → 14/09/18 |

Internet address |