Algorithms for hard quadratic combinatorial optimization problems and linkages with quantum bridge analytics

硬二次组合优化问题的算法以及与量子桥分析的联系

• 批准号: RGPIN-2021-03190
• 负责人: Punnen, Abraham
• 金额: $ 2.62万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741820
• 关键词: Algorithms; hard; quadratic; combinatorial; optimization

The primary objective of the proposed research program is to develop efficient algorithms for solving a class of hard quadratic combinatorial optimization (QCOP) problems with applications in production, planning, communication, distribution, sequencing and scheduling, and resource allocation. An equally important objective is to train highly qualified graduate and undergraduate students, and post-doctoral fellows, fostering equity, diversity, and inclusion (EDI) considerations, who could apply cutting-edge techniques within complex optimization projects by enhancing existing procedures and developing viable alternatives. Dissemination of research results through conference presentations and publications in reputable journals are also part of the objectives. The primary focus of the algorithm design aspect of the project is aimed at developing algorithms to run on standard computers as well as bridging algorithms to run on hybrid hardware involving both standard and quantum inspired computers. Accomplishment of these long-term objectives translate into short-term goals of developing new theoretical results, intelligent application of existing results, new problem decomposition methods, clever reformulations, development of computer programs, and extensive computational and theoretical analysis of algorithms for specific problem classes identified. The investigators research experience in QCOP and results obtained in the past will be very useful in successfully completing this project. In particular, very large neighborhood search techniques developed by this investigator along with various collaborators and past research works on the quadratic unconstrained binary optimization problem (QUBO) and variants will be used in the design of algorithms. Some specific research problems include solving large scale QUBO, bipartite QUBO and other related optimization problems that fall under this general framework. The research program is expected to result in novel solution approaches exploiting recent developments in machine learning, and artificial intelligence and using technological developments in the emerging area of quantum computing and quantum bridge analytics, for solving problems of interest hitherto unsolved or for solving problems more efficiently and thereby making fundamental contributions to optimization modeling and solution approaches. Exploiting modern technological advancements and by harnessing theoretical and applied research, the proposed research work is expected to enhance the efficacy and uses of operations research methodologies for socio-economic developments within Canada and abroad. Several students with diverse backgrounds, emphasizing EDI considerations, will be employed in the project as research associates. These students will receive valuable research training in the areas of optimization modeling, design and analysis of algorithms, machine learning, computational testing of algorithms, and quantum bridge analytics.

建议的研究计划的主要目标是开发有效的算法来解决一类硬二次组合优化（QCOP）问题的应用在生产，规划，通信，分销，排序和调度，资源分配。同样重要的目标是培养高素质的研究生和本科生以及博士后研究员，促进公平，多样性和包容性（EDI）的考虑，他们可以通过加强现有程序和开发可行的替代方案在复杂的优化项目中应用尖端技术。通过会议介绍和在著名期刊上发表文章传播研究成果也是目标的一部分。该项目的算法设计方面的主要重点是开发在标准计算机上运行的算法，以及在涉及标准和量子计算机的混合硬件上运行的桥接算法。这些长期目标的实现转化为短期目标，开发新的理论成果，现有成果的智能应用，新的问题分解方法，巧妙的重新表述，计算机程序的开发，以及对特定问题类的算法进行广泛的计算和理论分析。研究者在QCOP中的研究经验和过去获得的结果将对成功完成该项目非常有用。特别是，非常大的邻域搜索技术开发的这个调查员沿着与各种合作者和过去的研究工作的二次无约束二进制优化问题（QUBO）和变种将用于算法的设计。一些具体的研究问题，包括解决大规模QUBO，二分QUBO和其他相关的优化问题，属于这个一般框架。该研究计划预计将利用机器学习和人工智能的最新发展，并利用量子计算和量子桥分析新兴领域的技术发展，产生新型解决方案，以解决迄今为止尚未解决的感兴趣问题或更有效地解决问题，从而为优化建模和解决方案做出根本性贡献。利用现代技术进步，并利用理论和应用研究，拟议的研究工作，预计将提高效率和使用运筹学方法的社会经济发展在加拿大和国外。几个不同背景的学生，强调EDI的考虑，将在项目中作为研究助理。这些学生将在优化建模，算法设计和分析，机器学习，算法计算测试和量子桥分析等领域接受宝贵的研究培训。