Multiple linear ordering problem
研究线性排序问题中多个最优解带来的排序差异，提出将排序稳定性建模为优化问题的新方法，并设计启发式算法处理大规模实例，帮助用户从多个最优排序中获取更可靠的信息。
The linear ordering problem (LOP) is a well-known NP-hard combinatorial optimization problem. Given a set of elements and its dominance matrix, the objective is to find a simultaneous ordering of rows and columns of the matrix, to maximize the sum of entries above the main diagonal. This linear ordering returns a rank of the elements maximizing the dominance, which provides a practical tool in many applications from economy to social networks. However, the LOP may have many alternate optima with significantly different orderings, which makes it difficult to provide an optimal representative ranking. In this paper, we study the rankability of the input matrix in terms of the similarities among alternate optimal rankings. We propose new mathematical models to formulate the rankability as an optimization problem. We also present a heuristic algorithm, based on the VNS methodology, to target large instances. Our computational testing shows that the analysis of several alternate optimal solutions may provide the user with practical information to overcome the limitations of a single optimal ranking.