论文标题
最大独立集（稳定集）问题：使用二进制搜索和凸面编程的计算测试使用垃圾箱包装方法
Maximum independent set (stable set) problem: Computational testing with binary search and convex programming using a bin packing approach
论文作者
论文摘要
本文涉及最大独立集（M.I.S.）问题，也称为稳定集问题。捕获此问题的基本数学编程模型是一个整数程序（i.p.），其中一个变量$ x_j $，并且仅\ textit {edge Inboralities}具有$〜\ textStyle \ sum_ \ sum_ \ sum_ {j = 1}^n x_j〜 $ n $ n $ n $ n $的目标函数值。我们考虑$ LP（K）$，即I.P.的线性编程（LP）放松。带有附加约束$ \ textstyle \ sum_ {j = 1}^n x_j = k ~~（0 \ le k \ le n）。 ~~ $我们然后考虑$ lp（k）$的凸编程变体$ cp（k）$，与$ lp（k）$相同，只是目标函数是非线性凸功能（我们最小化）。 $〜$ $ the M.I.S.可以通过在间隔$ 〜0 \ le k \ le n〜 $中求解$ cp（k）$的每个值来解决问题，其中使用\ it {bin包装}类型的方法将凸功能最小化。在本文中，我们提出了为$ cp（k）$开发凸功能的努力。但是，在最新版本中，在没有凸功能的情况下，我们引入了新功能。在某个实例中，当我们提供部分解决方案（即150个顶点）时，击中最佳完整整数解决方案的频率会大大增加。
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)$.. However, in the latest version, in the absence of a convex function, we have introduced a new function; and for a certain instance, when we provide partial solutions (that is, for 5 vertices out of 150), the frequency of hitting an optimal complete integer solution increases significantly.
