Towards fast algorithms for the preference consistency problem based on hierarchical models

Simple item page
dc.contributor.authorGeorge, Anne-Marieen
dc.contributor.authorWilson, Nicen
dc.contributor.authorO'Sullivan, Barryen
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2025-04-23T16:22:29Z
dc.date.available2025-04-23T16:22:29Z
dc.date.issued2024en
dc.description.abstractIn 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.en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGeorge, A.-M., Wilson, N. and O'Sullivan, B. (2024) ‘Towards fast algorithms for the preference consistency problem based on hierarchical models’. arXiv. https://doi.org/10.48550/ARXIV.2410.23934en
dc.identifier.doi10.48550/ARXIV.2410.23934en
dc.identifier.endpage10en
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/17312
dc.language.isoenen
dc.publisherarXiven
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/Research Centres Programme/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://arxiv.org/abs/2410.23934en
dc.rights© 2024, the Authors.en
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectPreference Consistency Problemen
dc.subjectMixed Integer Linear Programmingen
dc.subjectMILP formulationen
dc.subject~Computer Science - Journal Articles~en
dc.titleTowards fast algorithms for the preference consistency problem based on hierarchical modelsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
2410.23934v1.pdf
Size:
184.92 KB
Format:
Adobe Portable Document Format
Description:
Published Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Insight Centre for Data Analytics - Journal Articles
School of Computer Science and Information Technology