提出三种快速求解偏好一致性问题的算法，递归方法显著优于传统优化模型。
Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models
- 基于层级模型特性设计递归剪枝算法，缩小搜索空间。
- 实验表明递归算法速度远超MILP，时间比随数据增长急剧扩大。
- 适合需要高效处理大规模偏好判断的应用场景。
本文针对基于层级模型的偏好一致性问题，构建并比较了多种算法求解方案。该问题包含一组直接比较（严格与非严格）不同备选方案的偏好陈述，以及一组可用于对所有备选方案评分的评估函数。当存在一个层级模型，能通过评估函数诱导出备选方案的顺序关系，并满足所有给定偏好关系时，该实例即为一致的。已知此判定问题在层级模型下为NP完全。本文提出三种求解方法：第一种是混合整数线性规划（MILP）形式化；后两种为基于问题特性的递归算法，可有效剪枝搜索空间。在合成数据上的实验表明，递归算法的速度明显优于求解MILP，且运行时间比随规模增加而急剧上升。
原文摘要 · Abstract (English)
In this paper, we construct and compare algorithmic approaches to solve the Preference Consistency Problem for preference statements based on hierarchical models. Instances of this problem contain a set of preference statements that are direct comparisons (strict and non-strict) between some alternatives, and a set of evaluation functions by which all alternatives can be rated. An instance is consistent based on hierarchical preference models, if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives by which all relations given by the preference statements are satisfied. Deciding if an instance is consistent is known to be NP-complete for hierarchical models. We develop three approaches to solve this decision problem. The first involves a Mixed Integer Linear Programming (MILP) formulation, the other two are recursive algorithms that are based on properties of the problem by which the search space can be pruned. Our experiments on synthetic data show that the recursive algorithms are faster than solving the MILP formulation and that the ratio between the running times increases extremely quickly.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。