算法的发现(Ⅲ)——非负独立集合问题与线性规划

ON DISCOVERY OF ALGORITHMS (Ⅲ)——Non-negative independent set problem and linear programming

本文讨论最大权非负独立集合问题（§１）。它与等式型线性规划问题等价，因此后者在组合优化中有着明确的“合法”地位。沿着文〔１，２〕的思路，前者得到寻求初始基可行解的生成算法（§３），它与后者的Ｍ法和二步法迥然不同。用对称差分解法自然得到一个算法（§４），相当于改进单纯形算法。最后，还作了几点评注（§５）。

This article discusses non-negative independent set problem (§1). It is equivalent to linear programming problem of equality type. Thus the latter problem has its own “legal” position in combinatorial optimization. Along with the idea of , the former problem has a generation algorithm for finding an initial basic feasible solution(§3). It is very different from the big M method and twostep method for the latter one. The symmetric difference decomposition method gives an algorithm for the former problem (§4), which is equivalent to the revised simplex algorithm for linear programming. Finally, several comments are made (§5).