Conditions beyond treewidth for tightness of higher-order LP relaxations

Mark Rowland, Aldo Pacchiano, Adrian Weller
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:10-18, 2017.

Abstract

Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integral vertex then the solution is guaranteed to be exact and we say that the relaxation is tight. We consider binary pairwise models and introduce new methods which allow us to demonstrate refined conditions for tightness of LP relaxations in the Sherali-Adams hierarchy. Our results include showing that for higher order LP relaxations, treewidth is not precisely the right way to characterize tightness. This work is primarily theoretical, with insights that can improve efficiency in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-rowland17a, title = {{Conditions beyond treewidth for tightness of higher-order LP relaxations}}, author = {Rowland, Mark and Pacchiano, Aldo and Weller, Adrian}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {10--18}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/rowland17a/rowland17a.pdf}, url = {https://proceedings.mlr.press/v54/rowland17a.html}, abstract = {Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integral vertex then the solution is guaranteed to be exact and we say that the relaxation is tight. We consider binary pairwise models and introduce new methods which allow us to demonstrate refined conditions for tightness of LP relaxations in the Sherali-Adams hierarchy. Our results include showing that for higher order LP relaxations, treewidth is not precisely the right way to characterize tightness. This work is primarily theoretical, with insights that can improve efficiency in practice.} }
Endnote
%0 Conference Paper %T Conditions beyond treewidth for tightness of higher-order LP relaxations %A Mark Rowland %A Aldo Pacchiano %A Adrian Weller %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-rowland17a %I PMLR %P 10--18 %U https://proceedings.mlr.press/v54/rowland17a.html %V 54 %X Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integral vertex then the solution is guaranteed to be exact and we say that the relaxation is tight. We consider binary pairwise models and introduce new methods which allow us to demonstrate refined conditions for tightness of LP relaxations in the Sherali-Adams hierarchy. Our results include showing that for higher order LP relaxations, treewidth is not precisely the right way to characterize tightness. This work is primarily theoretical, with insights that can improve efficiency in practice.
APA
Rowland, M., Pacchiano, A. & Weller, A.. (2017). Conditions beyond treewidth for tightness of higher-order LP relaxations. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:10-18 Available from https://proceedings.mlr.press/v54/rowland17a.html.

Related Material