Figure 1.
Linear Ordering Polytope: $ P^{3}_{ \rm{LO}} $
-
Previous Article
Normalization effects on shallow neural networks and related asymptotic expansions
- FoDS Home
- This Issue
-
Next Article
Wave-shape oscillatory model for nonstationary periodic time series analysis
June
2021, 3(2): 133-149.
doi: 10.3934/fods.2021010
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 |
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,
2021, 3
(2)
: 133-149.
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. |
| [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. |
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. |
| [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. |
Figure 2.
Simple Digraphs on $ 3 $ vertices
Figure 3.
Optimal Solution(s) on Linear Ordering Polytope
Figure 4.
College Features from U.S. World News 2013 Rankings
Figure 5.
The degree of linearity and the hindsight accuracy of NFL rankings
Figure 6.
Correlation between the degree of linearity and the hindsight accuracy of NFL rankings
Figure 7.
The absolute difference between the foresight accuracy of two optimal rankings
Figure 8.
Diversity among NFL playoff teams in two optimal rankings for years 1992 and 1999
Figure 9.
NFL playoff progression in 1992; the opaque team lost the indicated matchup
Figure 10.
NFL playoff progression in 1999; the opaque team lost the indicated matchup
| [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 and 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 and 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 and 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 and Management Optimization, 2022, 18 (2) : 1247-1259. doi: 10.3934/jimo.2021017 |
| [8] |
Joss Sánchez-Pérez. On the linearity property for allocation problems and bankruptcy problems. Journal of Dynamics and Games, 2018, 5 (1) : 9-20. doi: 10.3934/jdg.2018002 |
| [9] |
Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete and Continuous Dynamical Systems, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971 |
| [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 and 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 and 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 and Continuous Dynamical Systems - B, 2018, 23 (2) : 887-912. doi: 10.3934/dcdsb.2018047 |
| [16] |
Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473 |
| [17] |
Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021132 |
| [18] |
Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2599-2610. doi: 10.3934/jimo.2021083 |
| [19] |
Giovanni F. Gronchi, Chiara Tardioli. The evolution of the orbit distance in the double averaged restricted 3-body problem with crossing singularities. Discrete and Continuous Dynamical Systems - B, 2013, 18 (5) : 1323-1344. doi: 10.3934/dcdsb.2013.18.1323 |
| [20] |
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 and Management Optimization, 2016, 12 (3) : 1091-1119. doi: 10.3934/jimo.2016.12.1091 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]