To search, Click below search items.


All Published Papers Search Service


Hybrid algorithms for Minimum Base Problem


Zbigniew Kokosinski


Vol. 20  No. 10  pp. 158-162


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.


simulated annealing, tabu search, hybrid algorithm, minimum base problem