A Grammar-Based Approach to Dynamic Programming for Combinatorial Optimization

这项拨款为开发上下文无关语法提供资金，这些语法将用于超大规模邻域（VLSN）搜索，以解决组合优化中的问题。组合优化问题出现在确定项目的最佳安排或排序非常复杂的领域。实际上，大多数组合问题本质上太复杂而无法解决最优性，而是使用启发式方法（如邻域搜索）来解决。VLSN搜索是该领域的一个重要工具，因为它提供了设计搜索邻域的灵活性，这些邻域非常大，并且也会导致有效的解决方案。这项研究包括上下文无关文法的发展，代表非常大的社区与搜索的邻居的工具。该研究的主要目标是自动化许多不同类型的VLSN搜索以及提供工具，开发新的非常大规模的neighborhoods.If成功，这项研究可以导致改进的软件开发VLSN搜索算法的组合优化问题的范围广泛。例子包括制造中的各种问题（如如何最佳地调度机器，如何在制造中排序项目等），在运输方面，如何安排提货和送货，如何有效地管理车队等），在聚类（如何聚合数据到集群中使用的数据挖掘，如何聚合客户成组的营销目的）等这项研究也可能导致使用VLSN搜索解决困难的组合问题的新方法。

This grant provides funding for the development of context free grammars that will be used in very large scale neighborhood (VLSN) search to solve problems in combinatorial optimization. Combinatorial optimization problems arise in domains where there is significant complexity in determining the optimal arrangements or sequencing of items. Most combinatorial problems in practice are intrinsically too complex to solve to optimality, and are instead solved using heuristic methodologies such as neighborhood search. An important tool within this domain is VLSN search since it offers the flexibility of designing search neighborhoods that are quite large and which also result in effective solutions. This research consists of the development of Context Free Grammars for representing very large neighborhoods in conjunction with tools for searching the neighborhoods. The primary objective of the research is to automate many different types of VLSN search as well as provide tools for developing new very large scale neighborhoods.If successful, this research can lead to improved software development for VLSN search heuristics for a wide range of combinatorial optimization problems. Examples include a variety of problems in manufacturing (such as how to schedule machines optimally, how to sequence items within manufacturing, etc.), in transportation, how to schedule pickups and deliveries, how to manage the fleet efficiently, etc.), in clustering (how to aggregate the data into clusters for use in data mining, how to aggregate customers into groups for marketing purposes) etc. This research may also lead to new ways of using VLSN search to solve hard combinatorial problems.