Maximum independent set (stable set) problem: A mathematical programming model with valid inequalities and computational testing
share
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 I.P. 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 I.P. We tested about 5000 instances of randomly generated (and connected) graphs with up to 40 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) I.P.
READ FULL TEXT