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.
Resolution branch and bound and an application: The maximum weighted stable set problem / Avenali, Alessandro. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - 55:5(2007), pp. 932-948. [10.1287/opre.1070.0397]
Resolution branch and bound and an application: The maximum weighted stable set problem
AVENALI, Alessandro
2007
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.File | Dimensione | Formato | |
---|---|---|---|
VE_2007_11573-144571.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
256.22 kB
Formato
Adobe PDF
|
256.22 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.