A branch-and-price approach for the maximum weight independent set problem

A branch-and-price approach for the maximum weight independent set problem

0.00 Avg rating0 Votes
Article ID: iaor20063601
Country: United States
Volume: 46
Issue: 4
Start Page Number: 198
End Page Number: 205
Publication Date: Dec 2005
Journal: Networks
Authors: , , ,
Keywords: sets, combinatorial optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.