A tutorial on branch and cut algorithms for the maximum stable set problem
Steffen Rebennack, Gerhard Reinelt, Pãnos M. Pardalos · International Transactions in Operational Research · 2011
Abstract 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.