Re: Maximum independent set computation

[Andrew Makhorin]

Hi Prabhu,

Thank you for your interest in glpk and the link to your article.

I think you may be interested in challenge MIS problems, some of which
were used on testing glpk; see https://oeis.org/A265032/a265032.html .


Best regards,

Andrew Makhorin



On Tue, 2022-07-05 at 10:38 +0930, Prabhu Manyem wrote:
> I think you will find this interesting..  GLPK has been very useful,
> very helpful with this research.. Thank you!
> 
> https://arxiv.org/abs/2206.12531  (older version)
> 
> (newer version)
> https://www.researchgate.net/publication/361555319_Maximum_independent
> _set_stable_set_problem_A_mathematical_programming_model_with_valid_in
> equalities_and_computational_testing/stats
> 
> Abstract:
> 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 5000 instances of randomly generated (and
> connected) graphs with up to 45 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.  More testing is required before we can draw
> conclusions about the “likelihood” of the solvability of M.I.S. in
> polynomial time.
> 
> Best,
> 
> -pm
>