A Grammar-Based Approach to Dynamic Programming for Combinatorial Optimization

点击翻译按钮获取中文摘要

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.