A Branch and Cut solver for the maximum stable set problem |
| |
Authors: | Steffen Rebennack Marcus Oswald Dirk Oliver Theis Hanna Seitz Gerhard Reinelt Panos M Pardalos |
| |
Institution: | (3) Center of Applied Optimization, University of Florida, Gainesville, USA; |
| |
Abstract: | This paper deals with the cutting-plane approach to the maximum stable set problem. We provide theoretical results regarding
the facet-defining property of inequalities obtained by a known project-and-lift-style separation method called edge-projection,
and its variants. An implementation of a Branch and Cut algorithm is described, which uses edge-projection and two other separation
tools which have been discussed for other problems: local cuts (pioneered by Applegate, Bixby, Chvátal and Cook) and mod-k cuts. We compare the performance of this approach to another one by Rossi and Smiriglio (Oper. Res. Lett. 28:63–74, 2001) and discuss the value of the tools we have tested. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|