Combinatorial optimization: approximation algorithm and robust optimization

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

• 批准号: RGPIN-2014-06446
• 负责人: Du, Donglei
• 金额: $ 1.6万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=678625
• 关键词: 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-HARD组合优化问题的宝贵选择。强大的优化是解决优化问题的竞争范式，仅当提供了基本问题的不完整信息，从而使经典随机优化不合适，而必须知道基本概率分布的全部知识。这两个研究领域仍在快速发展，并留下许多深刻的问题。更重要的是，在大数据时代，这些方法采用这些方法仍处于起步阶段。 *我们希望研究一些与近似算法和鲁棒优化有关的特定问题。精心选择这些特定问题，使它们具有代表性，基本，基本性，并且具有巨大的潜力，可以促进对相应的主观领域的了解，并在整个过程中产生新的方法。此外，要研究的问题不仅具有理论上的重要性，而且具有很大的实际意义。我们选择了跨越设施位置理论的主观领域，集合和搜索，网络流，供应链管理，财务优化和调度的问题。拟议的研究基于我们以前的工作以及我们过去在攻击上述某些问题的成功取得了成功，这表明我们有必要的数学基础和适当的工具来处理它们。 *这项调查的结果不仅会导致有效的算法并增强对所考虑的特定问题的理解，而且还将建立基础，以创新潜在的新机制，这些机制对加拿大和国际商业和经济学的管理具有很大实践意义和重要性。