On the linear ordering problem and the rankability of data

Thomas R. Cameron; Sebastian Charmot; Jonad Pulaj

doi:10.3934/fods.2021010

Article Contents

2021, Volume 3, Issue 2: 133-149. Doi: 10.3934/fods.2021010

This issue Previous Article Wave-shape oscillatory model for nonstationary periodic time series analysis Next Article Normalization effects on shallow neural networks and related asymptotic expansions

On the linear ordering problem and the rankability of data

1.
Penn State Behrend, 1 Prischak Building, Erie, PA, 16563, USA
2.
Davidson College, P.O. Box 7129, Davidson, NC, 28035, USA

Received: December 2020

Revised: March 2021

Early access: April 2021

Published: June 2021

Abstract / Introduction Full Text(HTML) Figure(10) Related Papers Cited by

Abstract

In 2019, Anderson et al. proposed the concept of rankability, which refers to a dataset's inherent ability to be meaningfully ranked. In this article, we give an expository review of the linear ordering problem (LOP) and then use it to analyze the rankability of data. Specifically, the degree of linearity is used to quantify what percentage of the data aligns with an optimal ranking. In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight. In fact, under the appropriate objective function, we show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking. Moreover, we develop a binary program to compute the maximal Kendall tau ranking distance between two optimal rankings, which can be used to measure the diversity among optimal rankings without having to enumerate all optima. Finally, we provide several examples from the world of sports and college rankings to illustrate these concepts and demonstrate our results.

Keywords:

Mathematics Subject Classification: 52B12, 90C09, 90C27, 90C35.

Citation:

Full Text(HTML)

Figure 1. Linear Ordering Polytope: $ P^{3}_{ \rm{LO}} $

Download: Full-size image PowerPoint slide

Figure 2. Simple Digraphs on $ 3 $ vertices

Download: Full-size image PowerPoint slide

Figure 3. Optimal Solution(s) on Linear Ordering Polytope

Download: Full-size image PowerPoint slide

Figure 4. College Features from U.S. World News 2013 Rankings

Download: Full-size image PowerPoint slide

Figure 5. The degree of linearity and the hindsight accuracy of NFL rankings

Download: Full-size image PowerPoint slide

Figure 6. Correlation between the degree of linearity and the hindsight accuracy of NFL rankings

Download: Full-size image PowerPoint slide

Figure 7. The absolute difference between the foresight accuracy of two optimal rankings

Download: Full-size image PowerPoint slide

Figure 8. Diversity among NFL playoff teams in two optimal rankings for years 1992 and 1999

Download: Full-size image PowerPoint slide

Figure 9. NFL playoff progression in 1992; the opaque team lost the indicated matchup

Download: Full-size image PowerPoint slide

