二次分配问题及其线性化技术

本书是有关管理学中的一个分支--运筹学的的理论专著。该书以二次分配问题的线性化技术为基础，对所提出的二次分配问题求解方法不仅给出了其数学证明，从理论的角度说明了各种方法的正确性，而且选用了二次分配基准问题库(QAPLIB)中的部分实例进行了计算，将计算结果与原有方法进行比较，从实验的角度说明了本书提出的方法对二次分配问题的求解具有较好的性能。

前言
第一章 预备知识
1.1 最优化问题及其分类
1.2 组合优化问题
1.3 算法及其分类
1.4 计算复杂性与NP完全问题
第二章 二次分配问题
2.1 QAP简述
2.2 QAP模型
2.2.1 二次整数规划模型
2.2.2 迹模型
2.2.3 Kronecker内积模型
2.2.4 凹二次规划模型
2.3 QAP的目标函数均值
2.4 QAP的计算复杂性
2.4.1 QAP全局最优和近似最优的计算复杂性
2.4.2 QAP局部搜索的计算复杂性
2.5 QAP的渐进行为
2.6 扩展QAP问题
2.6.1 双二次分配问题
2.6.2 瓶颈二次分配问题
2.6.3 二次半分配问题
2.6.4 一般二次分配问题
2.6.5 多目标二次分配问题
2.6.6 二次三维分配问题
2.6.7 黑白二次分配问题
2.7 几种可转化为QAP的组合优化问题
2.7.1 旅行商问题
2.7.2 图的分割问题
2.7.3 最大团问题
2.7.4 图的同构
2.7.5 图的包装
2.8 二次分配问题的应用
第三章 二次分配问题的求解方法
3.1 经典求解方法
3.1.1 分支定界法
3.1.2 割平面法
3.1.3 求解QAP的其他经典方法
3.2 启发式求解算法
3.2.1 模拟退火算法
3.2.2 遗传算法
3.2.3 蚁群算法
3.2.4 粒子群算法
3.2.5 禁忌搜索算法
3.2.6 贪婪随机自适应搜索过程
3.2.7 大洪水算法
第四章 二次分配问题的线性化及其多面体描述
4.1 QAP线性化模型
4.1.1 Lawler QAP线性化模型
4.1.2 Kaufman-Broeckx类QAP线性化模型
4.1.3 Flow-Based QAP线性化模型
4.1.4 Frieze-Yadegar QAP线性化模型
4.1.5 Adams-Johnson 类 QAP线性化模型
4.1.6 QAP高阶模型
4.2 QAP的多面体描述
第五章 二次分配问题的下界计算方法
5.1 Gilmore-Lawler类下界
5.1.1 二次分配问题线性化模型的结构特征
5.1.2 Gilmore-Lawler下界
5.1.3 基于缩减技术的QAP下界计算方法
5.1.4 基于再建模技术的QAP下界计算方法
5.1.5 基于匈牙利算法的QAP下界对偶上升求解方法
5.2 QAP线性化模型的线性松驰
5.2.1 Frieze-Yadegar模型和Adams-Johnson模型的线性松驰
5.2.2 Kaufman-Broeckx类模型的线性松驰
5.3 方差缩减下界计算方法
5.4 基于正交松驰的QAP下界计算方法
5.5 基于凸二次松驰的QAP下界计算方法
5.6 基于正定规划的QAP下界计算方法
第六章 几种特殊二次分配问题及其求解
6.1 稀疏二次分配问题
6.1.1 稀疏二次分配问题的线性化
6.1.2 算例分析
6.2 对称二次分配问题
6.2.1 对称二次分配问题及其线性化模型
6.2.2 对称二次分配问题的多面体描述
6.2.3 非对称二次分配问题的对称化
6.2.4 算例分析
参考文献