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

The linear ordering problem (LOP), which consists in ordering M objects from their pairwise comparisons, is commonly applied in many areas of research. While efforts have been made to devise efficient LOP algorithms, little was done to verify if the obtained solutions are valid and thus if they have a meaningful interpretation. To remedy this problem, we propose to characterize the reliability of the LOP solutions by adopting 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(M22 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