Combinatorial optimization: approximation algorithm and robust optimization

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

• 批准号: RGPIN-2014-06446
• 负责人: Du, Donglei
• 金额: $ 1.6万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708320
• 关键词: 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 难组合优化问题的一个有价值的选择。鲁棒优化是一种解决优化问题的竞争范式，当只能获得有关基础问题的不完整信息时，这使得经典随机优化在必须了解基础概率分布的全部知识的情况下不适用。这两个研究领域仍在快速发展，许多深刻的问题尚未得到解答。更重要的是，在大数据时代，将这些方法应用于解决现实问题仍处于起步阶段。 我们希望研究一些与近似算法和鲁棒优化相关的具体问题。这些具体问题经过精心挑选，具有代表性、基础性、根本性，在推进相应主观领域的知识、催生新的方法论方面具有巨大的潜力。而且，所要研究的问题不仅具有理论意义，而且具有重大的现实意义。我们选择的问题涵盖设施选址理论、交会和搜索、网络流、供应链管理、财务优化和调度等主观领域。拟议的研究建立在我们之前的工作的基础上，我们过去在解决上述一些问题方面取得的成功表明我们拥有必要的数学基础和适当的工具来解决这些问题。 这项调查的结果不仅将带来有效的算法并增强对所考虑的特定问题的理解，而且还将为创新潜在的新机制奠定基础，这对加拿大和国际商业和经济的管理具有重大的现实意义和重要性。