Hybrid algorithms for minimum base problem
Authors:
- Zbigniew Kokosiński
Abstract
In this paper we present two hybrid algorithms for approximate solving of Minimum Base Problem (MBP) which is known to be NP-complete [5]. In both algorithms metaheuristic search for a solution of size k is combined with a relaxation mechanism which triggers new metaheuristic search for a solution with incremented size and another mechanism which helps to remove possible solution redundancy. Depending on the outcome of the first step of the hybrid algorithm the result may be either accepted as a final solution or used as a starting point for the second search step. The search is continued until a feasible base is found. Then, the hybrid algorithms tries to remove solution redundancy (if it exists) by using one of the two mechanisms. The new algorithms has been implemented and tested on a collection of random binary matrices as problem instances. In all cases the search space is composed of combinations of matrix columns satisfying specific problem requirements. The solver application contains SA and TS metaheuristics as its basic components. The test results are reported in terms of solution quality and computation time. A influence of the final reduction step is investigated. Some conclusions resulting from the computer experiments are derived.
- Record ID
- CUT44301c4f83c9486e86cc2c11e1f9b90b
- Publication categories
- ;
- Author
- Journal series
- International Journal of Computer Science and Network Security, ISSN 1738-7906
- Issue year
- 2020
- Vol
- 20
- No
- 10
- Pages
- 158-162
- Other elements of collation
- tab.; Bibliografia (na s.) - 162; Bibliografia (liczba pozycji) - 8; Oznaczenie streszczenia - Summ.; Numeracja w czasopiśmie - Vol. 20, No. 10
- Keywords in English
- simulated annealing, tabu search, hybrid algorithm, minimum base problem
- DOI
- DOI:10.22937/IJCSNS.2020.20.10.21 Opening in a new tab
- URL
- http://search.ijcsns.org/02_search/02_search_03.php?number=202010021 Opening in a new tab
- Language
- eng (en) English
- License
- Score (nominal)
- 20
- Publication indicators
- = 1
- Citation count
- 1
- Additional fields
- Indeksowana w: Web of Science
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUT44301c4f83c9486e86cc2c11e1f9b90b/
- URN
urn:pkr-prod:CUT44301c4f83c9486e86cc2c11e1f9b90b
* presented citation count is obtained through Internet information analysis, and it is close to the number calculated by the Publish or PerishOpening in a new tab system.