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