AF: Small: RUI: Ranking and Clustering by Integer and Linear Optimization

该方案的研究内容是关于排名和聚类。给定的项目集合将根据某种标准(例如，从最重要到最不重要)进行排序。在集群中，目标是对项目进行分组，以便相似的项目一起出现。尽管研究得很好，但排名和聚类研究一直被启发式方法所主导，这些方法很快就能产生近似的结果。产生精确最优结果的优化方法的研究要少得多，这可能是因为这些方法需要更长的计算时间，而且在许多应用中，精度方面的收益并不超过计算成本。这是不幸的，因为优化方法基于一个漂亮的理论框架，可以产生新颖而有趣的结果。例如，PI关于排名优化方法的初步工作表明，可以将多个最优解链接到排名列表中的平局。另一方面，启发式方法并不是为了处理产出排名中的平局而设计的。这项研究的两个主要目标是：(1)揭示有趣的理论联系；(2)使用经典和巧妙的新松弛技术来增加最优解问题的规模限制。排序，也称为线性排序(LOR)，在精神上与旅行商问题(TSP)非常接近：两者都很容易表述，但很难以最优方式求解。几十年来，在可溶解的TSP的大小上取得了巨大的进展，导致了新的和不可预见的用途。值得注意的例子出现在运输业(涉及千座城市的TSP)和微处理器行业(更大的TSP在电路板上布线铜线)。LOR预计也会取得类似的进展，在某些情况下，其目前的限制是几百到几千个项目。然而，更大的LOR的应用程序比比皆是，例如基因、产品和网页的排名。此外，TSP的突破(以及拟议的LOR工作)不仅与规模有关，而且理论上的进步和理解与其他问题和领域的联系的进展在整数规划通用方法的发展中也同样至关重要，例如割平面、分支和割技术。所提出的研究具有很大的影响。排名和聚类已成为具有多种用途的标准数据分析工具。例如，谷歌使用排名来对用户查询得到的网页进行排序，并使用聚类来实现其“查找相似页面”功能。亚马逊在其“购买了X的顾客也购买了Y的顾客”功能中使用了集群。Facebook和Twitter可以根据排名和聚类算法生成广告和好友推荐。为了确保拟议的研究成果能够接触到这些消费者，这项工作将通过期刊出版物和两本书广泛传播。该项目新颖的学生培训计划，包括同行指导和国际交流计划，将扩大代表不足的群体的参与。教育部分及其微积分活动手册旨在改变学生对科学的态度，并向学生灌输对科学能力的信心，这将对那些更常见的未能被留住的学生(可能是相对较大的来自代表性不足的群体)产生更大的影响，从而有助于进一步多样化和扩大对STEM学科的参与。

The research component of this proposal is about ranking and clustering. A given collection of items is to be ordered according to some criterion (e.g., from most to least important). In clustering, the goal is to group items so that similar items appear together. Though well-studied, ranking and clustering research has been dominated by heuristic methods that produce approximate results quickly. Optimization methods that produce exact optimal results have been far less studied, possibly because these methods require longer computational times, and the gains in accuracy do not outweigh the computational costs in many applications. This is unfortunate since optimization methods are based on a beautiful theoretical framework and can lead to novel and interesting results. For example, preliminary work by the PI on a ranking optimization method, indicates that multiple optimal solutions can be linked to ties in the ranked list. On the other hand, heuristic methods are not designed to handle ties in the output ranking. Two main goals of the proposed research are: (1) to reveal interesting theoretical connections, and (2) to increase the size limits of optimally solvable problems using both classical and clever new relaxation techniques.Ranking, also known as linear ordering (LOR), is close in spirit to the Traveling Salesman Problem (TSP): both are simple to state, yet hard to solve optimally. Over several decades, huge gains have been made on the size of solvable TSPs, that have resulted in new and unforeseen uses. Notable examples occur in the transportation industry (involving thousand-city TSPs) and in the microprocessor industry (with even larger TSPs routing copper wiring on circuit-boards). Similar progress is expected for the LOR, whose current limit is a few hundred to a few thousand items in some cases. Yet applications for much larger LORs abound, e.g. rankings of genes, products, and webpages. Furthermore, breakthroughs for the TSP (and likewise the proposed LOR work) have not solely been related to scale, but theoretical advances and progress in understanding connections to other problems and fields have been equally crucial in the development of general purpose methods for integer programming, such as cutting plane and branch and cut techniques. The proposed research has great impact. Ranking and clustering have become standard data analysis tools with many uses. For example, Google uses ranking to order webpages resulting from user queries, and also uses clustering for its "Find Similar Pages" function. Amazon uses clustering in its "Customers Who Bought X Also Bought Y" feature. Facebook and Twitter can generate ads and friend recommendations based on ranking and clustering algorithms. To ensure the results of the proposed research reach these consumers, the work will be widely disseminated through journal publications and two books. The project's novel student training plan, which includes peer mentoring and an international exchange program, will broaden participation of underrepresented groups. The educational component and its Calculus Activity Book, being aimed at changing students attitudes towards the sciences and at instilling confidence in scientific ability, will have the stronger impact on those students who more commonly fail to be retained (likely a relatively large number coming from underrepresented groups), and thus will help further diversify and broaden participation in STEM disciplines.