二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

几种基于匈牙利算法求解二次分配问题的方法及其分析比较

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。二次分配问题的线性化模型和下界计算方法,是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础,根据现有QAP对偶上升下界计算方法中的具体操作,提出几种可行的QAP对偶上升计算新方法。最后,通过求解QA-PLIB中的部分实例,深入分析其运行结果,详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度,这为基于匈牙利算法求解二次分配问题的方法的改进奠定了基础。     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

求解二次分配问题的拉格朗日松弛新方法

以改进的拉格朗日松弛(Lagrangian relaxation,LR)方法和二次分配问题(quadratic assignment problem,QAP)的线性化模型为基础,给出了求解QAP的拉格朗日松弛新方法,这为有效求解QAP提供了一种新的解决方案.通过求解二次分配基准问题库(QAPLIB)中的实际算例,从实验的角度说明了拉格朗日松弛新方法求解QAP的可行性及存在的不足之处,并对今后进一步的研究工作指明了方向.     

正定二次型判别条件的证明

正定二次型判别条件的证明刘学鹏（临沂师专２７６００５）在二次型的理论中，正定二次型是一类特殊而重要的二次型，相应的正定矩阵也是一类特殊而重要的矩阵．对于实二次型，其正定性的判别法之一，是利用其顺序主子式是否大于零．此理论根据的证明，笔者依据目前流行的...     

非线性特征值问题的二次近似方法

本文研究求解非线性特征值问题的数值方法.基于矩阵值函数的二次近似,将非线性特征值问题转化为二次特征值问题,提出了求解非线性特征值问题的逐次二次近似方法,分析了该方法的收敛性.结合求解二次特征值问题的Arnoldi方法和Jacobi-Davidson方法,给出求解非线性特征值问题的一些二次近似方法.数值结果表明本文所给算法是有效的.     

一种求解物流设施二次分配问题的混合分布估计算法

为了求解物流设施二次分配问题,提出了一种混合分布估计算法(HEDA)。首先,根据QAP的距离和物流量矩阵信息,提出了一种基于假设物流中心启发式规则的种群初始化方法,用于提高初始种群的质量和算法的搜索效率;其次,针对HEDA的概率模型,提出了一种概率矩阵初始构型生成机制和扰动操作,用于提高算法的全局探索能力;最后,在分析QAP的结构性质的基础上,设计了一种基于快速评价的局部搜索策略,用于提高算法的局部开发能力。仿真计算实验和算法比较验证了HEDA的优化性能。     

多参数二次特征值问题重特征值的灵敏度分析

本文研究解析依赖于多参数的二次特征值问题重特征值的灵敏度分析,得到了重特征值的方向导数,证明了相应的特征向量矩阵和特征值平均值的解析性,给出了其一阶偏导数的表达式．然后以这些结论为基础,定义了二次特征值问题重特征值及其不变子空间的灵敏度,并给出了确定二次特征值问题所含矩阵中敏感元素的方法．     

一类大规模二次规划问题的可行下降分解算法

本文对一类大规模二次规划问题，提出了矩阵剖分的概念和方法，并将问题转化为求解一系列容易求解的小规模二次规划子问题．另外，通过施加某些约束机制，使子问题所产生的迭代点均为可行下降点．在通常的假定下，证明算法具有全局收敛性，大量数值实验表明，本文所提出的新算法是有效的。     

一类二次规划逆问题的交替方向数值方法

考虑求解一类二次规划逆问题的交替方向数值算法．首先给出矩阵变量子问题解的显示表达式,而后构造了两个求解向量变量子问题近似解的数值算法,其中一个算法基于不动点原理,另一算法则应用半光滑牛顿法．数值实验表明,所提出的算法能够快速高效地求解二次规划逆问题．     

求解二次分配问题的新的流量模型

二次分配问题是具有广泛应用背景的经典组合优化难题之一。本文在二次分配问题已有线性化模型的基础上,提出了一种新的基于流量的线性化模型。数值试验结果表明,新模型无论从时间上还是计算节点数都更具有优势。     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods

This paper reports heuristic and exact solution advances for the Quadratic Assignment Problem (QAP).QAPinstances most often discussed in the literature are relatively well solved by heuristic approaches. Indeed, solutions at a fraction of one percent from the best known solution values are rapidly found by most heuristic methods. Exact methods are not able to prove optimality for these instances as soon as the problem size approaches 30 to 40. This article presents new QAP instances that are ill conditioned for many metaheuristic-based methods. However, these new instances are shown to be solved relatively well by some exact methods, since problem instances up to a size of 75 have been exactly solved.     

A Hybrid Metaheuristic for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%. This work was supported in part by the National Science Council, R.O.C., under Contract NSC 91-2213-E-005-017.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.