Classes of quadratic assignment problem instances: isomorphism and difficulty measure in a statistical approach

Nair Maria Maia de Abreu

Tania Maia Querido

Paulo Oswaldo Boaventura Netto

Elisabeth Ferreira Gouvea

1 -Introduction: The Quadratic Assignment Problem (QAP) is still one of the most difficult challenge in the combinatorial optimization area. For this reason, considerable attention is given to the complexity theory focusing the features of a particular QAP instance. A complete survey and applications of the QAP can be found in [3].

In this work we define a novel class of QAP instances that leads to the same linearization. Besides a discussion about isomorphism, we will present a difficulty measure in a statistical basis, which approach was partially suggested by Graves and Whinston in the early 70’s and remained an open question so far.

2 - QAP partition into classes of relative instances: The QAP can be stated as:

z = Min for 1 i < j  n, (2.1)

where is the set of permutations in {1, 2, …, n} and the coefficients of the objective function are defined by the vectors F= [] and D = [], with N = elements. An instance, represented by the pair of vectors (F,D) will be denoted by QAP(F,D) and = F will be the matrix consisting of the coefficients in 2.1. Ranking F and D elements in non-increasing and non-decreasing order, respectively, we obtain () with coefficient matrix =. We will designate Relclass() the family of relative instances {QAP(F,D) / =}. A particular feature of this set lies on the fact that instances in Relclass() induce the same pair (). Thus, we can think of the QAP as: QAP = Relclass.

3 - Costs average and variance for QAP(F,D): The large space of local optimums for the QAP instances suggests the use of the average and variance as parameters to establish the particular difficulty an instance reveals. Many researchers have been ranking the problem hardness or introduced algorithms based on a variance approach, such as in [5] and [6]. Graves and Whinston [4] indicated how the variance of QAP solutions could be determined. However, up to this date, a polynomial expression for this variance was not developed.

Programa de Engenharia de Produção, COPPE/UFRJ

CEFET-RJ

e-mails: {boaventu, nair, bgouvea}@pep.ufrj.br;

Consider S .The average of the costs for QAP(F,D) is = , over [4], [1], [5]. Seeking a cost variance parameter, we first decompose , and define , where k = 0, 1, 2 and . Thus, we have the variance expression for the QAP in O() as stated in Theorem 3.1.

Theorem 3.1 - ,

where: , and

.

4 - Variance applications: Verifyingisomorphism in QAP instances is a hard task inducing to the analysis of the n! possibilities. Firstly, the study of variance costs leads to isomorphism of QAP in the sense that given two isomorphic instances and in Relclass(), they will have the same set of feasible solutions and consequently . In practice, can be view as an invariant for the instances isomorphism study, pointing out non-isomorphic instances. The instances Chr12a and Chr12b, available at the QAPLIB [2] are suitable examples of instances sharing the same Relclass(). However, these instances have the respective standard deviations 4413.99 and 4269.89, characterizing non-isomorphic instances.

A second application concerns to a new statistical approach that shall guide this combinatorial subject to some more generic and sensible difficulty measure than the flow dominance (FD(F)) used by Mautor and Roucairol [5]. We define as solutions deviation factor SDF(Z) = . The SDF(z) is able to indicate harder and easier versions in , while FD(F) is not because it is constant in this family. Finally, we suggest the use of variance as a decision parameter on a most suitable procedure to solve the problem or even evaluate the current value obtained by a given heuristic in optimization problems.

References

1. E. Angel and V. Zissimopoulos, On the quality of local search for the quadratic assignment problem, Discrete Appl. Math. 82 (1998), 15-25.

2. R.E. Burkard, S.E.Karisch and F. Rendl, QAPLIB - A quadratic assignment problem library, rep. 287 cdldo-41, Technische Universitat, Graz (1994).

3. E. Çela, The quadratic assignment problem: theory and algorithm, in D.Z. Du and P.Pardalos (Editors), Kluwer Academic Publishers (1998).

4. G.W. Graves and A.B. Whinston, An algorithm for the quadratic assignment problem, Management Science, v.17, n.7, (1970).

5. T. Mautor and C. Roucairol, Difficulties of exact methods for solving the quadratic assignment problem in P. Pardalos and H Wolkowicz (Editors), Quadratic Assignment and Related Problems, DIMACS Series in Discrete Math. Theoret. Comput. Sci., vol.16, AMS, Providence, (1994).

6. P. Pardalos, K.G. Ramakrishnan, M.G.C. Resende and Y. Li, Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem, SIAM J. Optim. 7,1,(1997)280-294.