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.