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 算法分析分数规划问题线性或二次函数的比率是本项目中考虑的一些具体主题​我们还将研究更一般的非线性整数规划，这是一类具有相当大的建模灵活性的离散优化问题，但算法进步相对较少。 ***该研究预计将为迄今为止尚未解决的感兴趣的问题或更有效地解决问题带来新的解决方法，从而为利用理论和应用的优化建模和解决方法做出基础贡献研究工作的成果预计将提高运筹学方法在加拿大和国外社会经济发展中的有效性和用途。此外，该项目雇用的研究生、本科生和博士后研究员将获得宝贵的运筹学研究培训。 **