Collaborative Research: GOALI: New Directions in Very Large-Scale Neighborhood Search

本课题主要研究使用大规模邻域（VLSN）搜索算法求解几类复杂的组合优化问题。VLSN搜索算法是邻域搜索算法，其中邻域的大小非常大，就输入大小参数而言可能是指数级的，枚举所有邻域并评估它们是非常昂贵的。这项研究依赖于使用改进图来搜索大型社区。改进图允许快速优化非常大的邻域。该方法已被用于解决一些经典的组合优化问题以及航空和铁路行业中出现的调度问题。对于我们已经解决的问题，VLSN搜索算法，如果实现得好，是鲁棒的，并提供优秀的解决方案。本研究计划针对三个问题类别，提出VLSN搜寻演算法。第一类问题将是集群、数据挖掘和时间表中出现的大规模分区和约束分区问题。第二类问题将是物流和电信中出现的整数多商品流问题。整数多商品流问题是要求每一种商品在任意一条弧线上的流量为整数的多商品流问题。要调查的第三类问题将是联合航空公司出现的可选航班生成问题。可选航班生成问题的目标是确定一组良好的潜在候选者，这些候选者将被添加到航空公司的时间表中，以提高总体盈利能力。对于大规模和结构复杂的组合优化问题，需要开发有效和实用的启发式（近似）求解程序，这是研究VLSN搜索算法的动机。目标是通过开发具有广泛适用性的新方法来增强启发式搜索的工具包。我们预计我们和其他人将成功地开发和应用VLSN搜索技术来解决广泛的重要组合问题，包括物流和运输问题，并且通过使用这些方法将节省大量资金。

This project is concerned with solving several classes of difficult combinatorial optimization problems using very large-scale neighborhood (VLSN) search algorithms. The VLSN search algorithms are neighborhood search algorithms where the size of the neighborhood is very large, possibly exponential in terms of the input size parameters, and enumerating all neighbors and evaluating them is prohibitively expensive. The research relies on the use of improvement graphs for searching large neighborhoods. Improvement graphs allow optimizing over very large neighborhoods quickly. This methodology has been used to solve some classic combinatorial optimization problems as well as scheduling problems that have arisen in airline and railroad industries. For the problems that we have addressed, VLSN search algorithms, when implemented well, are robust and provide excellent solutions. The research project addresses VLSN search algorithms for three problem classes. The first problem class will be large-scale partitioning and constrained partitioning problems arising in clustering, data mining and timetabling. The second problems class will be integer multicommodity flow problems arising in logistics and telecommunication. Integer multicommodity flow problems are multicommodity flow problems where the flow of each commodity on any arc is required to be integer. The third class of problems to be investigated will be optional flight generation problem arising at United Airlines. The objective in the optional flight generation problem is to determine a set of good potential candidates for additional flight legs to be added to an airline schedule to improve overall profitability. The research of the PIs on VLSN search algorithms is motivated by the need to develop effective and practical heuristic (approximate) solution procedures for large-scale and structurally complex combinatorial optimization problems. The goal is to enhance the toolkit for heuristic search by developing new methodologies with broad applicability. We anticipate we and others will successfully develop and apply VLSN search techniques to a wide range of important combinatorial problem including problems arising in logistics and transportation and substantial savings will accrue by the use of these methods.