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

abstract

• 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.

authors

• Butenko, Sergiy

published proceedings

• OPTIMIZATION LETTERS

author list (cited authors)

• Hosseinian, S., & Butenko, S.

citation count

• 3

complete list of authors

• Hosseinian, Seyedmohammadhossein||Butenko, Sergiy

publication date

• September 2019

publisher

• Springer Nature  Publisher

published in

• Optimization Letters  Journal

keywords

• Combinatorial Branch-and-bound
• Construction Heuristic
• Generalized Independent Set Problem
• Quadratic Optimization

Digital Object Identifier (DOI)

• 10.1007/s11590-019-01418-9

start page

• 1211

end page

• 1222

volume

• 13

issue

• 6

URL

• http://dx.doi.org/10.1007/s11590-019-01418-9