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

• URL: http://arxiv.org/abs/2410.23934v1
• Date: Thu, 31 Oct 2024 13:48:46 GMT
• Title: Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models
• Authors: Anne-Marie George, Nic Wilson, Barry O'Sullivan,
• Abstract summary: We construct and compare algorithmic approaches to solve the Consistency Problem for preference statements based on hierarchical models. An instance is consistent if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives. We develop three approaches to solve this decision problem.
• Score: 4.007697401483925
• License:
• Abstract: 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.

Related papers

• Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation [5.924780594614676]
  This paper presents a novel framework for inferring timed temporal logic properties from data. We formulate the inference process as a mixed integer linear programming optimization problem. Applying a max-flow algorithm on the resultant tree transforms the problem into a global optimization challenge. We conduct three case studies involving two-class, multi-class, and complex formula classification scenarios.
  arXiv  Detail & Related papers  (2024-07-30T16:56:21Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  We propose an interactive genetic algorithm for solving multi-objective optimization problems under preference imprecision. Our algorithm, called RIGA, can be applied to any multi-objective optimization problem provided that the aggregation function is linear in its parameters. For several performance indicators (computation times, gap to optimality and number of queries), RIGA obtains better results than state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-11-10T13:56:15Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  We explore the use of Doubly Matrices (DSM) for matching and assignment nature permutation problems. Specifically, we adopt the framework of estimation of distribution algorithms and compare DSMs to some existing proposals for permutation problems. Preliminary experiments on instances of the quadratic assignment problem validate this line of research and show that DSMs may obtain very competitive results.
  arXiv  Detail & Related papers  (2023-04-05T14:36:48Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  We propose a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on optimized on a hybrid ranking and regression loss function.
  arXiv  Detail & Related papers  (2022-10-31T14:06:11Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  This is a sample problem in which we search for the optimal stratification from the set of all possible stratifications of basic strata. evaluating the cost of each solution is expensive. We compare the above multi-stage combination of algorithms with three recent algorithms and report the solution costs, evaluation times and training times.
  arXiv  Detail & Related papers  (2021-08-18T08:41:58Z)
• Learning Structure in Nested Logit Models [22.269565708490468]
  We introduce a new data-driven methodology for nested logit structure discovery. We demonstrate the ability of our algorithm to correctly recover the true nesting structure from synthetic data. We provide our implementation as a customizable and open-source code base written in the Julia programming language.
  arXiv  Detail & Related papers  (2020-08-18T17:15:43Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.