二次指派问题(Quadratic Assignment Problem，简称QAP)自1957年问世以来就一直是国际研究热点之一，广为世界各地的数学家、计算机科学家、运筹学者以及工程设计师所关注。一方面是因为它的实际和理论的重要性，另一方面是由于它的计算复杂性，它是组合优化领域最困难的问题之一，不仅本身是NP-难问题，而且求一个∈近似解也是NP-难的。　　 本文在扼要综述了二次指派问题理论和算法各研究分支的结果之上分别作出了多项贡献。　　 第二章我们完善了置换方阵直接消去分解的结构分析，为后继工作提供了理论工具。我们还提出了平移消去分解。　　 第三章我们提出了二次指派问题的两个新线性化XYL1(A，B)和XYL2(A，B)，它们都是当时规模最小的线性化。然后我们基于置换方阵的直接消去分解又提出了两个新的更小规模的线性化，SL1(A，B)和SL2(A,B)，从而回答了“Kaufman-Broeckx线性化是否是二次指派问题规模最小的线性化”这个公开问题。最后，我们还提出了一种新的中等规模的线性化XL(A，B)。　　 第四章我们改进了二次指派问题的很多下界，提出了一些新颖的下界。在线性规划下界部分，松弛我们的线性化XYL2(A，B)得到线性规划下界RXYL2(A，B)，我们证明了它不弱于经典的Gilmore-Lawler下界GLB(A，B)，且在一定的假定下我们证明了RXYL2(A，B)严格大于GLB(A，B)。我们证明了判断是否GLB(A，B，C)=QAP(A，B，C)这一NP-完全问题的计算复杂度最多是O(nk+3)，k是GLB(A，B，C)的最优顶点解的个数。最后我们讨论了线性化XYL2(A，B)的Lagrangian松弛下界和Lagrangian分解下界。在特征值下界部分，我们给出了改进原始特征值下界的方法，对投影特征值下界，我们也给出了两种改进方法。此外，我们提出了一个Gilmore-Lawler类型的投影特征值下界，它不弱于投影特征值下界，而且计算简单，复杂度O(n3)。我们改善了信赖域型下界TB(A，B，C)。我们建立了基于直接消去分解的投影信赖域型下界TRB(A，B，C)，证明了它至少不比在某个二次指派问题的等价变形下的信赖域型下界弱。随后，我们对该投影信赖域型问题添加了一个凹二次约束，它来自我们对置换方阵直接消去分解的精细结构分析。我们证明了添加了这样一个凹二次约束之后的问题仍然具有强对偶性，其对偶为一半正定规划，我们同时给出了该问题的最优解形式，而且其计算复杂度只有O(n3)。原来的约束是半径为(√n-1)的(n-1)2维超球的一个子集合，我们添加的这个约束相当于从原来的那个约束集合内再挖去一个半径为(√n-2)的开球。因此我们在不改变计算量的前提下极大地改进了投影信赖域型下界。随后我们利用上一小节改进投影特征值下界的技巧进一步改进了TRB(A，B，C)。在二次规划下界部分，我们先讨论了如何改进简单的二次规划下界。我们给出了基于改进的投影特征值下界的技巧的两个凸二次规划下界，证明其中之一不比改进的投影特征值下界弱，且在一定假定下要严格强。我们提出了基于改进的投影信赖域下界TRB(A，B，C)的凸二次规划下界QTRB(A,B，C)，证明了它不比TRB(A,B，C)弱，而且在一定假定下要严格强。进一步我们基于前一节改进TRB(A,B，C)的技巧也得到了两个凸二次规划下界，并证明了一定的紧性结果。在求解这类坏条件数的凸二次规划方面，我们利用二维子空间搜索改进了传统的Frank-Wolfe算法效率，取得了良好的计算效果。最后在半正定规划下界方而，我们给出了两个新的含O(n4)变量的半正定规划下界，证明了它们不比相应的二次规划下界弱。我们首次提出了简单的只含O(n2)个变量的半正定规划，在介绍了文献最新的也是更强的含O(n2)个变量的半正定规划之后，我们给出了基于直接消去分解的相应的半正定规划下界，基于此我们还提出了一个很强的线性规划下界。最后，我们建立了一个含O(n3)个变量的半正定规划，我们证明了它不比最新文献中的O(n2)变量的半正定规划弱。我们也证明了它不比相应的二次规划下界弱。最后我们也利用直接消去分解技术给出了相应的半正定规划下界和相应的理论结果。　　 第五六七章是算法方面。我们改善了传统的割平面算法效率，讨论了还不成熟的两边夹算法。我们提出了非单调局部搜索算法。基于我们的线性化XYL1(A，B)极大地改善了启发式割平面算法的效率，给出了相应的数值结果，并进一步结合禁忌搜索提高了计算效率。我们对一般的带线性约束的非线性0-1优化问题提出了新的连续化方法，它被成功地应用到二次指派问题上，数值结果显示了我们策略的优越性，此外我们还讨论了二次指派问题的舍入技巧。对比新的连续化方法和蚂蚁群体的社会进化模拟，我们原创地提出了蚁群社会进化算法，我们给出了初步的计算结果。最后一节我们提出了一些还不成熟的工作：包括选取好的初始点的一个方法，邻域连续化方法以及线性回归算法。