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
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758566
• 关键词: 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的考虑，将被聘为项目的研究助理。这些学生将在优化建模、算法设计和分析、机器学习、算法计算测试和量子桥分析等领域接受有价值的研究培训。