A tutorial on branch and cut algorithms for the maximum stable set problem
A tutorial on branch and cut algorithms for the maximum stable set problem
复制标题
DOI：
10.1111/j.1475-3995.2011.00805.x
复制
发表时间：
2012-01-01
影响因子：
3.1
通讯作者：
Pardalos, Panos M.
中科院分区：
文献类型：
--
作者：
Rebennack, Steffen;Reinelt, Gerhard;Pardalos, Panos M.
This tutorial provides an overview of various characteristics of effective branch and cut type algorithms for the maximum stable set problem. We discuss several facet-defining inequalities for the stable set polytope along with their separation routines. In particular, we review implementation tweaks for the separation routines and reference empirical studies, illustrating the performance of these cutting planes for benchmark graphs. In addition to the polyhedral study, we present basic preprocessing, discuss heuristic methods particularly suited within a branch and cut framework, and examine a branching rule.
