Abstract

Abstract: 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).

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.