二次分配问题算法研究

VIP免费

3.0 侯斌 2024-11-19 4 4 1.46MB 125 页 15积分

侵权投诉

摘要

二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归入

NP-hard 问题。二次分配问题不仅以不同的形式存在于工厂布局，作业车间调度，

挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，它是一

个既有广泛的实际应用背景，又有重要的理论研究价值的优化问题。

随着二次分配问题实例规模的增长，其解空间呈现组合爆炸特征，因而通常

在多项式时间内无法求得其最优解。过去几十年，由于二次分配问题的高度求解

复杂性，已激发了人们对优化技术的研究。因此，研究二次分配问题的求解方法

对优化技术和二次分配问题自身的发展有着重要意义。

本文着重研究了以线性化技术为基础的二次分配问题的求解方法，具体包括：

(1) 详细讨论了基于匈牙利算法的二次分配问题的最优目标函数值的下界求解技

术；(2) 对原有二次分配问题的下界求解方法和二次分配问题线性化模型进行深入

研究的基础上，提出三种基于线性化技术的二次分配问题求解新方法；(3) 对输入

矩阵(流矩阵和距离矩阵)中存在零元素的二次分配问题的求解进行了探讨，为该

类特殊二次分配问题的求解提供了新的解决手段；(4) 提出使用半拉格朗日算法

求解二次分配问题的方法，这为有效求解二次分配问题提供了一种新的解决方案。

本文对所提出的二次分配问题求解方法不仅给出了其数学证明，从理论的角

度说明了各种方法的正确性，而且选用了二次分配基准问题库(QAPLIB)中的部分

实例进行了计算，将计算结果与原有方法进行比较，从实验的角度说明了本文提

出的方法对二次分配问题的求解具有较优的性能。

关键词：二次分配问题线性化下界匈牙利算法半拉格朗日松弛

ABSTRACT

Quadratic assignment problem (QAP) is one of the classical NP-hard combinatorial

optimization problems, which is simple to be described but difficult to be solved

optimally. QAP has not only been applied in various fields, including factory layout, job

shop scheduling, backboard wiring, etc., but also synthesizes a large group of typical

characteristics of the problems in combinatorial optimization. QAP is an optimization

problem with a diversity of applications and important significance of theoretical study.

With the enlargement of the scale of QAP instances, the solution space makes the

characteristic of combinatorial explosion, which therefore can not be solved in

polynomial time. Over the years, owing to its astounding computational complexity, the

QAP has drawn the researcher’s attention worldwide in improving the combinatorial

optimization algorithms and methods. Furthermore, the study on the solution methods

for the QAP plays an important role in the development of itself and the optimization

techniques.

This paper focuses on the solution methods for the QAP based on the linearization

techniques. To be more specific, which cover: (1) Several dual ascent procedures for the

lower bound of the QAP based on Hungarian algorithm are discussed in detail; (2)

Three new solution methods are proposed based on making an intensive study on the

available QAP linearization as well as the QAP lower bound methods; (3) The

resolution of the special kind of QAP in which input matrices there are many zero

elements is further studied, a new solving method, furthermore, is proposed for it; (4)

The semi-Lagrangian relaxation of the QAP is proposed, which is a new effective

solution methods for the QAP.

From the theoretical point of view, the results of mathematical derivation in this

paper show that the proposed solution methods for the QAP are feasible. From the

experimental point of view, a few of selected QAP instances in the QAPLIB are

implemented with the new proposed solution methods and some current available

methods respectively, and the investigated experimental results show that the new

proposed solution methods are more important and effective in solving the QAP.

Key Words: Quadratic assignment problem, Linearization, Lower bounds,

Hungarian algorithm, Semi-Lagrangian relaxation

中文摘要

ABSTRACT

第一章绪论.................................................................................................................1

§1.1 研究背景.............................................................................................................1

§1.2 本文主要研究内容.............................................................................................1

第二章二次分配问题.....................................................................................................5

§2.1 组合优化问题.....................................................................................................5