Figure 10. NFL playoff progression in 1999; the opaque team lost the indicated matchup

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	P. Anderson, T. Chartier and A. Langville, The rankability of data, SIAM J. Math. Data Sci., 1 (2019), 121-143. doi: 10.1137/18M1183595.
[2]	P. E. Anderson, T. P. Chartier, A. N. Langville and K. E. Pedings-Behling, The rankability of weighted data from pairwise comparisons, Foundations of Data Science, 3 (2021), 1-26. doi: 10.3934/fods.2021002.
[3]	C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh and P. H. Vance, Branch-and-price: Column generation for solving huge integer programs, Oper. Res., 46 (1998), 316-329. doi: 10.1287/opre.46.3.316.
[4]	T. R. Cameron, S. Charmot and J. Pulaj, Diameter polytopes of feasible binary programs, preprint, arXiv: 2008.06844.
[5]	T. R. Cameron, A. N. Langville and H. C. Smith, On the graph Laplacian and the rankability of data, Linear Algebra Appl., 588 (2020), 81-100. doi: 10.1016/j.laa.2019.11.026.
[6]	S. Chanas and P. Kobylański, A new heuristic algorithm solving the linear ordering problem, Comput. Optim. Appl., 6 (1996), 191-205. doi: 10.1007/BF00249646.
[7]	T. Chartier and J. Peachey, Reverse engineering college rankings, Math Horiz., 22 (2014), 5-7. doi: 10.4169/mathhorizons.22.2.5.
[8]	S. L. Chau, J. González and D. Sejdinovic, Learning inconsistent preferences with kernal methods, preprint, arXiv: 2006.03847.
[9]	B. H. Chiarni, New Algorithm for the Triangulation of Input-Output Tables and the Linear Ordering Problem, Master's thesis, University of Florida, 2004.
[10]	CPLEX, IBM ILOG CPLEX 12.9 User's Manual, IBM ILOG CPLEX Division, Incline Village, NV, 2019. Available from: https://www.ibm.com.
[11]	G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.
[12]	G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen and L. Eifler, et al., The SCIP Optimization Suite 7.0, ZIB-Report 20-10, Zuse Institute Berlin, 2020. Available from: http://nbn-resolving.de/urn:nbn:de:0297-zib-78023.
[13]	M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979.
[14]	F. Glover, T. Klastorin and D. Klingman, Optimal weighted ancestry relationships, Management Science, 20 (1974), 1190-1193. doi: 10.1287/mnsc.20.8.1190.
[15]	F. Glover, C.-C. Kuo and K. S. Dhir, Heuristic algorithms for the maximum diversity problem, J. Inform. Optim. Sci., 19 (1998), 109-132. doi: 10.1080/02522667.1998.10699366.
[16]	M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem, Oper. Res., 32 (1984), 1195-1220. doi: 10.1287/opre.32.6.1195.
[17]	M. Grötschel, M. Jünger and G. Reinelt, Facets of the linear ordering polytope, Math. Programming, 33 (1985), 43-60. doi: 10.1007/BF01582010.
[18]	M. Grötschel, M. Jünger and G. Reinelt, On the acyclic subgraph polytope, Math. Programming, 33 (1985), 28-42. doi: 10.1007/BF01582009.
[19]	M. Grötschel and M. W. Padberg, Polyhedral theory, in The Traveling Salesman Problem, Wiley-Intersci. Ser. Discrete Math., Wiley-Intersci. Publ., Wiley, Chichester, 1985,251-305.
[20]	Gurobi Optimization, Reference manual, 2020., Available from: http://www.gurobi.com.
[21]	L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR, 244 (1979), 1093-1096.
[22]	M. G. Kendall, A new measure of rank correlation, Biometrika, 30 (1938), 81-93. doi: 10.2307/2332226.
[23]	Y. Kondo, Triangulation of input-output tables based on mixed integer programs for inter-temporal and inter-regional comparison of production structures, J. Econ. Struct., 3 (2014), 1-19. doi: 10.1186/2193-2409-3-2.
[24]	C.-C. Kuo, F. Glover and K. S. Dhir, Analyzing and modeling the maximum diversity problem by zero-one programming, Decision Sci., 24 (1993), 1171-1185. doi: 10.1111/j.1540-5915.1993.tb00509.x.
[25]	A. N. Langville and C. D. Meyer, Who's #1?: The Science of Rating and Ranking, Princeton University Press, Princeton, NJ, 2012. doi: 10.1515/9781400841677.
[26]	J. Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511616655.
[27]	W. Leontiff, Input-Output Economics, Oxford University Press, NY, 1986. doi: 10.1038/scientificamerican1051-15.
[28]	R. Martí and G. Reinelt, The Linear Ordering Problem. Exact and Heuristic Methods in Combinatorial Optimization, Applied Mathematical Sciences, 175, Springer, Heidelberg, 2011. doi: 10.1007/978-3-642-16729-4.
[29]	T. Petit and A. C. Trapp, Enriching solutions to combinatorial problems via solution engineering, INFORMS J. Comput., 31 (2019), 429-444. doi: 10.1287/ijoc.2018.0855.
[30]	G. Reinelt, A note on small linear-ordering polytopes, Discrete Comput. Geom., 10 (1993), 67-78. doi: 10.1007/BF02573963.
[31]	Spreadspoke, NFL scores and betting data, 2020., Available from: https://www.kaggle.com/tobycrabtree/nfl-scores-and-betting-data.
[32]	J.-F. Tsai, M.-H. Lin and Y.-C. Hu, Finding multiple solutions to general integer linear programs, European J. Oper. Res., 184 (2008), 802-809. doi: 10.1016/j.ejor.2006.11.024.