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

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

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.