Algorithms for the generalized independent set problem based on a quadratic optimization approach Academic Article uri icon


  • © 2019, Springer-Verlag GmbH Germany, part of Springer Nature. This paper presents two algorithms—a construction heuristic and an exact solution method—for the generalized independent set problem. Both methods take advantage of a nonlinear formulation of this problem and are based on optimization of a quadratic function over a hypersphere. Heuristic solutions are constructed by exploring stationary points of a surrogate problem of this form. The exact method is a combinatorial branch-and-bound algorithm that uses a spherical relaxation of the original feasible region in its pruning subroutine. We show competence of the proposed methods through computational experiments on benchmark instances.

author list (cited authors)

  • Hosseinian, S., & Butenko, S.

citation count

  • 3

publication date

  • September 2019