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

该项目致力于使用超大规模邻域(VLSN)搜索算法来解决几类困难的组合优化问题。VLSN搜索算法是邻域搜索算法，其中邻域的大小非常大，根据输入大小参数可能是指数的，并且枚举所有邻域并评估它们的成本高得令人望而却步。这项研究依赖于使用改进图来搜索大片社区。改进图允许对非常大的社区进行快速优化。这种方法已经被用来解决一些经典的组合优化问题以及航空和铁路行业中出现的调度问题。对于我们已经解决的问题，VLSN搜索算法，当实施得很好时，是健壮的，并提供了优秀的解决方案。该研究项目针对三类问题提出了VLSN搜索算法。第一类问题将是在聚类、数据挖掘和时间表安排中出现的大规模划分和约束划分问题。第二类问题将是物流和电信中出现的整数多商品流动问题。整数多商品流动问题是指每种商品在任意弧线上的流动都要求为整数的多商品流动问题。要调查的第三类问题将是联合航空公司出现的可选航班生成问题。可选航班生成问题的目标是确定一组很好的潜在候选者，以便将额外的航班段添加到航空公司的时间表中，以提高整体盈利能力。针对大规模、结构复杂的组合优化问题开发有效实用的启发式(近似)求解程序的需求，推动了对VLSN搜索算法的PI研究。目标是通过开发具有广泛适用性的新方法来增强启发式搜索的工具包。我们预计，我们和其他公司将成功地开发和应用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.