Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization

Abdelkader Ouali, David Allouche, Simon de Givry, Samir Loudni, Yahia Lebbah, Francisco Eckhardt, Lakhdar Loukil
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:481-490, 2017.

Abstract

Graphical models factorize a global probabil- ity distribution/energy function as the prod- uct/sum of local functions. A major infer- ence task, known as MAP in Markov Ran- dom Fields and MPE in Bayesian Networks, is to find a global assignment of all the vari- ables with maximum a posteriori probabil- ity/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighbor- hood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search in- side its local neighborhood exploration. The resulting hybrid method offers a good compro- mise between completeness and anytime be- havior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on dif- ficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver at www.inra.fr/mia/T/toulbar2 v1.0.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-ouali17a, title = {Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization}, author = {Ouali, Abdelkader and Allouche, David and de Givry, Simon and Loudni, Samir and Lebbah, Yahia and Eckhardt, Francisco and Loukil, Lakhdar}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {481--490}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/ouali17a/ouali17a.pdf}, url = {https://proceedings.mlr.press/r15/ouali17a.html}, abstract = {Graphical models factorize a global probabil- ity distribution/energy function as the prod- uct/sum of local functions. A major infer- ence task, known as MAP in Markov Ran- dom Fields and MPE in Bayesian Networks, is to find a global assignment of all the vari- ables with maximum a posteriori probabil- ity/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighbor- hood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search in- side its local neighborhood exploration. The resulting hybrid method offers a good compro- mise between completeness and anytime be- havior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on dif- ficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver at www.inra.fr/mia/T/toulbar2 v1.0.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization %A Abdelkader Ouali %A David Allouche %A Simon de Givry %A Samir Loudni %A Yahia Lebbah %A Francisco Eckhardt %A Lakhdar Loukil %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-ouali17a %I PMLR %P 481--490 %U https://proceedings.mlr.press/r15/ouali17a.html %V R15 %X Graphical models factorize a global probabil- ity distribution/energy function as the prod- uct/sum of local functions. A major infer- ence task, known as MAP in Markov Ran- dom Fields and MPE in Bayesian Networks, is to find a global assignment of all the vari- ables with maximum a posteriori probabil- ity/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighbor- hood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search in- side its local neighborhood exploration. The resulting hybrid method offers a good compro- mise between completeness and anytime be- havior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on dif- ficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver at www.inra.fr/mia/T/toulbar2 v1.0. %Z Reissued by PMLR on 04 October 2026.
APA
Ouali, A., Allouche, D., de Givry, S., Loudni, S., Lebbah, Y., Eckhardt, F. & Loukil, L.. (2017). Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:481-490 Available from https://proceedings.mlr.press/r15/ouali17a.html. Reissued by PMLR on 04 October 2026.

Related Material