Back to Search
Start Over
Multi-language evaluation of exact solvers in graphical model discrete optimization
Multi-language evaluation of exact solvers in graphical model discrete optimization
- Source :
- Constraints, Constraints, Springer Verlag, 2016, 21 (3), pp.413-434. ⟨10.1007/s10601-016-9245-y⟩
- Publication Year :
- 2016
- Publisher :
- HAL CCSD, 2016.
-
Abstract
- International audience; 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).
- Subjects :
- 0301 basic medicine
MaxSAT
Mathematical optimization
Optimization problem
Linear programming
02 engineering and technology
03 medical and health sciences
Artificial Intelligence
Discrete optimization
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
[INFO]Computer Science [cs]
Graphical model
[MATH]Mathematics [math]
Integer programming
Mathematics
Markov random field
Solver
030104 developmental biology
Integer linear programming
Computational Theory and Mathematics
Benchmark (computing)
Probability distribution
020201 artificial intelligence & image processing
Weighted constraint satisfaction problem
Software
Subjects
Details
- Language :
- English
- ISSN :
- 13837133 and 15729354
- Database :
- OpenAIRE
- Journal :
- Constraints, Constraints, Springer Verlag, 2016, 21 (3), pp.413-434. ⟨10.1007/s10601-016-9245-y⟩
- Accession number :
- edsair.doi.dedup.....b853d16627a0d1c2c0590acf2c4e3f17
- Full Text :
- https://doi.org/10.1007/s10601-016-9245-y⟩