Quadratic Assignment Problem
We have recently showed that the Microarray Placement Problem is an instance of the Quadratic Assignment Problem (QAP) [1]. Here are some QAP instances derived from our models and the best solutions computed with QAP solvers.
The problem instances were derived from small artificial microarrays containing between 36 and 144 probes. These probes must be assigned to specific locations of the chip (spots), whose dimensions range from 6x6 to 12x12. Once the assignment is made, there are two models that evaluate the quality of the layout: border length and conflict index (these models are somewhat correlated, i.e. a good layout has both low border length and low conflict indices).
In our formulations, the flow matrix contains the Euclidean distance between the spots, while the distance matrix contains the (weighted) Hamming distance between the probe embeddings. The chips available here are square in shape and thus, for every solution, there are another seven symmetrical solutions.
Because of the large number of probes on industrial microarrays (up to 1.3 million probes), it is not feasible to use any QAP method to design an entire microarray chip. However, it is certainly possible to design or improve small sub-regions of a chip. Since the instances that we work on are only a small part of the whole problem, we are more interested in methods that can solve a QAP rather quickly (in a few minutes). Nonetheless, we also report here results obtained with other time-consuming approaches.
Note that the results that appeared in [1] are averages over three runs on a set of ten random files uniformely generated (the files available here are only the first file of each set).
File Formats
Problems and solutions are available as plain text files with the formats used by QAPLIB. The format of the problem file is:
A
B
where n is the size of the instance, A and B are flow and distance matrices, respectively. The format of the solution file is:
p
where n gives the size of the instance, sol is the objective function value and p is the corresponding permutation.
Problem Instances and Solutions
The results obtained with GRASP with Path Relinking (GRASP-PR) [3] used default parameters (32 iteractions, alpha = beta = 0.5) and finished in less than 5 minutes each.
The solutions found with RTL-1 [4] and RTL-2 [5] were reported by Dr. Peter Hahn, with running times ranging from 6.7 to 29.2 hours on a Dell 7150 733 MHz Itanium CPU.
Chris MacPhee reported the best solutions so far (obtained by a QAP solver), using GATS [6], a hybrid genetic / tabu search algorithm, with running times ranging from 84 seconds to 479 hours.
This page will be updated as soon as we hear about better solutions.
To download all problem instances and GRASP-PR solutions, click here.
Border Length Minimization
| Chip size | Name | Dimension (n) | Best known solution | Other solutions |
| 6x6 | RAND-S-6x6-36-25-AFFY-00_rand_rand_bl | 36 | 3,296(GATS) | 3,304(RTL-2) 3,304(RTL-2) 3,352(GRASP-PR) |
| 7x7 | RAND-S-7x7-49-25-AFFY-00_rand_rand_bl | 49 | 4,564(GATS) | 4,580(RTL-1) 4,660(GRASP-PR) |
| 8x8 | RAND-S-8x8-64-25-AFFY-00_rand_rand_bl | 64 | 6,048(GATS) | 6,080(RTL-1) 6,200(GRASP-PR) |
| 9x9 | RAND-S-9x9-81-25-AFFY-00_rand_rand_bl | 81 | 7,644(GATS) | 7,900(GRASP-PR) |
| 10x10 | RAND-S-10x10-100-25-AFFY-00_rand_rand_bl | 100 | 9,432(GATS) | 9,684(GRASP-PR) |
| 11x11 | RAND-S-11x11-121-25-AFFY-00_rand_rand_bl | 121 | 11,640(GATS) | 12,032(GRASP-PR) |
| 12x12 | RAND-S-12x12-144-25-AFFY-00_rand_rand_bl | 144 | 13,832(GATS) | 14,196(GRASP-PR) |
Conflict Index Minimization
| Chip size | Name | Dimension (n) | Best known solution | Other solutions |
| 6x6 | RAND-S-6x6-36-25-AFFY-00_rand_rand_ci | 36 | 169,016,907(GATS) | 169,925,219(GRASP-PR) |
| 7x7 | RAND-S-7x7-49-25-AFFY-00_rand_rand_ci | 49 | 237,077,377(GATS) | 238,859,844(GRASP-PR) |
| 8x8 | RAND-S-8x8-64-25-AFFY-00_rand_rand_ci | 64 | 326,696,412(GATS) | 327,770,071(GRASP-PR) |
| 9x9 | RAND-S-9x9-81-25-AFFY-00_rand_rand_ci | 81 | 428,682,120(GATS) | 434,317,170(GRASP-PR) |
| 10x10 | RAND-S-10x10-100-25-AFFY-00_rand_rand_ci | 100 | 525,401,670(GATS) | 532,573,788(GRASP-PR) |
| 11x11 | RAND-S-11x11-121-25-AFFY-00_rand_rand_ci | 121 | 658,317,466(GATS) | 664,137,090(GRASP-PR) |
| 12x12 | RAND-S-12x12-144-25-AFFY-00_rand_rand_ci | 144 | 803,379,686(GATS) | 813,127,758(GRASP-PR) |
Contact
For more information, or to report a better solution, please contact Sergio A. de Carvalho Jr.
References
[1] de Carvalho Jr., S.A., Rahmann, S. (2006): Microarray Layout as a quadratic assignment problem. In D. Hudson et al., editors, Proceedings of the German Conference on Bioinformatics (GCB), volume P-83 of Lecture Notes in Informatics, pages 11-20. Gesellschaft für Informatik. Preview (PDF).
[2] de Carvalho Jr., S.A., Rahmann, S. (2006): Microarray Layout and the Quadratic Assignment Problem. (poster) 14th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB), Fortaleza, Brazil. Preview (PDF).
[3] Oliveira, C.A.S., Pardalos, P.M. and Resende, M.G.C. (2004): GRASP with Path-relinking for the Quadratic Assignment Problem. In Ribeiro, C.C. and Martins, S.L. (eds.), Efficient and Experimental Algorithms, LNCS, 3059, 356-368, Springer-Verlag.
[4] Hahn, P., Grant, T. and Hall, N. (1998): A Branch-and-bound Algorithm for the Quadratic Assignment Problem Based on the Hungarian Method. European Journal of Operational Research, 108, 629-640.
[5] Adams, W., Guignard, M., Hahn, P. and Hightower, W.: A Level-2 Reformulation Linearization Technique Lower Bound for the Quadratic Assignment Problem. To appear in the European Journal of Operational Research.
[6] Rodriguez, J.M., MacPhee, F.C., Bonham, D.J., Horton, J.D. and Bhavsar, V.C. (2004): Best Permutations for the Dynamic Plant Layout Problem. In Dasgupta, A.R., Iyengar, S.S., and Bhatt, H.S. (Eds.): Proceedings of the 12th International Conference on Advances in Computing and Communications (ADCOM 2004), Allied Publishers Pvt. Ltd., New Delhi Ahmedabad, India, 15-18 Dec., ISBN 81-7764-717-2, pp.173-178.