A branch-and-cut algorithm for the maximum cardinality stable set problem

A branch-and-cut algorithm for the maximum cardinality stable set problem

0.00 Avg rating0 Votes
Article ID: iaor20022959
Country: Netherlands
Volume: 28
Issue: 2
Start Page Number: 63
End Page Number: 74
Publication Date: Mar 2001
Journal: Operations Research Letters
Authors: ,
Keywords: programming: integer, sets
Abstract:

We propose a branch-and-cut algorithm for the Maximum Cardinality Stable Set problem. Rank constraints of general structure are generated by executing clique separation algorithms on a modified graph obtained with edge projections. A branching scheme exploiting the available inequalities is also introduced. A computational experience on the DIMACS benchmark graphs validates the effectiveness of the approach.

Reviews

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