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 algorithmsa construction heuristic and an exact solution methodfor 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.

published proceedings

  • Optimization Letters

author list (cited authors)

  • Hosseinian, S., & Butenko, S.

complete list of authors

  • Hosseinian, Seyedmohammadhossein||Butenko, Sergiy

publication date

  • January 1, 2019 11:11 AM