Algorithms for hard discrete optimization problems with linear and quadratic objective functions

提出的研究计划的主要目标是开发有效的算法来解决通信、分配系统、运输和资源分配领域中出现的困难优化问题。一个同样重要的目标是培训高素质的人员，他们可以通过优化现有程序和开发可行的替代办法，在复杂的优化项目中应用尖端技术。通过会议发言和在有信誉的期刊上发表文章来传播研究成果也是目标的一部分。实现这些目标需要开发新的理论结果，智能地应用现有的结果，开发计算机程序，以及对算法进行广泛的计算和理论分析。研究人员过去取得的研究经验和成果将对顺利完成这一项目非常有用。特别是，由该调查者与各种合作者一起开发的非常大的邻域搜索技术将是我们计划开发的启发式算法的重要设计工具。主要研究内容包括解决具有线性和二次目标的大规模离散优化问题，其中特殊的图论结构作为可行解。为元启发式算法的输出建立最优证书，组合结构的算法特征，以及基于网格计算的启发式算法是将被研究的其他重要课题。预计该研究方案将为迄今尚未解决的感兴趣的问题或更有效地解决问题带来新的解决办法，从而为优化建模和解决方法作出根本贡献。通过将理论研究和应用研究结合在一起，该项目预计将提高运筹学对加拿大社会经济发展的效力和用途。几名学生将作为研究助理受雇于该项目。这些学生将在优化建模、算法设计和分析以及计算测试领域接受有价值的研究培训。

The primary objective of the proposed research program is to develop efficient algorithms for solving hard optimization problems arising in the areas of communication, distribution systems, transportation, and resource allocation. An equally important objective is to train highly qualified personnel who could apply cutting-edge techniques within complex optimization projects by optimizing existing procedures and developing viable alternatives. Dissemination of research results through conference presentations and publications in reputable journals are also part of the objectives. Accomplishment of these objectives necessitate the development of new theoretical results, intelligent application of existing results, development of computer programs, and extensive computational and theoretical analysis of algorithms. The investigators research experience and results obtained in the past will be very useful in successfully completing this project. In particular, very large neighbourhood search techniques developed by this investigator along with various collaborators will be a vital design tool for heuristic algorithms we plan to develop. The intended research includes, among others, solving large scale discrete optimization problems with linear and quadratic objectives where special graph theoretic structures serve as feasible solutions. Establishing certificate of optimality for the output of metaheuristics, algorithmic characterization of combinatorial structures, and grid computing based heuristics are other important topics that will be studied. The research program is expected to result in novel solution approaches for problems of interest hitherto unsolved or for solving problems more efficiently and thereby making fundamental contributions to optimization modeling and solution methodologies. By bringing together theoretical and applied research, the project is expected to enhance the efficacy and uses of operations research for socio-economic developments of Canada. Several students 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, and computational testing.