Implementation of iterative local search (ILS) for the quadratic assignment problem
The quadratic assignment problem (QAP) is one of the hardest NP-hard problems and problems with a dimension of 20 or more can be difficult to solve using exact methods. The QAP has a set of facilities and a set of locations. The goal is to assign each facility to a location such that the product of the flow between pairs of facilities and the distance between them are minimized. Sometimes there is also a cost associated with assigning a facility to a location. In this work, I solve the QAP using a population based iterative local search with open source code in C++. Results show that the code is able to solve all nug instances to optimality, thereby proving that the algorithm is capable of solving larger problems for which optimum solutions are not known.
Code (1)
Similar Papers 제목 키워드 기반
Efficient and Robust Shape Correspondence via Sparsity-Enforced Quadratic Assignment
In this work, we introduce a novel local pairwise descriptor and then develop a simple, effective iterative method to solve the resulting quadratic assignment through sparsity control for shape correspondence between two…
A Genetic Algorithm Meta-Heuristic for a Generalized Quadratic Assignment Problem
The generalized quadratic assignment problem (GQAP) is one of the hardest problems to solve in the operations research area. The GQAP addressed in this work is defined as the task of minimizing the assignment and transpo…
Q-Match: Iterative Shape Matching via Quantum Annealing
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) that becomes infeasible for shapes with high sampling density. A promising research direction is to tackle such quadratic o…
Continuous-time iterative linear-quadratic regulator
We present a continuous-time equivalent to the well-known iterative linear-quadratic algorithm including an implementation of a backtracking line-search policy and a novel regularization approach based on the necessary c…
Numerical IntegrationMulti-swarm PSO algorithm for the Quadratic Assignment Problem: a massive parallel implementation on the OpenCL platform
This paper presents a multi-swarm PSO algorithm for the Quadratic Assignment Problem (QAP) implemented on OpenCL platform. Our work was motivated by results of time efficiency tests performed for single-swarm algorithm i…