Premium
A tutorial on branch and cut algorithms for the maximum stable set problem
Author(s) -
Rebennack Steffen,
Reinelt Gerhard,
Pardalos Panos M.
Publication year - 2012
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2011.00805.x
Subject(s) - polytope , computer science , branch and cut , preprocessor , heuristic , set (abstract data type) , heuristics , algorithm , benchmark (surveying) , polyhedron , branching (polymer chemistry) , facet (psychology) , mathematical optimization , integer programming , mathematics , artificial intelligence , combinatorics , materials science , geodesy , composite material , programming language , geography , operating system , psychology , social psychology , personality , big five personality traits
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.