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.**