Exact and Heuristic Solution Approaches for the Generalized Independent Set Problem

The generalized independent set problem (GIS) is a generalization of the classical maximum independent set problem and has various practical applications, such as forest harvesting and image/video processing. In this work, we present highly effective exact and heuristic algorithms for the GIS. In the proposed exact algorithm, a new upper bound on the maximum net benefit of an independent set in a subgraph is derived using a Lagrangian relaxation of a linear integer programming formulation of the GIS problem. This bound is then employed in a combinatorial branchand-bound (B&B) algorithm. To solve larger instances, we propose an adaptive local search procedure which jointly considers several neighborhoods and selects a neighborhood to explore in an adaptive manner at each iteration. Our proposed exact and heuristic algorithms are evaluated on a set of 216 GIS benchmark instances and compared with several state-of-the art algorithms. Computational results indicate that our proposed algorithm competes favorably with the best existing approaches for the GIS. In particular, the exact algorithm is able to attain all known optimal solutions and to solve 26 more instances to optimality for the first time