American Institute of Mathematical Sciences

Advanced
doi: 10.3934/fods.2021010

On the linear ordering problem and the rankability of data

Thomas R. Cameron 1, , Sebastian Charmot 2, and  Jonad Pulaj 2,

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 Published  April 2021

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: Linear ordering problem, degree of linearity, Kendall tau distance, valid inequalities, rankability.
Mathematics Subject Classification: 52B12, 90C09, 90C27, 90C35.
Citation: Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj. On the linear ordering problem and the rankability of data. Foundations of Data Science, doi: 10.3934/fods.2021010
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

T. R. Cameron, S. Charmot and J. Pulaj, Diameter polytopes of feasible binary programs, preprint, arXiv: 2008.06844. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

T. Chartier and J. Peachey, Reverse engineering college rankings, Math Horiz., 22 (2014), 5-7.  doi: 10.4169/mathhorizons.22.2.5.  Google Scholar

[8]

S. L. Chau, J. González and D. Sejdinovic, Learning inconsistent preferences with kernal methods, preprint, arXiv: 2006.03847. Google Scholar

[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. Google Scholar

[10]

CPLEX, IBM ILOG CPLEX 12.9 User's Manual, IBM ILOG CPLEX Division, Incline Village, NV, 2019. Available from: https://www.ibm.com. Google Scholar

[11] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.   Google Scholar
[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Gurobi Optimization, Reference manual, 2020., Available from: http://www.gurobi.com. Google Scholar

[21]

L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR, 244 (1979), 1093-1096.   Google Scholar

[22]

M. G. Kendall, A new measure of rank correlation, Biometrika, 30 (1938), 81-93.  doi: 10.2307/2332226.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar
[26] J. Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2004.  doi: 10.1017/CBO9780511616655.  Google Scholar
[27] W. Leontiff, Input-Output Economics, Oxford University Press, NY, 1986.  doi: 10.1038/scientificamerican1051-15.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[30]

G. Reinelt, A note on small linear-ordering polytopes, Discrete Comput. Geom., 10 (1993), 67-78.  doi: 10.1007/BF02573963.  Google Scholar

[31]

Spreadspoke, NFL scores and betting data, 2020., Available from: https://www.kaggle.com/tobycrabtree/nfl-scores-and-betting-data. Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

T. R. Cameron, S. Charmot and J. Pulaj, Diameter polytopes of feasible binary programs, preprint, arXiv: 2008.06844. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

T. Chartier and J. Peachey, Reverse engineering college rankings, Math Horiz., 22 (2014), 5-7.  doi: 10.4169/mathhorizons.22.2.5.  Google Scholar

[8]

S. L. Chau, J. González and D. Sejdinovic, Learning inconsistent preferences with kernal methods, preprint, arXiv: 2006.03847. Google Scholar

[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. Google Scholar

[10]

CPLEX, IBM ILOG CPLEX 12.9 User's Manual, IBM ILOG CPLEX Division, Incline Village, NV, 2019. Available from: https://www.ibm.com. Google Scholar

[11] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.   Google Scholar
[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Gurobi Optimization, Reference manual, 2020., Available from: http://www.gurobi.com. Google Scholar

[21]

L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR, 244 (1979), 1093-1096.   Google Scholar

[22]

M. G. Kendall, A new measure of rank correlation, Biometrika, 30 (1938), 81-93.  doi: 10.2307/2332226.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar
[26] J. Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2004.  doi: 10.1017/CBO9780511616655.  Google Scholar
[27] W. Leontiff, Input-Output Economics, Oxford University Press, NY, 1986.  doi: 10.1038/scientificamerican1051-15.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[30]

G. Reinelt, A note on small linear-ordering polytopes, Discrete Comput. Geom., 10 (1993), 67-78.  doi: 10.1007/BF02573963.  Google Scholar

[31]

Spreadspoke, NFL scores and betting data, 2020., Available from: https://www.kaggle.com/tobycrabtree/nfl-scores-and-betting-data. Google Scholar

[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.  Google Scholar

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

Download full-size image

Download as PowerPoint slide

Figure 2.  Simple Digraphs on $ 3 $ vertices
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

[1]

Dinh T. Tran, John A. G. Roberts. Linear degree growth in lattice equations. Journal of Computational Dynamics, 2019, 6 (2) : 449-467. doi: 10.3934/jcd.2019023
[2]

C. Davini, F. Jourdan. Approximations of degree zero in the Poisson problem. Communications on Pure & Applied Analysis, 2005, 4 (2) : 267-281. doi: 10.3934/cpaa.2005.4.267
[3]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019
[4]

Xin Yang Lu. Regularity of densities in relaxed and penalized average distance problem. Networks & Heterogeneous Media, 2015, 10 (4) : 837-855. doi: 10.3934/nhm.2015.10.837
[5]

Jia Shu, Zhengyi Li, Weijun Zhong. A market selection and inventory ordering problem under demand uncertainty. Journal of Industrial & Management Optimization, 2011, 7 (2) : 425-434. doi: 10.3934/jimo.2011.7.425
[6]

Raz Kupferman, Asaf Shachar. On strain measures and the geodesic distance to $SO_n$ in the general linear group. Journal of Geometric Mechanics, 2016, 8 (4) : 437-460. doi: 10.3934/jgm.2016015
[7]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017
[8]

Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete & Continuous Dynamical Systems, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971
[9]

Joss Sánchez-Pérez. On the linearity property for allocation problems and bankruptcy problems. Journal of Dynamics & Games, 2018, 5 (1) : 9-20. doi: 10.3934/jdg.2018002
[10]

Yong Zhang, Huifen Zhong, Yue Liu, Menghu Huang. Online ordering strategy for the discrete newsvendor problem with order value-based free-shipping. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1617-1630. doi: 10.3934/jimo.2018114
[11]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[12]

Jesus Idelfonso Díaz, Jean Michel Rakotoson. On very weak solutions of semi-linear elliptic equations in the framework of weighted spaces with respect to the distance to the boundary. Discrete & Continuous Dynamical Systems, 2010, 27 (3) : 1037-1058. doi: 10.3934/dcds.2010.27.1037
[13]

Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028
[14]

Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002
[15]

Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Linear type centers of polynomial Hamiltonian systems with nonlinearities of degree 4 symmetric with respect to the y-axis. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 887-912. doi: 10.3934/dcdsb.2018047
[16]

Giovanni F. Gronchi, Chiara Tardioli. The evolution of the orbit distance in the double averaged restricted 3-body problem with crossing singularities. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1323-1344. doi: 10.3934/dcdsb.2013.18.1323
[17]

Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473
[18]

Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021083
[19]

Mohsen Lashgari, Ata Allah Taleizadeh, Shib Sankar Sana. An inventory control problem for deteriorating items with back-ordering and financial considerations under two levels of trade credit linked to order quantity. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1091-1119. doi: 10.3934/jimo.2016.12.1091
[20]

Giovanni Cupini, Eugenio Vecchi. Faber-Krahn and Lieb-type inequalities for the composite membrane problem. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2679-2691. doi: 10.3934/cpaa.2019119

 Impact Factor: 

Tools

Metrics

  • PDF downloads (22)
  • HTML views (90)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences