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

本提案的研究部分是关于排名和聚类。 给定的项目集合将根据某个标准（例如，从最重要到最不重要）。在聚类中，目标是对项目进行分组，以便相似的项目出现在一起。虽然研究得很好，但排名和聚类研究一直由快速产生近似结果的启发式方法主导。产生精确最优结果的优化方法研究得少得多，可能是因为这些方法需要更长的计算时间，并且在许多应用中，精度的增益并不超过计算成本。这是不幸的，因为优化方法是基于一个美丽的理论框架，并可能导致新的和有趣的结果。例如，PI对排名优化方法的初步工作表明，多个最佳解决方案可以链接到排名列表中的关系。另一方面，启发式方法并不是为了处理输出排名中的关系而设计的。该研究的两个主要目标是：（1）揭示有趣的理论联系;（2）使用经典的和聪明的新松弛技术来增加最优可解问题的大小限制。排序，也称为线性排序（LOR），在精神上与旅行商问题（TSP）很接近：两者都很简单，但很难最优解决。几十年来，在可解决的TSP的规模上取得了巨大的进展，这导致了新的和不可预见的用途。值得注意的例子出现在运输行业（涉及千城TSP）和微处理器行业（更大的TSP在电路板上布线）。预计《法律责任条例》也将取得类似的进展，在某些情况下，《法律责任条例》目前的限制是几百至几千件。然而，更大的LOR的应用比比皆是，例如基因，产品和网页的排名。 此外，TSP的突破（以及同样提出的LOR工作）不仅与规模有关，而且在理解与其他问题和领域的联系方面的理论进步和进展在整数规划的通用方法的发展中同样至关重要，例如切割平面和分支和切割技术。这项研究具有很大的影响。排名和聚类已经成为具有许多用途的标准数据分析工具。例如，Google使用排名来对用户查询产生的网页进行排序，并且还将聚类用于其“查找相似页面”功能。亚马逊在其“购买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.