The stable set problem: Clique and nodal inequalities revisited. (November 2020)

• Record Type: Journal Article
• Authors: Letchford, Adam N.; Rossi, Fabrizio; Smriglio, Stefano
• Is Part Of: Computers & operations research. Volume 123(2020)
• Publication Date: 2020-11
• Subjects: Stable set problem -- Clique inequalities -- Nodal inequalities; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105024
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The stable set problem is a fundamental problem in combinatorial optimisation. It can be formulated as an integer program in many different ways. We consider formulations based on clique inequalities, nodal inequalities, or a combination of the two. We perform a detailed theoretical and computational study of these formulations. The best formulations work very well on both random and structured instances. 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 so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance.