Resolution branch and bound and an application: The maximum weighted stable set problem
成果类型：
Article
署名作者：
Avenali, Alessandro
署名单位：
Sapienza University Rome
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0397
发表日期：
2007
页码：
932-948
关键词：
摘要：
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 [Mannino, C., A. Sassano. 1994. An exact algorithm for the maximum stable set problem. Computational Optim. Appl. 3 243-258] for the unweighted case. Computational results validate the effectiveness of the provided branching rule and the good performance of RBB on many DIMACS benchmarks.