§2.2 算法及其分类.....................................................................................................6

§2.3 计算复杂性与 NP 完全问题 ............................................................................. 7

§2.4 二次分配问题...................................................................................................10

§ 2.4.1 QAP 模型.....................................................................................................10

§ 2.4.2 QAP 的计算复杂性.....................................................................................13

§ 2.4.3 QAP 的线性化.............................................................................................17

§ 2.4.4 QAP 的多面体描述(QAP Polytopes)........................................................ 22

§ 2.4.5 QAP 的下界计算方法.................................................................................24

§ 2.4.6 扩展 QAP 问题...........................................................................................28

§ 2.4.7 QAP 的求解方法.........................................................................................31

§ 2.4.8 QAP 的渐进特性(The Asymptotic Behavior of The QAP) ........................ 37

§2.5 小结...................................................................................................................38

第三章基于匈牙利算法的 QAP 对偶上升求解法.......................................................39

§3.1 概述...................................................................................................................39

§3.2 二次分配问题线性化模型的结构特征...........................................................39

§3.3 基于匈牙利算法的 QAP 下界对偶上升求解方法.........................................43

§ 3.3.1 匈牙利算法..................................................................................................43

§ 3.3.2 几种基于匈牙利算法的 QAP 对偶上升求解法........................................44

§3.4 算例分析...........................................................................................................53

§3.5 小结...................................................................................................................58

第四章几种求解二次分配问题的新方法...................................................................59

§4.1 概述...................................................................................................................59

§4.2 基于 Gilmore-Lawler 下界的 QAP 线性化模型 .............................................59

§ 4.2.1 Gilmore-Lawler 下界的等价形式 ...............................................................59

§ 4.2.2 QAP 问题的 Gilmore-Lawler 线性化模型 .................................................61

§ 4.2.3 算例分析......................................................................................................63

§4.3 Adams-Johnson 线性化模型的缩减与改进 ....................................................67

§ 4.3.1 Adams-Johnson 线性化模型的有效缩减 ................................................... 67

§ 4.3.2 算例分析......................................................................................................70

§4.4 一种 QAP 线性化新方法.................................................................................77

§ 4.4.1 一种 QAP 线性化新模型............................................................................77

§ 4.4.2 算例分析......................................................................................................80

§4.5 小结...................................................................................................................80

第五章稀疏二次分配问题及其求解...........................................................................83

§5.1 概述...................................................................................................................83

§5.2 稀疏二次分配问题的线性化...........................................................................83

§5.3 算例分析...........................................................................................................91

§5.4 小结...................................................................................................................96

第六章二次分配问题的半拉格朗日求解法...............................................................97

§6.1 概述...................................................................................................................97

§6.2 拉格朗日松弛方法...........................................................................................97

§6.3 半拉格朗日松弛方法(Semi-Lagrangian Relaxation).................................... 98

§6.4 求解 QAP 问题的半拉格朗日算法...............................................................102

§ 6.4.1 QAP 的半拉格朗日松弛及其对偶问题...................................................102

§ 6.4.2 QAP 的半拉格朗日松弛的核问题...........................................................104

§6.4.3 求解 QAP 的半拉格朗日松弛对偶问题的算法.......................................106

§6.5 算例分析.........................................................................................................106

§6.6 小结.................................................................................................................109

第七章结论与展望.....................................................................................................111

§7.1 全文总结.........................................................................................................111

§7.2 进一步的工作.................................................................................................112

参考文献.......................................................................................................................113

在读期间公开发表的论文和承担科研项目及取得成果...........................................125

致谢.............................................................................................................................127

第一章绪论

§1.1 研究背景

二次分配问题(quadratic assignment problem，

QAP)[1]是最经典，最具有挑战性

的组合优化问题之一[2]。自 1957 年Koopmans 和Beckmann[1]首次将 QAP 问题作

为组合优化问题提出之后，其已被广泛应用于诸多领域，许多问题象集成电路布

