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 >