Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

An experimental evaluation of CP/AI/OR solvers for optimization in graphical models

Abstract : Graphical models on discrete variables allows to model NP-hard optimization problems where the objective function is factorized into a set of local functions. In the graphical interpretation, each function's scope is represented by a clique. Deterministic graphical models such as Cost Function Network (CFN) aim at minimizing the sum of all functions (or constraints if zero/infinite costs are used). Probabilistic graphical models such as Markov Random Field (MRF) aim at maximizing the product of all functions (or constraints if using zero/one probabilities). A direct (-log) transformation exists between the two frameworks that can also be modeled as weighted MaxSAT or ILP. Strong connections exist between LP itself and bounds used in graphical models. We report a large comparison of state-of-the-art CP/AI/OR exact solvers on several deterministic and probabilistic graphical models coming from the Probabilistic Inference Challenge 2011, the Weighted Partial Max-SAT Evaluation 2013, the MiniZinc Challenge 2012 and 2013, and a library of Cost Function Networks. These competitions are usually restricted to a family of dedicated solvers. We instead compare the efficiency of eight state-of-the-art exact solvers of each optimization language on these encodings. It includes MRF solvers daoopt ( version 1.1.2), mplp2 ( version 2), toulbar2 ( version 0.9.6), MaxSAT solver maxhs (, ILP solver cplex (version 12.2), and CP solvers numberjack-mistral ( version 1.3.40), gecode ( version 4.2.0), opturion-cpx ( version 1.0.2). All the 1062 instances are made publicly available in five different formats (uai, wcsp, wcnf, lp, mzn) and seven formulations at The results suggest the opportunity for a simple portfolio approach and we give preliminary results based on the numberjack platform.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 05:01:05
Dernière modification le : mercredi 14 octobre 2020 - 04:13:05


  • HAL Id : hal-02742905, version 1
  • PRODINRA : 266023



Simon de Givry, Barry Hurley, David Allouche, Georgios Katsirelos, Barry O'Sullivan, et al.. An experimental evaluation of CP/AI/OR solvers for optimization in graphical models. Congrès ROADEF'2014, Feb 2014, Bordeaux, France. 1 p. ⟨hal-02742905⟩



Consultations de la notice