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 7000 instances of randomly generated (and connected) graphs with up to 64 vertices (as well as all 64, 128, and 256-vertex instances at the "challenge" website OEIS.org). 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. Our experience has been that a binary search on the objective function value is a powerful tool which yields a (weakly) polynomial algorithm.
翻译:本文涉及最大独立的数据集( M. I. S. ) 问题, 也称为稳定设置问题 。 包含该问题的基本数学编程模型是一个零一变量的整数程序( I. P. ), 包含零一变量, 只有边缘不平等 。 我们提出了一个强化模型, 增加了线性约束的多数值, 称为有效不平等 ; 这个新模型仍然是图中脊椎数的复数 。 我们对新的整数程序的线性放松进行了计算测试。 我们测试了大约7000例随机生成( 和连接) 图, 最高为64个脊椎( 以及所有64、 128个) 和 256个垂直图 。 在每一个案例中, 线性放松都返回了一个最佳解决方案, (一) 每个变量都有整数值, (二) 线性放松的优化解决方案值与原始( 基本) Integer 程序相同。 我们的经验是, 在“ changegreenge” 网站 OEIS.org 上, 对目标值进行双轨搜索, 是一个强大的工具。