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

具有线性和二次目标函数的硬离散优化问题的算法

• 批准号: 170381-2010
• 负责人: Punnen, Abraham
• 金额: $ 2.4万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2011
• 资助国家: 加拿大
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=476244
• 关键词: Algorithms; hard; discrete; optimization; problems

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.

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