Maximum independent set (stable set) – Computational testing with a bin packing approach – Prabhu Manyem (Nanchang Institute of Technology)

This talk 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 with an objective function value of the form Z = x_1 + x+2 + … + x_N, where N is the number of vertices in the input.  We consider LP (k), which is the Linear programming (LP) relaxation of the I.P. with an additional constraint Z = k (where 1 <= k <= N).  We then consider a convex programming variant CP (k) of LP (k), which is the same as LP(k), except that the objective function is a nonlinear convex function (which we minimise).  The M.I.S. problem can be solved by solving CP(k) for every value of k in the interval [0, N] where the convex function is minimised using a bin packing type of approach.  We present efforts to developing a polynomial convex function for CP (k). When we provide partial solutions for 5 vertices for a 150-vertex instance, the frequency of hitting an optimal complete integer solution increases significantly.  Anyone interested is welcome to follow the manuscript posted at Arxiv or at Researchgate.