Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem

Alessandro Avenali ()
Additional contact information
Alessandro Avenali: Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma “La Sapienza,” 00185 Roma, Italy

Operations Research, 2007, vol. 55, issue 5, 932-948

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 [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.

Keywords: mathematics; combinatorics; programming; integer; algorithms; branch and bound; networks/graphs (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0397 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:55:y:2007:i:5:p:932-948

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().