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.
