Maximum independent set (stable set) problem: Computational testing with binary search and convex programming using a bin packing approach

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 $x_j$ and only the \textit{edge inequalities} with an objective function value of the form $~\textstyle \sum_{j=1}^N x_j~$ 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 $\textstyle \sum_{j=1}^N x_j = k ~~ (0 \le k \le 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 \le k \le N~$ where the convex function is minimised using a \it{bin packing} type of approach. In this paper, we present efforts to developing a convex function for $CP(k)$.