| Issue |
RAIRO-Oper. Res.
Volume 40, Number 1, January-March 2006
|
|
|---|---|---|
| Page(s) | 53 - 73 | |
| DOI | https://doi.org/10.1051/ro:2006010 | |
| Published online | 01 July 2006 | |
Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
IBM T. J. Watson research Center, Yorktown Heights, NY 10589, USA; barahon@us.ibm.com ; ladanyi@us.ibm.com
Received:
19
May
2005
Accepted:
8
December
2005
We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach.
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.