Abstract
This paper addresses the challenge of solving Incomplete Weighted Constraint Satisfaction Problems (IWCSPs), where some cost preferences are initially unknown and must be elicited from users. We propose two parameterized heuristics, Smallest Cost Elicitation (SCE) and Matrix-Based Elicitation (MBE), which allow for boundedly-suboptimal solutions. By introducing relative and additive error bounds, these heuristics significantly reduce both computational runtime and the number of user elicitations required, providing a controllable trade-off between solution quality and efficiency.
Introduction
In a standard Weighted Constraint Satisfaction Problem (WCSP), the goal is to find an assignment of values to variables that minimizes a total cost function. While traditional models assume all costs are known a priori, real-world applications—such as personalized scheduling or automated negotiation—often involve preferences that are initially hidden. These are modeled as Incomplete WCSPs (IWCSPs), where an algorithm must "elicit" missing costs during the search process.
Previous approaches to IWCSPs typically fell into two extremes: exhaustive search for the absolute optimum (which is computationally expensive and burdensome for the user) or heuristic methods with no quality guarantees. This work bridges that gap by providing "boundedly-suboptimal" solutions, allowing users to define acceptable error margins in exchange for faster results.
Problem Formulation
An IWCSP is defined by a set of variables, their domains, and a set of weighted constraints. Unlike standard WCSPs, some entries in the cost tables are unknown. To solve these, the search algorithm must decide when to ask the user for a missing value.
Proposed Methods
We extend the standard Depth-First Branch-and-Bound (DFBnB) search algorithm with two novel heuristics designed to prune the search space effectively while minimizing user interaction:
- Smallest Cost Elicitation (SCE) Heuristic: This heuristic estimates the minimum possible cost to complete a partial solution by multiplying the number of remaining unknown costs by the smallest possible cost value in the system. It incorporates two user-defined parameters: a relative error bound ($w$) and an additive error bound ($\epsilon$). If a path's estimated cost exceeds the current best solution (adjusted by these bounds), the algorithm prunes that branch.
- Matrix-Based Elicitation (MBE) Heuristic: A more sophisticated approach that maintains a "frequency matrix" to track the distribution of potential costs. This allows the algorithm to prune entire branches if it can be proven that no solution within that branch can outperform the current best, given the known cost bounds.
Experimental Evaluation
The heuristics were evaluated using randomly generated binary constraint graphs with 5 to 10 variables, a domain size of 4, and 20% initial cost incompleteness. Costs were sampled from the range [2, 100].
Key Results
- Efficiency Gains: The SCE heuristic consistently outperformed MBE in runtime. For 10-variable problems, SCE completed in approximately 4,500 seconds, whereas MBE required over 23,000 seconds due to the overhead of matrix maintenance.
- Reduced User Burden: Both heuristics successfully found high-quality solutions while eliciting only a fraction of the unknown costs (e.g., asking for ~43 out of 54 unknown values).
- Quality vs. Speed Trade-off: A clear "elbow curve" was observed in the relationship between error bounds and performance. As the additive error bound ($\epsilon$) increases, the runtime drops precipitously, allowing users to obtain near-optimal solutions almost instantly.
Conclusion
The primary insight of this research is that perfect optimization is often unnecessary in preference-based systems. By accepting a small, controlled amount of suboptimality, algorithms can significantly reduce both computational time and the "user burden" of elicitation. While SCE proved more efficient in these tests, future work will focus on scaling these methods to larger variable sets and exploring alternative elicitation styles, such as comparative ranking.
Summary updated