Guaranteed Diversity & Quality for the Weighted CSP - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2019

Guaranteed Diversity & Quality for the Weighted CSP


In many applications of constraint programming, it is often impossible to capture all the relevant information in one numerical criterion. In this case, it is useful to produce a set of high quality yet diverse solutions. In this paper, motivated by a Computational Protein Design application, we consider the general problem of producing a diverse set of high-quality solutions of a given Weighted Constraint Satisfaction Problem, with guarantees both on solution quality and diversity. We use weighted automata decomposed in functions of bounded arity, incremental CFN solving, a simple form of predictive bounding and compressed representations of distance constraints for improved efficiency. We show that this approach can be successfully applied to a variety of problems that include both Protein Design Problems but also large Bayesian networks represented as Cost Function Networks. We also show that our approach has the capacity to enumerate so-called local delta-modes and that it does provide improved protein designs.
No file

Dates and versions

hal-03181764 , version 1 (25-03-2021)



Manon Ruffini, Jelena Vucinic, Simon de Givry, George Katsirelos, Sophie Barbe, et al.. Guaranteed Diversity & Quality for the Weighted CSP. 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2019, Portland, United States. pp.18-25, ⟨10.1109/ICTAI.2019.00012⟩. ⟨hal-03181764⟩
148 View
0 Download



Gmail Facebook X LinkedIn More