（混合）整数规划问题的快速半拉格朗日蝙蝠算法及其应用研究

This project studies on the new intelligent algorithm and exact algorithm for (mixed) integer programming problems. On the one hand, one hybrid Lagrangian bat-inspired algorithm will be proposed for large-scale (mixed) integer programming problems through exploring the combination schemes of Lagrangian relaxation and the bat-inspired algorithm. The hybrid Lagrangian bat-inspired algorithm, inheriting from the Lagrangian relaxation the ability to calculate lower bounds on the objective and from the bat-inspired algorithm the ability to calculate upper bounds, can iteratively improve the solutions close to the optimal ones. The convergence property of the hybrid Lagrangian bat-inspired algorithm is studied by using the functional analysis or markov chain. On the other hand, fast semi-Lagrangian relaxation will be presented by improving the initialization and updating method of the Lagrangian multipliers, and the solution methods for the semi-Lagrangian relaxation problem. The performances and mechanism of the fast semi-Lagrangian relaxation are also explored by using the computational mathematics and combinatorial mathematics. Not only the performances of the hybrid Lagrangian bat-inspired algorithm and fast semi-Lagrangian relaxation are investigated by solving some typical combinatorial optimization problems, but also the application effect of the algorithms are studied by solving the real-word optimization problems in the fields of forest management and logistics distribution. The algorithms proposed in this project can provide some new solution methods for interdisciplinary fields such as operations research, intelligent optimization and management science, etc, and develop new solving techniques for some hard problems in engineering technology, social economy, etc.

本项目研究求解（混合）整数规划问题的新型智能优化算法和精确算法。一方面，通过有效利用由拉格朗日松弛方法提供的下界和蝙蝠算法提供的上界，从下界和上界两侧逐渐逼近问题的最优解，提出有利于大规模（混合）整数规划问题求解的拉格朗日蝙蝠智能优化算法，并借助泛函分析或马尔科夫链论证算法的渐近收敛性。另一方面，从拉格朗日乘子初始值的设定、更新和求解半拉格朗日松弛问题的算法三方面改进半拉格朗日松弛方法，提出求解效率更高的快速半拉格朗日松弛方法，并借助计算数学和组合数学等工具研究算法的求解性能和内在机理。项目不仅将拉格朗日蝙蝠智能优化算法与快速半拉格朗日松弛方法面向若干典型的组合优化难题进行测试，而且以森林管理和物流配送这两个应用领域为背景检验其实用效果。本项目研究不仅为运筹学、智能优化及管理科学等一系列跨学科领域发展新的求解方法，而且为工程技术和社会经济管理等范畴内的相关问题提供有效的解决手段。

本项目研究求解（混合）整数规划问题的快速半拉格朗日松弛算法和智能优化算法。一方面，从拉格朗日初始值的设定、更新和求解半拉格朗日松弛问题的算法等方面对半拉格朗日松弛方法进行了改进，并从理论和实验两方面对改进后的算法的求解性能和内在机理进行了研究。另一方面，在混沌搜索、量子搜索、仿生蚂蚁系统、蝙蝠优化算法、狼群系统、蜂群算法、遗传算法、拉格朗日松弛方法等思想的基础上，对这些基本优化方法加以融合和重构，提出了混沌蝙蝠算法、量子蚁群算法、拉格朗日蝙蝠算法、拉格朗日蚁群算法、拉格朗日狼群算法、遗传蚁群算法等一系列混合智能优化算法，并面向若干经典组合优化难题及有关实际应用领域测试了其求解效果。本项目研究内容不仅为运筹学、智能优化及管理科学等一系列跨学科领域发展新的求解方法，而且为工程技术和社会经济管理等范畴内的相关问题提供有效的解决手段。