Premium
A branch‐and‐price approach for the maximum weight independent set problem
Author(s) -
Warrier Deepak,
Wilhelm Wilbert E.,
Warren Jeffrey S.,
Hicks Illya V.
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20088
Subject(s) - computer science , vertex (graph theory) , mathematical optimization , combinatorial optimization , graph , set (abstract data type) , theoretical computer science , mathematics , algorithm , programming language
The maximum weight‐independent set problem (MWISP) is one of the most well‐known and well‐studied problems in combinatorial optimization. This article presents a novel approach to solve MWISP exactly by decomposing the original graph into vertex‐induced subgraphs. The approach solves MWISP for the original graph by solving MWISP on the subgraphs to generate columns for a branch‐and‐price framework. The authors investigate different implementation techniques that can be associated with the approach, and offer computational results to identify the strengths and weaknesses of each implementation technique. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 198–209 2005