Skip to Main content Skip to Navigation
Conference papers

Guaranteed Diversity & Quality for the Weighted CSP

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inrae.fr/hal-03181764
Contributor : Papa Abdoulaye Sow <>
Submitted on : Thursday, March 25, 2021 - 8:02:59 PM
Last modification on : Tuesday, June 15, 2021 - 2:57:34 PM

Identifiers

Citation

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⟩

Share

Metrics

Record views

78