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

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

Biological computation of the solution to the quadratic assignment problem

Biological computing provides a promising approach to attacking computationally intractable problems. The quadratic assignment problem (QAP) is a well-known NP-hard combinatorial optimization problem. This paper addresses the problem of how to solve QAP under the Adleman–Lipton-sticker model. A theoretically efficient DNA algorithm for solving QAP is proposed, which is executed by performing O(Kn⁴) operations on test tubes of DNA molecular strands with n² + K + 1 bit regions, where n is the number of facilities, and K is the length of the binary representation of an upper bound on the objective function. With the rapid progress of molecular biology techniques, the proposed algorithm might be of practical use in treating medium-sized instances of QAP.     

Minimum energy configurations on a toric lattice as a quadratic assignment problem

We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Ranking scalar products to improve bounds for the quadratic assignment problem

The eigenvalue bound for the quadratic assignment problem (QAP) is successively improved by considering a set of k-best scalar products, related to the QAP. An efficient procedure is proposedto find such a set of k-best scalar products. A class of QAPs is described for which this procedure in general improves existing lower bounds and at the same time generates good suboptimal solutions. The method leaves the user with a large flexibility in controlling the quality of the bound. However, since the method is sensitive to input data it should only be used in combination with other bounding rules.     

One-dimensional machine location problems in a multi-product flowline with equidistant locations

An assignment of machines to locations along a straight track is required to optimize material flow in many manufacturing systems. The assignment of M unique machines to M locations along a linear material handling track with the objective of minimizing the total machine-to-machine material transportation cost is formulated as a quadratic assignment problem (QAP). The distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Since an optimal solution to a problem with large M is computationally intractable (the QAP is NP-hard), a number of the amoebic properties are exploited to devise heuristics and a lower bound on the optimal solution. Computational results which demonstrate the performance of the heuristics and the lower bound are presented.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

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.     

Iterated local search for the quadratic assignment problem

Iterated local search (ILS) is a simple and powerful stochastic local search method. This article presents and analyzes the application of ILS to the quadratic assignment problem (QAP). We justify the potential usefulness of an ILS approach to this problem by an analysis of the QAP search space. However, an analysis of the run-time behavior of a basic ILS algorithm reveals a stagnation behavior which strongly compromises its performance. To avoid this stagnation behavior, we enhance the ILS algorithm using acceptance criteria that allow moves to worse local optima and we propose population-based ILS extensions. An experimental evaluation of the enhanced ILS algorithms shows their excellent performance when compared to other state-of-the-art algorithms for the QAP.     

Bounds for the quadratic assignment problem using the bundle method

Semidefinite programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the quadratic assignment problem (QAP) suggests SDP as a way to derive tractable relaxations. We recall some SDP relaxations of QAP and solve them approximately using a dynamic version of the bundle method. The computational results demonstrate the efficiency of the approach. Our bounds are currently among the strongest ones available for QAP. We investigate their potential for branch and bound settings by looking also at the bounds in the first levels of the branching tree.      

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.     

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.     

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.     

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

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

Generating Hard Test Instances with Known Optimal Solution for the Rectilinear Quadratic Assignment Problem

In this paper we consider the rectilinear version of the quadratic assignment problem (QAP). We define a class of edge-weighted graphs with nonnegatively valued bisections. For one important type of such graphs we provide a characterization of point sets on the plane for which the optimal value of the related QAP is zero. These graphs are used in the algorithms for generating rectilinear QAP instances with known provably optimal solutions. The basic algorithm of such type uses only triangles. Making a reduction from 3-dimensional matching, it is shown that the set of instances which can be generated by this algorithm is hard. The basic algorithm is extended to process graphs larger than triangles. We give implementation details of this extension and of four other variations of the basic algorithm. We compare these five and also two existing generators experimentally employing multi-start descent heuristic for the QAP as an examiner. The graphs with nonnegatively valued bisections can also be used in the construction of lower bounds on the optimal value for the rectilinear QAP.     

A contribution to quadratic assignment problems

We discuss special eases of the quadratic assignment problem (QAP) being polynomially solvable. In particular we give an algebraic condition for the cost; Matrices of a QAP which guarantees that it is equivalent with a linear assignment problem. Based on these results we develop an approximation algorithm for QAPs with non-negative symmetric cost matrices.     

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

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

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem

This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.