Parameterized Heuristics for Incomplete Weighted CSPs

Abstract

The key assumption in Weighted Constraint Satisfaction Problems (WCSPs) is that all constraints are specified a priori. This assumption does not hold in some applications that involve users preferences. Incomplete WCSPs (IWCSPs) extend WCSPs by allowing some constraints to be partially specified. Unfortunately, existing IWCSP approaches either guarantee to return optimal solutions or not provide any quality guarantees on solutions found. To bridge the two extremes, we propose a number of parameterized heuristics that allow users to find boundedly-suboptimal solutions, where the error bound depends on user-defined parameters. These heuristics thus allow users to trade off solution quality for fewer elicited preferences and faster computation times.