Reliability of Solutions in Linear Ordering Problem: New Probabilistic Insight and Algorithms

08/08/2022
by   Leszek Szczecinski, et al.
0

In this work, our goal is to characterize the reliability of the solutions that can be obtained by the linear ordering problem (LOP) which is used to order M objects from their pairwise comparisons. We adopt a probabilistic perspective, where the results of pairwise comparisons are modeled as Bernoulli variables with a common parameter which we estimate from the observed data. Estimation by brute-force enumeration has a prohibitive complexity of O(M!) we thus reformulate the problem and introduce a concept of Slater's spectrum which generalizes Slater's index, and next, devising an efficient algorithm to find the spectrum, we lower the complexity to O(M^2 2^M) which is manageable for moderate-size LOPs. Furthermore, with a minor modification of the algorithm, we are able to find all solutions of the LOP. Numerical examples on synthetic and real-world data are shown and the Python-implemented algorithms are publicly available.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset