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 note on a polynomial time solvable case of the quadratic assignment problem

We identify a class of instances of the Koopmans–Beckmann form of the Quadratic Assignment Problem that are solvable in polynomial time. This class is characterized by a path structure in the flow data and a grid structure in the distance data. Chr18b, one of the test problems in the QAPLIB, is in this class even though this feature of it has not been noticed until now.     

Lower bounds for the quadratic assignment problem via triangle decompositions

We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.The authors gratefully acknowledge financial support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Gilmore-Lawler bound of quadratic assignment problem

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.      

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.     

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.     

Autocorrelation measures for the quadratic assignment problem

In this article we provide an exact expression for computing the autocorrelation coefficient ξ and the autocorrelation length ? of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters ξ and ? for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem.     

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.     

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.     

Compounded genetic algorithms for the quadratic assignment problem

We introduce the compounded genetic algorithm. We propose to run a quick genetic algorithm several times as Phase 1, and compile the best solutions in each run to create a starting population for Phase 2. This new approach was tested on the quadratic assignment problem with very good results.     

New bounds on the unconstrained quadratic integer programming problem

We consider the maximization for a given symmetric . It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV ^T where with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem . In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada.     

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.     

The quadratic three-dimensional assignment problem: Exact and approximate solution methods

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64.     

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     

The quadratic knapsack problem—a survey

The binary quadratic knapsack problem maximizes a quadratic objective function subject to a linear capacity constraint. Due to its simple structure and challenging difficulty it has been studied intensively during the last two decades. The present paper gives a survey of upper bounds presented in the literature, and show the relative tightness of several of the bounds. Techniques for deriving the bounds include relaxation from upper planes, linearization, reformulation, Lagrangian relaxation, Lagrangian decomposition, and semidefinite programming. A short overview of heuristics, reduction techniques, branch-and-bound algorithms and approximation results is given, followed by an overview of valid inequalities for the quadratic knapsack polytope. The paper is concluded by an experimental study where the upper bounds presented are compared with respect to strength and computational effort.     

一类特殊二次分配问题的线性化求解新方法

许多抽象于实际的二次分配问题,其流矩阵与距离矩阵中有很多零元素,求解该类二次分配问题时,可通过先行利用零元素的信息减小问题规模,缩短计算时间．以二次分配问题的线性化模型为基础,提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法,不仅从理论上证明了方法的可行性,而且从实验的角度说明了该方法比以往方法更加优越．