Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models

Anne-Marie George, Nic Wilson, Barry O'SullivanIJCAI 2016

Abstract

Determining whether a set of user preferences is consistent with a hierarchical model is a fundamental task in recommender systems and multi-objective optimization. This problem, known as the Preference Consistency Problem (PCP), is NP-complete for Hierarchical Constraint Linear Programming (HCLP) models. This paper presents a novel recursive algorithm, PC-check, that leverages the mathematical properties of lexicographic hierarchies to achieve massive speedups over standard Mixed Integer Linear Programming (MILP) solvers. By exploiting a "singleton shortcut," the algorithm prunes the search space effectively, transforming a theoretically hard problem into one that is computationally feasible for real-time applications.

Introduction

In modern decision support systems, inferring a user's complete preference profile from a limited set of statements is critical to avoid user fatigue. This process, the Preference Deduction Problem (PDP), relies on first solving the Preference Consistency Problem (PCP): verifying if the provided statements are consistent with an underlying mathematical model. We focus on Hierarchical Constraint Linear Programming (HCLP), where alternatives are evaluated through a prioritized hierarchy of criteria. Despite its utility, the combinatorial nature of HCLP makes consistency checking a significant computational bottleneck.

Methodology

We evaluate three primary approaches to solving the PCP:

  1. MILP Baseline: A standard formulation using Boolean variables to assign evaluation functions to hierarchy levels, solved via general-purpose solvers like CPLEX.
  2. Recursive PC-check: Our primary contribution, which constructs the hierarchy level-by-level. A key theoretical insight—the "Singleton Shortcut"—proves that if a consistent model exists, one can be found by greedily adding as many single-attribute levels as possible. This drastically reduces the need for backtracking.
  3. Conflicting Sets Extension: An optimization that tracks failed combinations of evaluation functions to prevent redundant search paths.

Experimental Evaluation

Due to the lack of real-world HCLP datasets, we utilized synthetic data to stress-test the algorithms. We generated 50 instances for various problem sizes, varying the number of evaluation functions ($n$) from 10 to 30 and the number of preference statements ($g$) from 10 to 50.

Distribution of consistency types as a function of the number of preference statements.

As shown in Figure 1, the nature of the problem shifts as the number of statements increases. With fewer statements, instances are more likely to be consistent. As $g$ grows, the likelihood of inconsistency increases, which typically represents the most computationally demanding scenario for search algorithms as they must exhaust the entire search space to prove no model exists.

Results and Discussion

The performance disparity between the recursive PC-check and the MILP baseline is stark. In a test case with $n=20$ and $g=15$, the MILP solver required nearly 12 hours (41,472 seconds) to reach a solution. In contrast, the PC-check algorithm completed the same task in just 0.29 seconds.

Running time performance across varying numbers of evaluation functions ($n$) and statements ($g$).

Figure 2 illustrates the scaling behavior of the algorithm. While running times increase exponentially with the number of evaluation functions, the absolute times remain within a range suitable for practical use. Interestingly, the "Conflicting Sets" optimization provided marginal benefits, as the overhead of maintaining the set list often outweighed the pruning gains, suggesting that the basic recursive search is already highly optimized for this problem structure.

Conclusion

By exploiting the lexicographic structure of hierarchical preferences, we have developed algorithms that outperform general-purpose MILP solvers by several orders of magnitude. The "singleton shortcut" is a pivotal mathematical insight that enables efficient pruning. Future work will explore hybrid approaches combining recursive search with MILP relaxations and testing these algorithms on real-world preference data.

Summary updated

BibTeX
@inproceedings{george2016towards,
  author = {Anne-Marie George and Nic Wilson and Barry O'Sullivan},
  title = {{Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure