Finding diverse and similar solutions in constraint programming
Emmanuel Hébrard, Brahim Hnich, Barry O’Sullivan, Toby Walsh · 2005
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 simi-larity 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 so-lution methods, some of which use global constraints for en-forcing diversity (or similarity) between solutions. Empirical evaluation on a number of problems show promising results.