Breakout Local Search for Heaviest Subgraph Problem

This paper presents a breakout local search (BLS) heuristic algorithm for solving the heaviest k-subgraph problem - a combinatorial optimization graph problem with various practical applications. BLS explores the search space by alternating iteratively between local search phase and dedicated perturbation strategies. Focusing on the perturbation phase, the algorithm determines its jump magnitude and perturbation type according to the search history to obtain the most appropriate degree of diversification. Computational experiments are performed on a number of large random graphs. The experimental evaluations show that the results obtained by BLS are comparable to, and in most cases superior to, those of the current state-of-the-art approaches.