A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem

Date

2017-01-01

Author

Aksan, Yagmur
Dokeroglu, Tansel
Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

176
views

0
downloads

The Quadratic Assignment Problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems. Circuit-layout design, transportation/traffic engineering, and assigning gates to airplanes are some of the interesting applications of the QAP. In this study, we introduce an enhanced version of a recent local search heuristic, Breakout Local Search Algorithm (BLS), by using the Levenshtein Distance metric for checking the similarity of the new starting points to previously explored QAP permutations. The similarity-checking process prevents the local search algorithm, BLS, from getting stuck in already-explored areas. In addition, the proposed BLS Algorithm (BLS-OpenMP) incorporates multi-threaded computation using OpenMP. The stagnation-aware search for the optimal solutions of the QAP is executed concurrently on several cores with diversified trajectories while considering their similarity to already-discovered local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding up the fitness evaluations linearly with number of processors/threads. BLS-OpenMP has been tested on the hardest 59 problem instances of the QAPLIB, and it obtained 57 of the best known results. The overall deviation of the achieved solutions from the best known results is 0.019% on average, which is a significant improvement compared with state-of-the-art algorithms.

Subject Keywords

Quadratic assignment problem, Breakout local search, OpenMP, Optimization, Levenshtein distance

URI

https://hdl.handle.net/11511/30536

Journal

COMPUTERS & INDUSTRIAL ENGINEERING

DOI

https://doi.org/10.1016/j.cie.2016.11.023

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture Aksan, Yağmur; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2016) The quadratic assignment problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems with its several real life applications. Layout design, scheduling, and assigning gates to planes at an airport are some of the interesting applications of the QAP. In this thesis, we improve the talents of a recent local search heuristic Breakout Local Search Algorithm (BLS) by using adapted Levenshtein Distance metric for similarity checking of the previously explored permutations of the QAP p...
A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem Tosun, Umut; Dokeroglu, Tansel; Coşar, Ahmet (2013-07-01) The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-...
A strong conic quadratic reformulation for machine-job assignment with controllable processing times Akturk, M. Selim; Atamturk, Alper; Gürel, Sinan (2009-05-01) we describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation.
A GPU-accelerated adaptive discontinuous Galerkin method for level set equation KARAKUS, A.; WARBURTON, T.; AKSEL, MEHMET HALUK; Sert, Cüneyt (2016-01-02) This paper presents a GPU-accelerated nodal discontinuous Galerkin method for the solution of two- and three-dimensional level set (LS) equation on unstructured adaptive meshes. Using adaptive mesh refinement, computations are localised mostly near the interface location to reduce the computational cost. Small global time step size resulting from the local adaptivity is avoided by local time-stepping based on a multi-rate Adams-Bashforth scheme. Platform independence of the solver is achieved with an extens...
A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem Dokeroglu, Tansel; Coşar, Ahmet (2016-06-01) Hyper-heuristics introduce novel approaches for solving challenging combinatorial optimization problems by operating over a set of low level (meta)-heuristics. This is achieved by an evolutionary selection mechanism that controls and combines the strengths of the low level (meta) -heuristics. In this study, we propose a high-performance MultiStart Hyper-heuristic algorithm (MSH-QAP) on the grid for the solution of the Quadratic Assignment Problem (QAP). MSH-QAP algorithm makes use of state-of:the-art (meta)...

Citation Formats

Y. Aksan, T. Dokeroglu, and A. Coşar, “A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem,” COMPUTERS & INDUSTRIAL ENGINEERING, pp. 105–115, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30536.