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.