A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture

Download

index.pdf

Date

2016

Author

Aksan, Yağmur

Metadata

Show full item record

Item Usage Stats

142
views

71
downloads

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 problem instances. In addition to this, the proposed algorithm, BLS-OpenMP-QAP (Breakout Local Search Algorithm with Open Multi-Processing for Quadratic Assignment Problem), makes use of the parallel computation paradigm of the contemporary multi-core architectures using OpenMP programming paradigm. The stagnation-aware search for the (near-)optimal solution of the QAP is executed concurrently on several cores with diversified trajectories while considering the similarity of the already detected local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding-up the fitness evaluations as many as the number of the processors/threads. The BLS-OpenMP-QAP algorithm is executed on 59 problem instances of the QAP library benchmark and the results shows that it is able to solve 57 of the instances exactly. The overall deviation for the algorithm is obtained as 0.019% on the average; therefore, it can be reported to be among the best algorithms in the literature.

Subject Keywords

Quadratic assignment problem., Combinatorial optimization., Software architecture., Computer algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12620104/index.pdf
https://hdl.handle.net/11511/25753

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem Aksan, Yagmur; Dokeroglu, Tansel; Coşar, Ahmet (2017-01-01) 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 permut...
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-...
Converging preferred regions in multi-objective combinatorial optimization problems Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2011) Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting w...
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 NOVEL PARTITIONING METHOD FOR ACCELERATING THE BLOCK CIMMINO ALGORITHM Torun, F. Sukru; Manguoğlu, Murat; Aykanat, Cevdet (2018-01-01) We propose a novel block-row partitioning method in order to improve the convergence rate of the block Cimmino algorithm for solving general sparse linear systems of equations. The convergence rate of the block Cimmino algorithm depends on the orthogonality among the block rows obtained by the partitioning method. The proposed method takes numerical orthogonality among block rows into account by proposing a row inner-product graph model of the coefficient matrix. In the graph partitioning formulation define...

Citation Formats

Y. Aksan, “A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture,” M.S. - Master of Science, Middle East Technical University, 2016.