The features of using a brute force algorithm for solving a quadratic assignment problem

Aye Min Thike, S.A. Lupin, S.A. Balabaev

Abstract


The brute force algorithm of the variants is a universal method for solving discrete optimization problems, which provides finding all possible combinations of parameters corresponding to the extremum of the criterion function. The main disadvantage of the algorithm is its high computational complexity, which prevents its use for solving practical problems of large size. The article discusses some methods for reducing its computational complexity when solving the quadratic assignment problem, which do not lead to loss of accuracy. In addition to the traditional approach based on parallelization of resource-intensive computations, methods to accelerate the process of generating variants and limiting their number have been investigated. The results of computational experiments confirm the effectiveness of the proposed approach and its applicability in sequential and parallel implementations of the algorithm. The sequential application was obtained more than 2000x acceleration of calculations, and a multithreaded application provides an additional 2.3x performance boost when running on a quad-core processor.

Full Text:

PDF (Russian)

References


Mario Francisco, Silvana Revollar, Pastora Vega, Rosalba Lamanna,“A Comparative study of Deterministic and Stochastic Optimization methods for Integrated Design of Processes”, IFAC Proceedings Volumes, vol.38, Iss.1, pp. 335-340, 2005.

Wendly Saintil, “The Role of Optimization Algorithms in Improving Efficiency and Decision-Making”, [Online]. Available: https://medium.com/codex/the-role-of-optimization-algorithms-in-improving-efficiency-and-decision-making-d61df38ba6bc.

Thomas Weise, “Metaheuristic Optimization Algorithms”, An Introduction to Optimzation Algorithms, pp. 49-150, 26 December 2020.

Aye Min Thike, Sergey Lupin,Yuriy Vagapov, “Implementation of Brute Force Algorithm for Topology Optimisation of Wireless Networks”, 2016 International Conference for Students on Applied Engineering (ICSAE), 20 - 21 October 2016, Newcastle upon Tyne, UK. C. 264-268.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction of Algorithms”, ISBN 978-0-262-03384-8, 31 July 2009.

Madeline Corman, “Memoization”, [Online]. Available: https://medium.com/@madelinecorman/memoization-96ab60464bd2.

M. Fatih Tasgetiren, Quan-Ke Pan, P. N. Suganthan, Ikbal Ece Dizbay, “Metaheuristic algorithms for the quadratic assignment problem”, 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS), pp. 131-137, 16-19 April 2013, Singapore.

Milan Vaško, Marián Handrik, Alžbeta Sapietová, Jana Handriková, “Parallelization of computational algorithms for optimization problems with high time consumption”, MATEC Web of Conferences 157, pp. 1-10, 2018.

Elena Castellani. “On the meaning of symmetry breaking”, Symmetries in Physics: Philosophical Reflections, Cambridge University Press, 2003.

Ай Мин Тайк, С.А. Лупин, Мин Тху Кхаинг, “Методы повышения эффективности алгоритма полного перебора на примере решения задачи о неограниченном ранце”, International Journal of Open Information Technologies, Vol. 11, No 5 (2023), pp.41 -46.

Santosh Kumar Sahu, Manish Pandey, “Hybrid Ant System Algorithm for Solving Quadratic Assignment Problmes”, (IJCSIT) International Journal of Computer Science and Information Technologies, Vol.5, pp. 5950-5956, 2014.

Tansel Dokeroglu, Ahmet Cosar, Ender Sevinc, “Artificial bee colony optimization for the quadratic assignment problem”, Applied Soft Computing (JoCAI), March 2019.

Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, Tania Querido, “A survey for the quadratic assignment problem”, European Journal of Operational Research 176 (2007),pp. 657-690, 27 December 2005.

Xin (Bruce) Wu, Jiawei Lu, Shengnan Wu, Xuesong (Simon) Zhou, “Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem”, Transportation Research Part B: Methodological, Vol – 152, pp 140-179, October 2021.

Clayton W. Commander, “A Survey of the Quadratic Assignment Problem, with Applications”, Morehead Electronic Journal of Applicable Mathematics, 2005.

Cemre Cubukcuoglu, Pirouz Nourian, M. Fatih Tasgetiren, I. Sevil Sariyildiz, Shervin Azadi, “Hospital layout design renovation as a Quadratic Assignment Problem with geodesic distances”, Journal of Building Engineering 44(2021).

Ekrem Duman, Ilhan Or, “The quadratic assignment problem in the context of the printed circuit board assembly process”, Computers & Operations Research 34 (2007), pp-163-179.

Sharifah Shuthairah Syed-Abdullah, Syariza Abdul-Rahman, Aida Mauziah Benjamin, Antoni Wibowo, Ku-Ruhana Ku-Mahamud, “Solving Quadratic Assignment Problem with Fixed Assignment (QAPFA) using Branch and Bound Approach”, 4th International Conference on Operational Research (InteriOR), 2018.

Danny Munera, Daniel Diaz, Salvador Abreu, “Solving the Quadratic Assignment Problem with Cooperative Parallel Extremal Optimization”,16th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016, March 2016, Porto, Portugal.

H. Azarbonyad, R. Babazadeh, “A Genetic Algorithm for solving Quadratic Assignment Problem (QAP)”, 5th International Conference of Iranian Operations Research Society (ICIORS), Tabriz, Iran, 2012.

Kambiz Shojaee Ghandeshtani, Nima Mollai, Seyed Mohammad Hosein Seyedkashi, Mohammad Mohsen Neshati, “New Simulated Annealing Algorithm for Quadratic Assignment Problem”, 4th International Conference on Advanced Engineering Computing and Applications in Sciences, 2010.

Alfonsas Misevicius, “A Tabu Search Algorithm for the Quadratic Assignment Problem”, Computational Optimization and Applications, January 2005.

Omar Abdelkafi, Bilel Derbel, Arnaud Liefooghe, “A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem”, IEEE Congress on Evolutionary Computation, IEEE CEC 2019, Jun 2019, Wellington, New Zealand.

Hossein Jafari, Abbas Sheykhan, “Using a New Algorithm to Improve the Search Answer in Quadratic Assignment Problem (QAP)”, International Journal of Research in Industrial Engineering, Vol. 10, No. 2 (2021), 28 May 2021.

OpenMP. [Online]. Available: https://www.openmp.org/.

G. W. Graves and A. B. Whinston, “An Algorithm for the Quadratic Assignment Problem”, Management Science, Vol. 16, No. 7, Theory Series (Mar., 1970), pp. 453-471.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162