Exact and heuristic solution approaches for the Generalized Independent Set Problem

• Published in: Computers & operations research 2024-04, Vol.164, p.106561, Article 106561
• Main Authors: Zheng, Mingming, Hao, Jin-Kao, Wu, Qinghua
• Format: Article
• Language: English
• Subjects: Adaptive local search; Branch and bound; Heuristic; The generalized independent set problem
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2024.106561

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 branch-and-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. •We derive a new upper bound using a Lagrangian relaxation of the GIS problem.•We develop an effective exact algorithm based on the branch-and-bound framework for the GIS.•We propose an adaptive local search procedure jointly considering several neighborhoods.•The exact algorithm can solve 26 more instances to optimality for the first time.