Combinatorial optimization: approximation algorithm and robust optimization

组合优化：近似算法和鲁棒优化

• 批准号: RGPIN-2014-06446
• 负责人: Du, Donglei
• 金额: $ 1.6万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612223
• 关键词: Combinatorial; optimization; approximation; algorithm; robust

The objective of the research program is to develop general algorithmic theories in combinatorial optimization problems that are expected to have a significant impact on such applications as supply chain management, production/operations management, network flow, location and routing, scheduling, telecommunication, transportation, health, bioinformatics, and others. Approximation algorithm with provable performance is a valuable option for solving large-scale NP-hard combinatorial optimization problems. Robust optimization is a competitive paradigm to solve optimization problems when only incomplete information on the underlying problems is available, rendering the classical stochastic optimization inappropriate where the full knowledge of the underlying probability distribution must be known. These two research areas are still developing at a rapid pace, and leave many profound questions unanswered. More important, the adoption of these methods into real-world problems is still in its infancy in the big data era. We wish to study some specific problems related to approximation algorithm and robust optimization. These specific problems are carefully chosen such that that they are representative, basic, fundamental, and possess great potential in advancing the knowledge of the corresponding subjective areas in particular and spawning new methodologies at large. Moreover, the problems to be investigated are not only of theoretical importance, but also great practical significance. We have selected problems that span the subjective areas of facility location theory, rendezvous and search, network flow, supply chain management, finance optimization, and scheduling. The proposed research builds upon our previous work and our past success in attacking some of the aforementioned problems is an indicator that we have the necessary mathematical groundings and proper tools to work on them. The results of this investigation will not only lead to efficient algorithms and enhanced understanding for the particular problems under consideration, but will also build foundations to innovate potential new mechanisms that are of great practical significance and importance to the management of Canadian and international business and economics.

该研究计划的目标是开发组合优化问题的通用算法理论，这些问题预计将对供应链管理，生产/运营管理，网络流，位置和路由，调度，电信，运输，健康，生物信息学等应用产生重大影响。 具有可证明性能的近似算法是求解大规模NP难组合优化问题的一种有效方法。鲁棒优化（Robust Optimization）是一种竞争性的优化方法，它可以在只有不完全信息的情况下解决优化问题，使得经典的随机优化方法不适用于必须知道基本概率分布的情况。这两个研究领域仍在快速发展，并留下许多深刻的问题没有得到回答。更重要的是，在大数据时代，将这些方法应用于现实世界的问题仍处于起步阶段。 我们希望研究与近似算法和鲁棒优化有关的一些具体问题。这些具体问题是经过精心挑选的，因此它们具有代表性、基本性和根本性，并具有极大的潜力，特别是在推进相应的主观领域的知识和产生新的方法论方面。研究的问题不仅具有重要的理论意义，而且具有重要的现实意义。我们选择的问题，跨越主观领域的设施选址理论，会合和搜索，网络流，供应链管理，财务优化和调度。拟议的研究建立在我们以前的工作和我们过去的成功，在攻击上述一些问题是一个指标，我们有必要的数学基础和适当的工具来解决这些问题。 这项调查的结果不仅会导致有效的算法和加强对正在考虑的特定问题的理解，但也将建立基础，创新潜在的新机制，具有重大的实际意义和重要性，加拿大和国际商业和经济的管理。