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

Download
2016
Aksan, Yağmur
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.

Suggestions

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...
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 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 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.