×

Generating QAP instances with known optimum solution and additively decomposable cost function. (English) Zbl 1334.90141

Summary: Quadratic assignment problems (QAPs) is a NP-hard combinatorial optimization problem. QAPs are often used to compare the performance of meta-heuristics. In this paper, we propose a QAP problem instance generator that can be used for benchmarking for heuristic algorithms. Our QAP generator combines small size QAPs with known optimum solution into a larger size QAP instance. We call these instances composite QAPs (cQAPs), and we show that the cost function of cQAPs is additively decomposable. We give mild conditions for which a cQAP instance has known optimum solution. We generate cQAP instances using uniform distributions with different bounds for the component QAPs and for the rest of the cQAP elements. Numerical and analytical techniques that measure the difficulty of the cQAP instances in comparison with other QAPs from the literature are introduced. These methods point out that some cQAP instances are difficult for local search with many local optimum of various values, low epistasis and non-trivial asymptotic behaviour.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

QAPLIB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Angel E, Zissimopoulos V (2002) On the hardness of the quadratic assignment problem with metaheuristics. J Heuristics 8(4):399-414 · doi:10.1023/A:1015454612213
[2] Burkard RE, Çela E, Demidenko VM, Metelski NN, Woeginger GJ (1997) Perspectives of easy and hard cases of the quadratic assignment problems. Technical report, Institute of Mathematics Technical University Graz, Austria
[3] Burkard RE, Karisch SE, Rendl F (1997) QAPLIB a quadratic assignment problem library. J Glob Optim 10:391-403 · Zbl 0884.90116 · doi:10.1023/A:1008293323270
[4] Çela E (1998) The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers, Dordrecht · Zbl 0909.90226 · doi:10.1007/978-1-4757-2787-6
[5] Drezner Z, Hahn PM, Taillard ÉD (2005) Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann Oper Res 139(1):65-94 · Zbl 1091.90033 · doi:10.1007/s10479-005-3444-z
[6] Drugan MM (2013) Instance generator for the quadratic assignment problem with additively decomposable cost function. In: IEEE Congress on Evolutionary Computation (CEC’13), IEEE, pp 2086-2093 · Zbl 1103.90058
[7] Erdogan G, Tansel B (2011) Two classes of quadratic assignment problems that are solvable as linear assignment problems. Discret Optim 8(3):446-451 · Zbl 1233.90239
[8] Garnier J, Kallel L (2001) Efficiency of local search with multiple local optima. SIAM J Discret Math 15(1):122-141 · Zbl 0992.68039 · doi:10.1137/S0895480199355225
[9] Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J Appl Math 10:305-331 · Zbl 0118.15101 · doi:10.1137/0110022
[10] Hadley SW, Rendl F, Wolkowicz H (1992) A new lower bound via projection for the quadratic assignment problem. Math Oper Res 17:727-739 · Zbl 0767.90059 · doi:10.1287/moor.17.3.727
[11] Krokhmal P, Pardalos P (2009) Random assignment problems. Eur J Oper Res 194(1):1-17 · Zbl 1179.90212 · doi:10.1016/j.ejor.2007.11.062
[12] Li Y, Pardalos PM, Resende MGC (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos P, Wolkowicz H (eds) Quadratic assignment and related problems, volume 16 of DIMACS Series, in Discrete Mathematics and Theoretical Computer Science, pp 237-261 · Zbl 0817.90057
[13] Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T (2007) An analytical survey for the quadratic assignment problem. Eur J Oper Res 176(2):657-690 · Zbl 1103.90058 · doi:10.1016/j.ejor.2005.09.032
[14] Marzetta A, Brüngger A (1999) A dynamic-programming bound for the quadratic assignment problem. In COCOON’99, volume LNCS 1627, Springer, Berlin, pp 339-348 · Zbl 0992.68039
[15] Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evol Comput 4(4):337-352 · doi:10.1109/4235.887234
[16] Palubeckis G (2000) An algorithm for construction of test cases for the quadratic assignment problem. Informatica Lith Acad Sci 11(3):281-296 · Zbl 0983.90034
[17] Puglierin F, Drugan MM, Wiering M (2013) Bandit-inspired memetic algorithms for solving quadratic assignment problems. In IEEE Congress on, Evolutionary Computation (CEC’13), pp 2078-2085 · Zbl 0983.90034
[18] Siarry P, Michalewicz Z (eds) (2008) Advances in metaheuristics for hard optimization. Springer, Berlin · Zbl 1130.90006
[19] Stützle T, Fernandes S (2004) New benchmark instances for the qap and the experimental analysis of algorithms. In EvoCOP, pp 199-209 · Zbl 1177.90424
[20] Taillard ÉD (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17:443-455 · doi:10.1016/S0167-8191(05)80147-4
[21] Taillard ÉD (1995) Comparison of iterative searches for the quadratic assignment problem. Locat Sci 3:87-105 · Zbl 0916.90235 · doi:10.1016/0966-8349(95)00008-6
[22] Wayne A (1946) Inequalities and inversions of order. Scripta Mathematica 12(2):164-169
[23] Wright SE (2012) New linearizations of quadratic assignment problems. Comput Oper Res 39(11):2858-2866 · Zbl 1251.90293 · doi:10.1016/j.cor.2012.02.017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.