quadratic assignment problem

Data visualization is a key component of undirected data mining that it transforms data, information, and knowledge into visual view. In this paper, we formulate data visualization problem as a quadratic assignment problem (DV-QAP). The QAP is an NP-Hard problem and has high complexity that it is more acute for data visualization problem because it has intense dependencies among variables and big search space. Therefore, the exact approaches are inefficient to solve DV-QAP and we introduce a new technique called Distributed Self Adaptive Genetic Algorithm with Migration (DSAGAM) that their parameters adjust to increases the exploration and exploitation. This paper focuses on the effect of controlling the migration process and adjusting parameters with respect to the fitness to explore such big search spaces to improve solutions quality. Then we demonstrate the efficiency of the model for a real data set compared with the SGA, SAMGA, IGA and Sammon's mapping approaches.

A lot of real-world problems such as the assignment of special rooms in hospitals, operating room layout, image processing, etc., could be formulated in terms of Quadratic assignment problem. Different exact methods are suggested to solve these problems, but because of the special structure of these problems, by increasing the size of the problem, finding an exact solution become more complicated and even impossible. So, employing meta-heuristic algorithms is inevitable, due to this problem we use optics inspired optimization (OIO) in this paper. The obtained results and its comparison with the solutions of the central library of Quadratic assignment problem (QAPLIB) show that the proposed algorithm can exactly solve small-sized problems with 100% efficiency while the efficiency of medium-to-large size instances is 96%. Accordingly, one can conclude that the proposed OIO has generally high efficiency for solving permutation-based problems.

Construction Site Layout Planning (CSLP) is an important problem because of its impact on time, cost, productivity, and safety of the projects. In this paper, CSLP is formulated by the Quadratic Assignment Problem (QAP). At first, two case studies including equal and un-equal area facilities are solved by the simulated annealing optimization algorithm. Then, the obtained results are compared with the other papers. The comparisons show that the proposed Simulated Annealing (SA) is as efficient as ACO, PSO, CBO, ECBO, WOA, WOA-CBO, and ACO-PA which have been proposed by other papers for the same problems. As a result, the comparisons show that SA is as capable as other meta-heuristics of solving the combinatorial optimization problems like CSLP, while the hardware properties and computational times have been compared. Besides the comparisons, the design of experiments shows the relationship between each SA parameter and the computational time of the algorithm. Also, the history of convergence of the proposed SA indicates the high speed of reaching the optimal solution and the artificial intelligence of the proposed SA.

Quadratic assignment problem (QAP) is a well-known problem in the facility location and layout. It belongs to the NP-complete class. There are many heuristic and meta-heuristic methods, which are presented for QAP in the literature. In this paper, we applied 2-opt, greedy 2-opt, 3-opt, greedy 3-opt, and VNZ as heuristic methods and tabu search (TS), simulated annealing, and particle swarm optimization as meta-heuristic methods for the QAP. This research is dedicated to compare the relative percentage deviation of these solution qualities from the best known solution which is introduced in QAPLIB. Furthermore, a tuning method is applied for meta-heuristic parameters. Results indicate that TS is the best in 31% of QAPs, and the IFLS method, which is in the literature, is the best in 58 % of QAPs; these two methods are the same in 11% of test problems. Also, TS has a better computational time among heuristic and meta-heuristic methods.

We consider a generalization of the classical quadratic assignment problem, where coordinates of locations are uncertain and only upper and lower bounds are known for each coordinate. We develop a mixed integer linear programming model as a robust counterpart of the proposed uncertain model. A key challenge is that, since the uncertain model involves nonlinear objective function of the uncertain data, classical robust optimization approaches cannot be applied directly to construct its robust counterpart. We exploit the problem structure to develop exact solution methods and present some computational results.

Assigning facilities to locations is one of the important problems, which significantly is influence in transportation cost reduction. In this study, we solve quadratic assignment problem (QAP), using a meta-heuristic algorithm with deterministic tasks and equality in facilities and location number. It should be noted that any facility must be assign to only one location. In this paper, first of all, we have been described exact methods and heuristics, which are able to solve QAP; then we have been applied a meta-heuristic algorithm for it. QAP is a difficult problem and is in NP-hard class, so we have been used honey bee mating optimization (HBMO) algorithm to solve it.This method is new and have been applied and improved NP-hard problems. It’s a hybrid algorithm from Honey-Bee Mating system, simulated annealing and genetic algorithm.