The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach

In this paper, we apply the statistical mechanics formalism to study quadratic sum assignment problems (QSAP). This formalism allows us to exhibit, in the limit of large problems, the asymptotic behaviour of the optimal value of the cost function. The conclusions of the study are confirmed by the results of Metropolis computer simulations.     

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.     

On random quadratic bottleneck assignment problems

The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficientsd _ijpq =a _ip b _jq is considered, wherea _ip is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function(m), tending to zero, with probability tending to one asm , provided the data are uniformly distributed. This implies that any algorithm for the above mentioned problems yields asymptotically an arbitrarily small relative error with probability tending to one.     

A note on asymptotic properties of the quadratic assignment problem

We sharpen and simplify previous work of Frenk, Van Houweninge and Rinnooy Kan on the stochastic version of the quadratic assignment problem.     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

A novel chaotic search for quadratic assignment problems

We propose a novel method for solving the quadratic assignment problems. First, we realize the conventional tabu search on a neural network, and modify it to a chaotic version. Our novel method includes both effects of chaotic dynamics and tabu search. We compare the performance of the novel chaotic search with the conventional tabu search and an exponential tabu search whose memory effect for tabu (forbidding previous moves) decays exponentially. We show that the exponential tabu search has higher performance than the conventional tabu search, and further that the novel method with a chaotic neural network exhibits the best performance. We also propose a controlling method of the chaotic neural network for realizing easy and robust applications of our method. Then, better performance can be realized without manual parameter setting for various problems.     

The formulation and numerical method for partial quadratic eigenvalue assignment problems

In this paper, we consider the minimum norm and robust partial quadratic eigenvalue assignment problems (PQEVAP). A complete theory on the existence of solutions for the PQEVAP is established. It is shown that solving the PQEVAP is essentially solving an eigenvalue assignment for a linear system of a much lower order, and the minimum norm and robust PQEVAPs are then concerning the minimum norm and robust eigenvalue assignment problems associated with this linear system. Based on this theory, an algorithm for solving the minimum norm and robust PQEVAPs is proposed, and its efficient behaviors are illustrated by some numerical examples. Copyright © 2010 John Wiley & Sons, Ltd.     

A heuristic for quadratic Boolean programs with applications to quadratic assignment problems

A heuristic for quadratic Boolean programs is presented. Computational tests with quadratic assignment problems (QAP) showed that it finds very good suboptimal solutions in moderate time and behaves computationally stable. In the appendix a FORTRAN-program for QAP is listed which improves an earlier code published by Burkard and Derigs.     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

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.     

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.     

Global optimality conditions and optimization methods for quadratic assignment problems

In this paper some global optimality conditions for general quadratic {0, 1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods.     

The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time.Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.     

A note on the asymptotic behaviour of bottleneck problems

We generalize and sharpen results of Burkard and Fincke concerning the asymptotic behaviour of a certain class of combinatorial optimization problems with bottleneck objective function. In this way several open questions are answered.     

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et?al. (J Comb Optim 2:71–109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.     

On the asymptotic behaviour of the ideal counting function in quadratic number fields

LetK be a quadratic number field with discriminantD and denote byF(n) the number of integral ideals with norm equal ton. Forr≥1 the following formula is proved $$\sum\limits_{n \leqslant x} {F(n)F(n + r) = M_K (r)x + E_K (x,r).} $$ HereM _k (r) is an explicitly determined function ofr which depends onK, and for every ε>0 the error term is bounded by \(|E_K (x,r)|<< |D|^{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-0em} 2} + \varepsilon } x^{{5 \mathord{\left/ {\vphantom {5 6}} \right. \kern-0em} 6} + \varepsilon } \) uniformly for \(r<< |D|^{{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}} x^{{5 \mathord{\left/ {\vphantom {5 6}} \right. \kern-0em} 6}} \) Moreover,E _k (x,r) is small on average, i.e \(\int_X^{2X} {|E_K (x,r)|^2 dx}<< |D|^{4 + \varepsilon } X^{{5 \mathord{\left/ {\vphantom {5 2}} \right. \kern-0em} 2} + \varepsilon } \) uniformly for \(r<< |D|X^{{3 \mathord{\left/ {\vphantom {3 4}} \right. \kern-0em} 4}} \) .     

An asymptotic formula for the sum of the lengths of the periods of quadratic irrationalities with discriminant

On the basis of B. F. Skubenko's theorem on the uniform distribution of integral points on a hyperboloid with one sheet, one obtains an asymptotic formula for the sum of the lengths of the periods of quadratic irrationalities with discriminant.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 91, pp. 134–144, 1979.     

On the asymptotic behaviour of elliptic problems with periodic data

We study the asymptotic behaviour of the solution of elliptic problems with periodic data when the size of the domain on which the problem is set becomes unbounded. To cite this article: M. Chipot, Y. Xie, C. R. Acad. Sci. Paris, Ser. I 339 (2004).