Maximum independent set (stable set) problem: A mathematical programming model with valid inequalities and computational testing

This paper deals with the maximum independent set (M.I.S.) problem, also known as the stable set problem. The basic mathematical programming model that captures this problem is an Integer Program (I.P.) with zero-one variables and only the edge inequalities. We present an enhanced model by adding a polynomial number of linear constraints, known as valid inequalities; this new model is still polynomial in the number of vertices in the graph. We carried out computational testing of the Linear Relaxation of the new Integer Program. We tested about 7000 instances of randomly generated (and connected) graphs with up to 64 vertices. In each of these instances, the Linear Relaxation returned an optimal solution with (i) every variable having an integer value, and (ii) the optimal solution value of the Linear Relaxation was the same as that of the original (basic) Integer Program. For certain instances, a binary search on the objective function value is a useful tool which yields a (weakly) polynomial algorithm. We were able to solve all 64-vertex and 128-vertex instances at the OEIS webpage polynomially using a "warm start" approach.