Skip to Main content Skip to Navigation
Journal articles

Multi-language evaluation of exact solvers in graphical model discrete optimization

Abstract : By representing the constraints and objective function in factorized form, graphical models can concisely define various NP-hard optimization problems. They are therefore extensively used in several areas of computer science and artificial intelligence. Graphical models can be deterministic or stochastic, optimize a sum or product of local functions, defining a joint cost or probability distribution. Simple transformations exist between these two types of models, but also with MaxSAT or linear programming. In this paper, we report on a large comparison of exact solvers which are all state-of-the-art for their own target language. These solvers are all evaluated on deterministic and probabilistic graphical models coming from the Probabilistic Inference Challenge 2011, the Computer Vision and Pattern Recognition OpenGM2 benchmark, the Weighted Partial MaxSAT Evaluation 2013, the MaxCSP 2008 Competition, the MiniZinc Challenge 2012 & 2013, and the CFLib (a library of Cost Function Networks). All 3026 instances are made publicly available in five different formats and seven formulations. To our knowledge, this is the first evaluation that encompasses such a large set of related NP-complete optimization frameworks, despite their tight connections. The results show that a small number of evaluated solvers are able to perform well on multiple areas. By exploiting the variability and complementarity of solver performances, we show that a simple portfolio approach can be very effective. This portfolio won the last UAI Evaluation 2014 (MAP task).
Document type :
Journal articles
Complete list of metadata
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Wednesday, May 27, 2020 - 11:57:41 AM
Last modification on : Friday, September 23, 2022 - 4:48:13 PM




Barry Hurley, Barry O'Sullivan, David Allouche, George Katsirelos, Thomas Schiex, et al.. Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints, Springer Verlag, 2016, 21 (3), pp.413-434. ⟨10.1007/s10601-016-9245-y⟩. ⟨hal-02633083⟩



Record views