The Stable Set Problem: Clique and Nodal Inequalities Revisited

Adam N. Letchford(a.n.letchfordlancaster.ac.uk)
Fabrizio Rossi(fabrizio.rossiunivaq.it)
Stefano Smriglio(stefano.smrigliounivaq.it)

Abstract: The stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on various combinations of certain constraints known as clique and nodal inequalities. Extensive computational experiments show that the choice of formulation can have a dramatic effect on the time taken to solve specific instances.

Keywords: stable set problem

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: Working paper, Department of Management Science, Lancaster University, UK.

Download: [PDF]

Entry Submitted: 05/07/2018
Entry Accepted: 05/07/2018
Entry Last Modified: 05/07/2018

Modify/Update this entry