Markov Random Field MAP as Set Partitioning

James Cussens

Markov Random Field MAP as Set Partitioning

James Cussens

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

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 find-
able 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 the 9th International Conference on Probabilistic Graphical Models (PGM 18)
Subtitle of host publication	PMLR 72
Pages	85-96
Publication status	Published - 11 Sept 2018

Access to Document

http://proceedings.mlr.press/v72/cussens18a/cussens18a.pdf

Handle.net

Persistent link

Cite this

@inproceedings{6ca178b60f3f4dd4a8f94a968b46d323,

title = "Markov Random Field MAP as Set Partitioning",

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 find- able 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.",

author = "James Cussens",

year = "2018",

month = sep,

day = "11",

language = "English",

pages = "85--96",

booktitle = "Proceedings of the 9th International Conference on Probabilistic Graphical Models (PGM 18)",

}

TY - GEN

T1 - Markov Random Field MAP as Set Partitioning

AU - Cussens, James

PY - 2018/9/11

Y1 - 2018/9/11

N2 - 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 find- able 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.

AB - 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 find- able 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.

M3 - Conference Contribution (Conference Proceeding)

SP - 85

EP - 96

BT - Proceedings of the 9th International Conference on Probabilistic Graphical Models (PGM 18)

ER -

Markov Random Field MAP as Set Partitioning

Abstract

Access to Document

Handle.net

Fingerprint

Cite this