Algorithms for some hard discrete nonlinear optimization problems and applications

一些硬离散非线性优化问题的算法及应用

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

The primary objective of the proposed research program is to develop efficient algorithms for solving fundamental hard discrete optimization problems with applications in the areas of production, planning, distribution, scheduling, communication etc. An equally important objective is to train highly qualified graduate and undergraduate students and postdoctoral fellows who could apply cutting-edge algorithmic and modeling techniques to solve complex optimization projects and develop viable alternative solution approaches that improve solution quality and running time. Dissemination of research results through conference presentations and publications in reputable journals are also part of the objectives.***Accomplishment of these objectives necessitate development of new theoretical results, intelligent application of existing results, development of computer programs, and extensive experimental and theoretical analysis of algorithms. This investigator's research experience and results obtained in the past will be very useful in completing the project. In particular, domination analysis of heuristics and very large scale neighborhood search techniques developed by our research group and others will be vital algorithm design tools in the research project. The proposed research work includes, among others, solving large scale discrete optimization problems with nonlinear objective functions. Special emphasis will be given to quadratic, bilinear, and fractional objectives and applications where feasible solutions are special graph theoretic structures and/or discrete points within polyhedral sets. Variations of the binary quadratic programming problem, algorithms that uses fixed size unconstrained binary quadratic programs within a quantum computing-like framework, enhancements to variable neighborhood search algorithms, analysis of algorithms for 0-1 fractional programming problems involving ratios of linear or quadratic functions are some of the specific topics considered in this project.  We will also investigate more general nonlinear integer programs, a class of discrete optimization problems that has considerable modeling flexibility, yet relatively little algorithmic advancements have been reported in literature.***The research 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 approaches that harness theoretical and applied research. The outcome of the research work is expected to enhance the efficacy and uses of operations research methodologies for socioeconomic developments within Canada and abroad. Further, graduate and undergraduate students and postdoctoral fellows employed in the project will receive valuable research training in operations research.**

拟议的研究计划的主要目标是开发有效的算法，用于解决基本的硬离散优化问题，并在生产，计划，配送，调度，一个同样重要的目标是培养高素质的研究生和本科生和博士后研究员谁可以应用切割-边缘算法和建模技术，以解决复杂的优化项目，并开发可行的替代解决方案，提高解决方案的质量和运行时间。通过会议发言和在著名期刊上发表文章传播研究成果也是目标的一部分。实现这些目标需要发展新的理论成果，智能应用现有的结果，开发计算机程序，并广泛的实验和理论分析的算法。这位研究者过去的研究经验和成果将对完成该项目非常有用。特别是我们的研究小组和其他人开发的算法控制分析和超大规模邻域搜索技术将是研究项目中重要的算法设计工具。拟议的研究工作包括解决具有非线性目标函数的大规模离散优化问题。特别强调将给予二次，双线性和分数的目标和应用程序，其中可行的解决方案是特殊的图论结构和/或多面体集内的离散点。二进制二次规划问题的变化，在量子计算框架内使用固定大小无约束二进制二次规划的算法，对可变邻域搜索算法的增强，涉及线性或二次函数比率的0-1分式规划问题的算法分析是本项目考虑的一些具体主题。我们还将研究更一般的非线性整数规划，一类离散优化问题，具有相当大的建模灵活性，但文献中报道的算法进展相对较少。*这项研究预计将导致新的解决方案，迄今尚未解决的问题，或更有效地解决问题，从而使利用理论和应用研究的优化建模和解决方案的方法作出根本性的贡献。研究工作的成果预计将提高效率和使用运筹学方法的社会经济发展在加拿大和国外。此外，研究生和本科生以及项目中雇用的博士后研究员将接受运筹学方面的宝贵研究培训。