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

AF：小：RUI：通过整数和线性优化进行排名和聚类

• 批准号: 1116963
• 负责人: Amy Langville
• 金额: $ 39.99万
• 依托单位: College of Charleston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116963&HistoricalAwards=false
• 关键词: AF; Small; RUI; Ranking; Clustering

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.

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