Resolution branch and bound and an application: the maximum weighted stable set problem

Resolution branch and bound and an application: the maximum weighted stable set problem

0.00 Avg rating0 Votes
Article ID: iaor20083319
Country: United States
Volume: 55
Issue: 5
Start Page Number: 932
End Page Number: 948
Publication Date: Sep 2007
Journal: Operations Research
Authors:
Keywords: programming: branch and bound, networks, sets
Abstract:

We propose a new resolution algorithm, called resolution branch and bound (RBB), where a branch-and-bound scheme is empowered by exploiting the information contained in a family of closed subproblems, collected by a full resolution phase. In particular, we use this information to define a new branching rule that seems able to reduce the risk of incurring inappropriate branchings. We apply RBB and the proposed branching rule to the maximum weighted stable set problem, as its features allow us to speed up a time-consuming step in the full resolution phase. To compute upper bounds, we generalize to the weighted case the polynomial time procedure provided by Mannino and Sassano for the unweighted case. Computational results validate the effectiveness of the provided branching rule and the good performance of RBB on many DIMACS benchmarks.

Reviews

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