Algorithms for the generalized independent set problem based on a quadratic optimization approach
- Additional Document Info
- View All
© 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.