Generating the Top $K$ Solutions to Weighted CSPs: A Comparison of Different Approaches

The weighted constraint satisfaction problem (WCSP) is a general and very useful combinatorial optimization tool. Despite its importance, the task of generating the top K solutions to it is understudied. One benefit of generating the top K solutions is in creating a framework for “human-in-the-loop AI”. Most real-world problems cannot be modeled accurately/completely up front and, hence, generating the top K solutions gives users a chance to exercise preferences that are not explicitly included in the modeling phase. In this paper, we first discuss the importance of generating the top K solutions to WCSPs in various contexts. We then propose various approaches to do so and empirically compare them. We include approaches based on quadratization, pseudo-Boolean optimization, constraint propagation, and integer linear programming. Together, they cover all major algorithmic ingredients derived from constraint programming (CP), artificial intelligence (AI), and operations research (OR).