线[3,4]、工厂位置布局[5]、打字机键盘设计、作业调度问题[6-7]等等[2, 8-9]，都可形式

化为二次分配问题。此外，QAP 问题也被应用于统计数据分析[10]、考古数据排序[11]

和接力赛跑队的排序[12]等。另外，一些 NP-hard 组合优化问题，如旅行商问题(the

traveling salesman problem)，三角剖分问题(triangulation problem)和最大团问题

(the max clique problem)等也可以转化为二次分配问题[2, 8-9, 13]。基于 QAP 问题理论

和实际的重要性，过去几十年已激发了许多学者对其理论，应用和优化技术的研

究。

1976 年Sahni 和Gonzales[14]证明了 QAP 不仅属于 NP-hard 问题而且不存在



近似度的多项式时间近似算法(





)[15-16]。QAP 是很难求解的最优化问题，其主

要原因是所谓的“组合爆炸”现象，求解时间随问题规模呈指数增长[17]。一般而

言，当问题规模

20n

时，很难在有效的计算时间内利用经典算法找到其最优解，

如分支定界法，割平面法等[2]。为了实际可行地解决 QAP 问题，人们退而求其次，

许多启发式算法不断提出并被应用到 QAP 的求解，如：模拟退火算法[18-22]，遗传

算法[23-29]，蚂蚁算法[30-35]，粒子群算法[36-40]，禁忌搜索算法[41-46]和贪婪随机自适应

搜索算法[47-49]等。然而，这些启发式算法不能保证找到的解一定是最优解，他们

仅可以在人们可接受的时间内给出较优解。

由于 QAP 问题高度的计算复杂性和具有代表性的求解难度，许多新的算法，

理论和思想在被提出后也常常使用 QAP 作为测试其自身性能的标准，求解 QAP

问题已经成为优化技术成功的主要体现之一。

§1.2 本文主要研究内容

二次分配问题目标函数中的二次项在一定程度上增加了问题的求解复杂度，

通过一定方法将其二次项线性化，得到与原问题等价的(混合)整数规划模型，不

二次分配问题算法研究

仅会使问题的求解复杂度得到一定降低，能够应用既有的(混合)整数规划求解方

法求解 QAP 问题；而且当问题规模较大，较难求解时，可通过求解该(混合)整数

规划模型的线性松弛，求得原 QAP 问题最优解的下界值。

本文以二次分配问题的线性化技术为基础，主要研究了二次分配问题的求解

方法。本文从几种不同的角度探索并提出了多种二次分配问题的求解新方法，并

分别从理论和实验两方面讨论了各种方法的性能，为二次分配问题的求解提供了

有效的基本解决方案和手段。其整体框架内容如图 1-1 所示。

图1-1 论文整体框架内容

各章主要内容简述如下：

第一章简单介绍了本文的研究背景和本文的主要工作；

第二章对组合优化问题和二次分配问题进行了综述，介绍了目前二次分配问

题各个方面的研究现状；

研究现状

提出问题

总结与展望

第三章基于匈牙利算法

的QAP 对偶上升求解法

第二章二次分配问题

第一章绪论

第四章几种求解二次

分配问题的新方法

第五章稀疏二次分配

问题及其求解

第六章二次分配问题的半

拉格朗日求解法

第七章结论与展望

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归入NP-hard问题。二次分配问题不仅以不同的形式存在于工厂布局，作业车间调度，挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，它是一个既有广泛的实际应用背景，又有重要的理论研究价值的优化问题。随着二次分配问题实例规模的增长，其解空间呈现组合爆炸特征，因而通常在多项式时间内无法求得其最优解。过去几十年，由于二次分配问题的高度求解复杂性，已激发了人们对优化技术的研究。因此，研究二次分配问题的求解方法对优化技术和二次分配问题自身的发展有着重要意义。本文着重研究了以线性化技术为基础的二次分配问题的求解方法，具体包括：(...

展开>> 收起<<

二次分配问题算法研究.pdf

共125页,预览10页

还剩页未读，继续阅读

二次分配问题算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: