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

合作研究：GOALI：超大规模邻域搜索的新方向

• 批准号: 0217123
• 负责人: James Orlin
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0217123&HistoricalAwards=false
• 关键词: Collaborative; Research; GOALI; New; Directions

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.

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