Finding Diverse and Similar Solutions in Constraint Programming

Emmanuel Hebrard, Brahim Hnich, Barry O'Sullivan, Toby Walsh

It is useful in a wide range of situations to find solutions which are diverse (or similar) to each other. We therefore define a number of different classes of diversity and similarity problems. For example, what is the most diverse set of solutions of a constraint satisfaction problem with a given cardinality? We first determine the computational complexity of these problems. We then propose a number of practical solution methods, some of which use global constraints for enforcing diversity (or similarity) between solutions. Empirical evaluation on a number of problems show promising results.

Subjects: 15.2 Constraint Satisfaction; 9.2 Computational Complexity

Content Area: 6. Constraint Satisfaction and Satisfiability

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.