Algorithms for some hard discrete nonlinear optimization problems and applications

拟议研究计划的主要目标是开发有效的算法来解决生产、计划、分配、调度、通信等领域的应用程序中的基本硬离散优化问题。同样重要的目标是培养高素质的研究生和本科生以及博士后研究员，他们可以应用尖端的算法和建模技术来解决复杂的优化项目，并开发可行的替代解决方案，以提高解的质量和运行时间。通过会议报告和在有声誉的电子期刊上发表出版物来传播研究成果也是目标的一部分。 实现这些目标需要开发新的理论结果，智能地应用现有的结果，开发计算机程序，以及对算法进行广泛的实验和理论分析。这位研究人员过去获得的研究经验和成果将对完成这一项目非常有用。特别是，启发式的支配分析和我们等人开发的超大规模邻域搜索技术将是研究项目中重要的算法设计工具。将特别强调二次、双线性和分数目标和应用，其中可行的解决方案是特殊的图论结构和/或多面体集中的离散点。二次规划问题的变体、在类似量子计算的框架内使用固定大小的无约束二次规划的算法、可变邻域搜索算法的改进、涉及线性或二次函数比率的0-1分式规划问题的算法分析是本项目考虑的一些具体主题。我们还将研究更一般的非线性整数规划，这是一类离散优化问题，具有相当大的建模灵活性，但在算法方面的进展相对较少。 预计这项研究将为迄今尚未解决的感兴趣的问题或更有效地解决问题带来新的解决方法，从而为利用理论和应用研究的优化建模和解决方法作出根本性贡献。预计研究工作的结果将提高运筹学和方法论在加拿大国内外社会经济发展中的效力和用途。此外，受雇于该项目的研究生和本科生以及博士后研究员将接受有价值的运筹学研究培训。

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.