Note on solving linear programs in integers
Note on solving linear programs in integers
复制标题
求解整数线性规划的注意事项
DOI：
10.1002/nav.3800060109
复制
发表时间：
1959
期刊：
影响因子：
--
通讯作者：
G. Dantzig
中科院分区：
文献类型：
--
作者：
G. Dantzig
Gomory(普林斯顿)最近的一个结果解决了一个突出的问题，即求解整数线性规划的问题。Gomory展示了如何将线性不等式约束自动添加到线性规划问题中，从而使得到的凸极点只包含最小邻域内的整数解。本文给出了一种生成这些附加约束的另一种方法，该方法易于证明和应用。然而，这些条件是否会像较强的Gomory条件一样，在单纯形法的有限次迭代中得到解，目前尚不清楚。因此，任何考虑其实际用途的人都应该权衡生成的简易性和收敛无疑需要的额外迭代次数。
A recent result of Gomory (Princeton) solved an outstanding problem, namely that of solving linear programs in integers. Gomory showed how to add linear inequality constraints to a linear programming problem automatically in such a way that the extreme points of the resulting convex contain only integral solutions in the neighborhood of the minimum. In this paper an alternative method is given for generating these additional constraints in a way easy to justify and to apply. However it is not known whether these conditions will lead to a solution in a finite number of iterations of the simplex method as is true for the stronger Gomory conditions. Thus anyone considering their practical use should weigh the ease of generation against the extra number of iterations that will undoubtedly be required for convergence.