A Grammar-Based Approach to Dynamic Programming for Combinatorial Optimization

基于语法的组合优化动态规划方法

• 批准号: 0620189
• 负责人: James Orlin
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0620189&HistoricalAwards=false
• 关键词: Grammar; Based; Approach; Dynamic; Programming

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.

这笔赠款为开发上下文无关文法提供资金，这些文法将用于超大规模邻域(VLSN)搜索，以解决组合优化中的问题。组合优化问题出现在确定项目的最优排列或排序具有极大复杂性的领域。实践中的大多数组合问题本质上过于复杂，无法以最优方式解决，而是使用启发式方法(如邻域搜索)来解决。这个领域中的一个重要工具是VLSN搜索，因为它提供了设计相当大的搜索邻域的灵活性，并且也产生了有效的解决方案。这项研究包括开发上下文无关文法来表示非常大的社区，并结合用于搜索社区的工具。这项研究的主要目标是自动化多种不同类型的VLSN搜索，并为开发新的超大规模邻域提供工具。如果成功，该研究将有助于改进VLSN搜索启发式算法的软件开发，以解决广泛的组合优化问题。例如，制造业中的各种问题(例如如何优化机器调度，如何在制造中对项目进行排序等)，运输中，如何安排提货和交付，如何有效地管理车队等)，集群中(如何将数据聚合到集群中以用于数据挖掘，如何将客户聚合到组中以用于营销目的)等。这项研究还可能导致使用VLSN搜索来解决复杂组合问题的新方法。